183894 (584851), страница 2
Текст из файла (страница 2)
Оптимальный план исходной задачи Х*=(х1*=5,3; х2*=0,6). Минимальное значение целевой функции исходной задачи =3,5.
Ответ: min Z(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
Каноническая задача
В каждом варианте приведены таблицы, в которых записаны условия канонической задачи линейного программирования на минимум, т. е.
В первой строке помещены коэффициенты целевой функции. В остальных строках, в первых пяти столбцах, находятся векторы условий, а в последнем столбце записан вектор ограничений. В правом верхнем углу таблицы указана цель задачи.
Необходимо последовательно выполнить следующие задания.
-
Задачу решить графическим методом.
-
Применяя симплекс-метод, решить задачу, т.е. найти ее оптимальный план
![]()
и минимальное значение целевой функции ![]()
или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса. -
Построить двойственную задачу. Если вектор
![]()
найден, вычислить оптимальный план ![]()
двойственной задачи, используя первую теорему двойственности ![]()
. Вычислить максимальное значение функции ![]()
. -
Провести анализ полученного решения, применяя условия дополняющей нежесткости.
и минимальное значение целевой функции 
или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.
двойственной задачи, используя первую теорему двойственности 
. Вычислить максимальное значение функции 
. Если 
, то 
.
Если 
, то 
.
| 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. Следовательно, метод применим.
-
Приведём систему уравнений-ограничений к равносильной, разрешённой методом Жордана–Гаусса. Преобразуем систему уравнений методом Жордана-Гаусса до получения общего решения (табл. 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
.
18
16
14
12
(1)
10
8
6
4
A
А 
2
2
4
6
8
10
12
14
16
-2
-4
18
-1
-2
(2)
(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 приведены расчеты с третьей по пятую итерации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
