Контрольная работа Экономико-математический практикум
Работа добавлена на сайт bukvasha.net: 2015-10-25Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
от 25%
договор
Гипероглавление:
СПЕЦИАЛЬНОСТЬ «Менеджмент организаций »
К О Н Т Р О Л Ь Н А Я Р А Б О Т А
2. Двойственная задача
Проанализируем решение задачи
Решение задачи 2
x1 x2 x3 x4 x5 bi (1)
Решим симплекс-методом задачу линейного программирования, используя метод искусственного базиса
3.Построим двойственную задачу
Проанализируем решение задачи
Транспортная задача
1.Метод северо-западного угла.
Опорный план построен (табл. 3.2).
Исходные данные
удовлетворены.
удовлетворены.
Х0 Таблица 3.3.
3. Метод Фогеля
Сетевая задача
Задача о назначениях
1. Метод потенциалов.
Предварительный этап. Исходная матрица C:
Основной этап.
РОССИЙСКАЯ ФЕДЕРАЦИЯ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
По предмету: Экономико-математический практикум
Выполнил:
Студент 2 курса
4 семестр
Рахимова Лидия Рустамовна
Ташкент,2009
Задача № 1
Условно стандартная задача линейного программирования
Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи:
а) графическим методом;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
6. Найти оптимальное целочисленное решение:
а) графическим методом;
б) Методом Гомори.
Сравнить значения функций целочисленного и нецелочисленного решений
4
Решение задачи 1
1. Найдем оптимальный план решения графическим методом:
;
Построим на координатной плоскости Ох1х2 граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):
Область допустимых решений определяется многоугольником ОАВСD (см. график 1).
Для линий уровня х1 - 3х2 = h (h — const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L3 и L4, т. е. через точку . Для определения координат точки P решаем систему уравнений
.
Получаем х1 = 5,3, х2 = 0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Zmin=3,5
График № 1
1б) Перейдем к расширенной задаче:
Данная расширенная задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:
Расчеты проведем в таблице (Табл. 1)
Таблица 1
Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора Аk, вводимого в базис опорного решения, и вектора Аl, выводимого из базиса. Наибольшая положительная оценка соответствует А2, за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.
Вектор А2 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второе опорное решение с базисом (табл. 1.3). Целевая функция =-3М -21. Это решение не является оптимальным, так как есть положительная оценка.
Таблица 1
Целевая функция после второй итерации равна = 3,5. Все оценки отрицательные, план оптимален.
Оптимальный план исходной задачи Х*=(х1*=5,3; х2*=0,6). Минимальное значение целевой функции исходной задачи =3,5.
Ответ: min Z(X*) =3,5.
2. Двойственная задачаСПЕЦИАЛЬНОСТЬ «Менеджмент организаций »
К О Н Т Р О Л Ь Н А Я Р А Б О Т А
2. Двойственная задача
Проанализируем решение задачи
Решение задачи 2
x1 x2 x3 x4 x5 bi (1)
Решим симплекс-методом задачу линейного программирования, используя метод искусственного базиса
3.Построим двойственную задачу
Проанализируем решение задачи
Транспортная задача
1.Метод северо-западного угла.
Опорный план построен (табл. 3.2).
Исходные данные
удовлетворены.
удовлетворены.
Х0 Таблица 3.3.
3. Метод Фогеля
Сетевая задача
Задача о назначениях
1. Метод потенциалов.
Предварительный этап. Исходная матрица C:
Основной этап.
РОССИЙСКАЯ ФЕДЕРАЦИЯ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ТЮМЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ИНСТИТУТ ДИСТАНЦИОННОГО ОБРАЗОВАНИЯ
СПЕЦИАЛЬНОСТЬ «Менеджмент организаций »
К О Н Т Р О Л Ь Н А Я Р А Б О Т А
По предмету: Экономико-математический практикум
Выполнил:
Студент 2 курса
4 семестр
Рахимова Лидия Рустамовна
Ташкент,2009
Задача № 1
Условно стандартная задача линейного программирования
Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи:
а) графическим методом;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
6. Найти оптимальное целочисленное решение:
а) графическим методом;
б) Методом Гомори.
Сравнить значения функций целочисленного и нецелочисленного решений
4
Решение задачи 1
1. Найдем оптимальный план решения графическим методом:
;
Построим на координатной плоскости Ох1х2 граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе):
Область допустимых решений определяется многоугольником ОАВСD (см. график 1).
Для линий уровня х1 - 3х2 = h (h — const) строим нормальный вектор . Перпендикулярно нормальному вектору построим одну из линий уровня (на рис. 1 она проходит через начало координат) Так как задача на минимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L3 и L4, т. е. через точку . Для определения координат точки P решаем систему уравнений
.
Получаем х1 = 5,3, х2 = 0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Zmin=3,5
|
|
|
|
|
| ||||||
| ||||||
|
График № 1
1б) Перейдем к расширенной задаче:
Данная расширенная задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:
Расчеты проведем в таблице (Табл. 1)
Таблица 1
| | | | 1 | -3 | 0 | 0 | 0 | 0 | M |
| Б | Сб | В | А1 | А2 | А3 | А4 | А5 | А6 | А7 |
| А3 | 0 | 9 | -2 | 3 | 1 | 0 | 0 | 0 | 0 |
| А4 | 0 | 53 | 5 | 2 | 0 | 1 | 0 | 0 | 0 |
| А5 | 0 | 17 | 4 | -7 | 0 | 0 | 1 | 0 | 0 |
← | А7 | М | 37 | 6 | 8 | 0 | 0 | 0 | 1 | 1 |
| | 0 | –1 | 3 | 0 | 0 | 0 | 0 | 0 | |
| | 37 | 6 | 8 | 0 | 0 | 0 | 0 | 0 |
Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора Аk, вводимого в базис опорного решения, и вектора Аl, выводимого из базиса. Наибольшая положительная оценка соответствует А2, за разрешающий элемент выбираем коэффициент 8 и выполняем преобразование Жордана.
Вектор А2 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем второе опорное решение с базисом (табл. 1.3). Целевая функция =-3М -21. Это решение не является оптимальным, так как есть положительная оценка.
Таблица 1
Б | Сб | B | А1 | А2 | А3 | А4 | А5 | А6 | |
А2 | -3 | 3,0 | -0,7 | 1,0 | 0,3 | 0,0 | 0,0 | 0,0 | 0,0 |
А4 | 0 | 47,0 | 6,3 | 0,0 | -0,7 | 1,0 | 0,0 | 0,0 | 0,0 |
А5 | 0 | 38,0 | -0,7 | 0,0 | 2,3 | 0,0 | 1,0 | 0,0 | 0,0 |
a7 | М | 13,0 | 11,3 | 0,0 | -2,7 | 0,0 | 0,0 | 1,0 | 1,0 |
M+1 | -9,0 | 1,0 | 0,0 | -1,0 | 0,0 | 0,0 | 0,0 | 0,0 | |
M+2 | 13,0 | 11,3 | 0,0 | -2,7 | 0,0 | 0,0 | 0,0 | 0,0 | |
A2 | -3 | -2,4 | -0,6 | 1,0 | 0,0 | 0,0 | -0,1 | 0,0 | 0,0 |
a4 | 0 | 57,9 | 6,1 | 0,0 | 0,0 | 1,0 | 0,3 | 0,0 | 0,0 |
А3 | 0 | 16,3 | -0,3 | 0,0 | 1,0 | 0,0 | 0,4 | 0,0 | 0,0 |
A7 | М | 56,4 | 10,6 | 0,0 | 0,0 | 0,0 | 1,1 | 1,0 | 1,0 |
M+1 | 7,3 | 0,7 | 0,0 | 0,0 | 0,0 | 0,4 | 0,0 | 0,0 | |
M+2 | 56,4 | 10,6 | 0,0 | 0,0 | 0,0 | 1,1 | 0,0 | 0,0 | |
A2 | -3 | 0,6 | 0,0 | 1,0 | 0,0 | 0,0 | -0,1 | 0,1 | 0,1 |
a4 | 0 | 25,1 | 0,0 | 0,0 | 0,0 | 1,0 | -0,4 | -0,6 | -0,6 |
А5 | 0 | 17,8 | 0,0 | 0,0 | 1,0 | 0,0 | 0,5 | 0,0 | 0,0 |
A1 | 1 | 5,3 | 1,0 | 0,0 | 0,0 | 0,0 | 0,1 | 0,1 | 0,1 |
| | 3,5 | 0,0 | 0,0 | 0,0 | 0,0 | 0,4 | -0,1 | -0,1 |
| | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | 0,0 | -1,0 | -1,0 |
Целевая функция после второй итерации равна = 3,5. Все оценки отрицательные, план оптимален.
Оптимальный план исходной задачи Х*=(х1*=5,3; х2*=0,6). Минимальное значение целевой функции исходной задачи =3,5.
Ответ: min Z(X*) =3,5.
Двойственная задача имеет вид.
при условиях
3. Прямая задача имеет оптимальное решение, вычислим оптимальное решение двойственной задачи, используя условия дополняющей нежесткости
Откуда следует:
4. Оптимальный план двойственной задачи найдем, используя окончательную симплекс-таблицу прямой задачи (Табл.1)
Максимальное значение функции двойственной задачи совпадает с минимальным значением функции прямой задачи, что подтверждает первую теорему двойственности.
Проанализируем решение задачи, используя условия дополняющей нежесткости (вторую теорему двойственности). Подставляем координаты оптимального решения двойственной задачи Y* = (0;0;-0,35;-0,068), в систему ограничений.
Ответ: Z(X) =3,5 при Х* = (0;0;-0,35;-0,068).
Задача № 2
Каноническая задача
В каждом варианте приведены таблицы, в которых записаны условия канонической задачи линейного программирования на минимум, т. е.
В первой строке помещены коэффициенты целевой функции. В остальных строках, в первых пяти столбцах, находятся векторы условий, а в последнем столбце записан вектор ограничений. В правом верхнем углу таблицы указана цель задачи.
Необходимо последовательно выполнить следующие задания.
1. Задачу решить графическим методом.
2. Применяя симплекс-метод, решить задачу, т.е. найти ее оптимальный план и минимальное значение целевой функции или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.
3. Построить двойственную задачу. Если вектор найден, вычислить оптимальный план двойственной задачи, используя первую теорему двойственности . Вычислить максимальное значение функции .
4. Провести анализ полученного решения, применяя условия дополняющей нежесткости.
Если , то .
Если , то .
| 14 | | | | | |
1 | -5 | 6 | 8 | -2 | min | |
11 | 7 | 1 | 12 | 5 | 16 | |
14 | 10 | 0 | 3 | 8 | 17 | |
13 | 2 | 9 | 4 | 6 | 15 | |
Решение задачи 2
Представим исходные данные задачи в виде:
Проверяем, применим ли графический метод при решении данной задачи.
линейно независимы, так как их координаты непропорциональны. Поэтому ранг системы векторов-условий r = 3. Находим n - r =5 - 3 = 2 £ 2. Следовательно, метод применим.
1. Приведём систему уравнений-ограничений к равносильной, разрешённой методом Жордана–Гаусса. Преобразуем систему уравнений методом Жордана-Гаусса до получения общего решения (табл. 2.1).
Таблица 2.1.
№ итерац. | x1 | x2 | x3 | x4 | x5 | bi |
(1) | 11 | 7 | 1 | 12 | 5 | 16 |
14 | 10 | 0 | 3 | 8 | 17 | |
13 | 2 | 9 | 4 | 6 | 15 | |
(2) | -45,00 | -33,00 | 1,00 | 0,00 | -27,00 | -52,00 |
4,67 | 3,33 | 0,00 | 1,00 | 2,67 | 5,67 | |
-5,67 | -11,33 | 9,00 | 0,00 | -4,67 | -7,67 | |
(3) | 2,25 | 0,75 | 1,00 | 10,13 | 0,00 | 5,38 |
1,75 | 1,25 | 0,00 | 0,38 | 1,00 | 2,13 | |
2,50 | -5,50 | 9,00 | 1,75 | 0,00 | 2,25 | |
(4) | -12,21 | 32,57 | -51,07 | 0,00 | 0,00 | -7,64 |
1,21 | 2,43 | -1,93 | 0,00 | 1,00 | 1,64 | |
1,43 | -3,14 | 5,14 | 1,00 | 0,00 | 1,29 | |
(5) | 0,24 | -0,64 | 1,00 | 0,00 | 0,00 | 0,15 |
1,68 | 1,20 | 0,00 | 0,00 | 1,00 | 1,93 | |
0,20 | 0,14 | 0,00 | 1,00 | 0,00 | 0,52 |
Общее решение системы уравнений имеет вид
Учитывая, что все переменные неотрицательны, перейдем от уравнений к неравенствам из общего решения системы.
откуда получим систему неравенств с двумя переменными
Целевую функцию выразим через свободные переменные
Окончательно получим стандартную задачу линейного программирования с двумя переменными
Строим область допустимых решений (график 2). Любая точка многоугольника удовлетворяет системе неравенств. Вершина является точкой входа семейства прямых в область решений, следовательно, в этой точке она принимает минимальное значение.
В свою очередь, =(1,32;0,12).
Решая систему уравнений получаем х1 =2,2, х2 =0,6. Это и будет оптимальным решением данной задачи, которому соответствует минимальное значение целевой функции Zmin
.
|
|
A
А
|
|
(3)
график 2
2. Решим симплекс-методом задачу линейного программирования, используя метод искусственного базиса
Составим расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом +1. Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим переменную х6, во второе — переменную х7, в третье – х8. Данная задача — задача на нахождение минимума. Получаем
Данная расширенная задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:
Записываем исходные и расчетные данные в симплексную таблицу (табл.2.2).
Таблица 2.2
| | | | 1 | -5 | 6 | 8 | -2 | М | M | M |
| Б | Сб | А0 | А1 | А2 | А3 | А4 | А5 | А6 | A7 | A8 |
| А6 | М | 16 | 11 | 7 | 1 | 12 | 5 | 1 | 0 | 0 |
| A7 | M | 17 | 14 | 10 | 0 | 3 | 8 | 0 | 1 | 0 |
← | А8 | М | 15 | 13 | 2 | 9 | 4 | 6 | 0 | 0 | 1 |
| | 0 | -1 | 5 | -6 | -8 | 2 | 0 | 0 | 0 | |
| | 48 | 28 | 19 | 10 | 19 | 19 | 0 | 0 | 0 |
Начальное опорное решение не является оптимальным, так как в задаче на минимум имеются положительные оценки. Выбираем номер вектора Аk, вводимого в базис опорного решения, и вектора Аl, выводимого из базиса. В столбце «А3» (см. табл. 2.1) за разрешающий элемент выбираем коэффициент 9 в третьей строке и выполняем преобразование Жордана.
Вектор А3 выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем первое опорное решение с базисом (табл. 2.3). Целевая функция =31,33М -10. Это решение не является оптимальным, так как имеются положительные оценки.
Таблица 2.3
| | | | 1 | -5 | 6 | 8 | -2 | М | M | M |
| Б | Сб | А0 | А1 | А2 | А3 | А4 | А5 | А6 | A7 | A8 |
| А6 | М | 14,33 | 9,56 | 6,78 | 0,00 | 11,56 | 4,33 | 1,00 | 0,00 | -0,11 |
| A7 | M | 17,00 | 14,00 | 10,00 | 0,00 | 3,00 | 8,00 | 0,00 | 1,00 | 0,00 |
← | А3 | 6 | 1,67 | 1,44 | 0,22 | 1,00 | 0,44 | 0,67 | 0,00 | 0,00 | 0,11 |
| | 10,00 | -7,67 | -6,33 | 0,00 | 5,33 | -6,00 | 0,00 | 0,00 | -0,67 | |
| | 31,33 | 13,56 | 16,78 | 0,00 | 14,56 | 12,33 | 0,00 | 0,00 | -1,11 |
Вводим вектор А4 в базис, получаем второе опорное решение (таблица 2.4) с базисом . Целевая функция = 3,38+13,28M. Далее в таблице 2.4 приведены расчеты с третьей по пятую итерации.
Таблица 2.4
| | | 4 | 2 | -1 | 5 | 1 | М | M | M | |
Б | Сб | А0 | А1 | А2 | А3 | А4 | А5 | А6 | A7 | A8 | |
a4 | 8 | 1,24 | 0,83 | 0,59 | 0,00 | 1,00 | 0,38 | 0,09 | 0,00 | -0,01 | |
a7 | M | 13,28 | 11,52 | 8,24 | 0,00 | 0,00 | 6,88 | -0,26 | 1,00 | 0,03 | |
a3 | 6 | 1,12 | 1,08 | -0,04 | 1,00 | 0,00 | 0,50 | -0,04 | 0,00 | 0,12 | |
| 3,38 | -12,08 | -9,46 | 0,00 | 0,00 | -8,00 | -0,46 | 0,00 | -0,62 | ||
| 13,28 | 1,52 | 8,24 | 0,00 | 0,00 | 6,88 | -1,26 | 0,00 | -0,97 | ||
a4 | 8 | 0,52 | 0,20 | 0,14 | 0,00 | 1,00 | 0,00 | 0,10 | -0,05 | -0,01 | |
a5 | -2 | 1,93 | 1,68 | 1,20 | 0,00 | 0,00 | 1,00 | -0,04 | 0,15 | 0,00 | |
a3 | 6 | 0,15 | 0,24 | -0,64 | 1,00 | 0,00 | 0,00 | -0,02 | -0,07 | 0,11 | |
| | 18,84 | 1,33 | 0,13 | 0,00 | 0,00 | 0,00 | -0,76 | 1,16 | -0,58 | |
| | 0,00 | -10,00 | 0,00 | 0,00 | 0,00 | 0,00 | -1,00 | -1,00 | -1,00 | |
a1 | 1 | 2,60 | 1,00 | 0,69 | 0,00 | 5,04 | 0,00 | 0,51 | -0,27 | -0,06 | |
a5 | -2 | -2,42 | 0,00 | 0,04 | 0,00 | -8,44 | 1,00 | -0,89 | 0,61 | 0,10 | |
a3 | 6 | -0,47 | 0,00 | -0,80 | 1,00 | -1,20 | 0,00 | -0,14 | -0,01 | 0,13 | |
| | 4,19 | 0,00 | -0,79 | 0,00 | -6,68 | 0,00 | -1,44 | 1,53 | -0,51 | |
| | 25,99 | 0,00 | 6,90 | 0,00 | 50,35 | 0,00 | 4,07 | -3,75 | -1,56 |
Целевая функция после пятой итерации равна = 4,19. Положительных оценок нет, план оптимален. Ответ: min Z(X*) =4,2.
3.Построим двойственную задачу
Используя вторую симметричную пару двойственных задач, составим задачу, двойственную к исходной:
Вводим неотрицательные дополнительные переменные у4, у5, у6 у7, у8 для приведения задачи к каноническому виду:
Находим начальное опорное решение Y1 = (0,0,0,1,-5,6,8,-2) с базисом Б1 = (А4, А5, А6, А7, А8). Решение задачи симплексным методом приведено в табл. 2.5. (расчеты табл.2.2. и табл.2.4.)
Таблица 2.5
| | | | 1 | -5 | 6 | 8 | -2 | М | M | M | ||
| Б | Сб | А0 | А1 | А2 | А3 | А4 | А5 | А6 | A7 | A8 | ||
← | А6 | М | 16 | 11 | 7 | 1 | 12 | 5 | 1 | 0 | 0 | ||
| A7 | M | 17 | 14 | 10 | 0 | 3 | 8 | 0 | 1 | 0 | ||
| А8 | М | 15 | 13 | 2 | 9 | 4 | 6 | 0 | 0 | 1 | ||
| | 0 | -1 | 5 | -6 | -8 | 2 | 0 | 0 | 0 | |||
| | 48 | 28 | 19 | 10 | 19 | 19 | 0 | 0 | 0 | |||
| a1 | 1 | 2,60 | 1,00 | 0,69 | 0,00 | 5,04 | 0,00 | 0,51 | -0,27 | -0,06 | ||
| a5 | -2 | -2,42 | 0,00 | 0,04 | 0,00 | -8,44 | 1,00 | -0,89 | 0,61 | 0,10 | ||
| a3 | 6 | -0,47 | 0,00 | -0,80 | 1,00 | -1,20 | 0,00 | -0,14 | -0,01 | 0,13 | ||
| 4,19 | 0,00 | -0,79 | 0,00 | -6,68 | 0,00 | -1,44 | 1,53 | -0,51 | ||||
| 25,99 | 0,00 | 6,90 | 0,00 | 50,35 | 0,00 | 4,07 | -3,75 | -1,56 | ||||
Приведем оптимальное решение прямой задачи
Окончательный базис, соответствующий оптимальному решению прямой задачи, состоит из векторов А2А3А4 поэтому базисная матрица имеет вид
Решение прямой задачи начиналось с единичного базиса А6,А7,А8 . Поэтому в окончательной таблице указанные столбцы преобразуются в матрицу , обратную к базисной матрице , следовательно,
Оптимальный план двойственной найдем из соотношения
Откуда При этом плане максимальное значение функции двойственной задачи составляет величину равную
Максимальное значение целевой функции двойственной задачи совпадает с минимальным значением целевой функции прямой задачи.
5. Проанализируем решение задачи, используя условия дополняющей нежесткости (вторую теорему двойственности).
Подставляем координаты оптимального решения двойственной задачи в систему ограничений.
Первое, третье и пятое ограничения выполняются как строгие неравенства, следовательно, их координаты оптимального решения исходной задачи равны нулю: . Учитывая это, первую, вторую и пятую координаты оптимального решения Х* находим при совместном решении уравнений-ограничений исходной задачи:
Ответ: Z(X) = 4,2 при Х* = (0;1,6; 0;4,9;0).
Задача № 3
Транспортная задача
Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», «двойного предпочтения», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.
| 24 | | | | | |
34 | 30 | 39 | 29 | 18 | 82 | |
40 | 35 | 45 | 41 | 10 | 36 | |
36 | 38 | 41 | 50 | 8 | 79 | |
14 | 10 | 13 | 10 | 12 | 80 | |
77 | 60 | 22 | 68 | 50 | | |
Решение.
1.Метод северо-западного угла.
Исходные данные задачи сведем в таблицу (табл. 3.1).
Таблица 3.1.
Поставщики | Потребители | Запасы | ||||
| | | | | ||
| 34 | 30 | 39 | 29 | 18 | 82 |
| 40 | 35 | 45 | 41 | 10 | 36 |
| 36 | 38 | 41 | 50 | 8 | 79 |
| 14 | 10 | 13 | 10 | 12 | 8 0 |
Потребности | 77 | 60 | 22 | 6 8 | 50 | |
Решение. Построим опорный план задачи методом северо-западного угла.
Объем перевозки и последовательность заполнения матрицы будем записывать в соответствующие клетки табл. 3.2.
Цифры, стоящие в скобках над объемами перевозок, обозначают номер шага, на котором определяются эти перевозки.
1. х11(1)=min(82,77)=77. Потребности первого потребителя удовлетворены, исключаем его. Запасы первого поставщика уменьшились на х11(1) и стали равны (82-77=5) 5.
2. х12(1)=min(5,60)=5. Запасы первого поставщика исчерпаны, исключим первую строку. Второй потребитель удовлетворил свои потребности на 5 единиц, его спрос уменьшился на величину х11(1) и стал равным 55.
3. х22(3)=min(36,55)=36. После третьего шага ресурсы поставщика А2 исчерпаны. Спрос потребителя B2 равен b2(3)=55-36=19.
4. х23(4)=min(79,19)=19. Следует исключить потребителя B2. Ресурсы поставщика А3(4) = a3 – х23(4)=79-19=60 составляет 60 единиц.
5. х33(5)=min(60,22)=22. Потребитель В3 полностью удовлетворил свой спрос, исключаем столбец 3.
6. х34(6)=min(38,68)=38. Следует исключить поставщика А3, запасы которого исчерпаны. Спрос потребителя В4 в4(6) – х34(5)=68-38=30 составляет 30 единиц.
7. х44(7)=min(80,30)=30. Спрос четвертого потребителя удовлетворен. Запасы поставщика А4 составляет
80-30=50.
8. х45(8)=min(50,50)=0. Запасы исчерпаны, потребности удовлетворены.
Опорный
план построен (табл. 3.2).
Таблица 3.2.
34 | 3 0 | 3 9 | 29 | 18 | |
77(1) | 5(2) | | | | 82 |
4 0 | 35 | 4 5 | 41 | 10 | |
| 36(3) | | | | 36 |
36 | 3 8 | 41 | 50 | 8 | |
| 19(4) | 22(5) | 38(6) | | 79 |
1 4 | 1 0 | 1 3 | 1 0 | 1 2 | |
| | | 30(7) | 50(8) | 8 0 |
7 7 | 60 | 22 | 6 8 | 50 | |
Суммарные транспортные издержки на перевозку продукции от поставщиков к потребителю составляют
2.Метод минимального элемента.
Исходные данные
поставщики | потребители | Запасы | ||||
В1 | В2 | В3 | В4 | В5 | ||
А1 | 34 | 30 | 39 | 29 | 18 | 82 |
А2 | 40 | 35 | 45 | 41 | 10 | 36 |
А3 | 36 | 38 | 41 | 50 | 8 | 79 |
А4 | 14 | 10 | 13 | 10 | 12 | 8 0 |
потребности | 77 | 60 | 22 | 6 8 | 50 | |