Экономико-математический практикум (стр. 2 из 9)
Ответ: minZ(X*) =3,5.
2. Двойственная задача
Двойственная задача имеет вид.
при условиях
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
 | ||
с базисом 
. Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:
| 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 в третьей строке и выполняем преобразование Жордана.