Теорема 1 (первая теорема двойственности)
Если одна из пары двойственных задач I и II разрешима, то разрешима и другая, причем значения целевых функций на оптимальных планах совпадают, F(x*)=G(y*), где х*, у* – оптимальные решения задачи I и II
Теорема 2 (вторая теорема двойственности)
Планы х* и у* оптимальны в задачах I и II тогда и только тогда, когда при подстановке их в систему ограничений задачи I и II соответственно, хотя бы одно из любой пары сопряженных неравенств обращается в равенство.
Решение исходной задачи двойственным симплекс методом
Двойственный симплекс–метод основан на очень простой идее. Поскольку решая исходную задачу, мы автоматически получаем решение двойственной, то иногда удобно выбирать, какую из задач решать, естественно, более простую по форме, а затем, решив, находим оптимальное решение другой. Этот метод удобно применять при решении задачи о рационе, задачи о раскрое и некоторых других ЗЛП
Идея двойственного симплекс–метода заключается в следующем. По данной задаче построить двойственную, решить двойственную (ее форма имеет более простой вид), а затем автоматически выписать решение исходной.
Возможны ситуации:
1. В индексной F– строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком. Переходим к IV этапу.
|
|
|
2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных элементов. Тогда делаем вывод о том, что целевая функция F→∞ неограниченно убывает.
3. В индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к следующему III шагу, пересчитываем таблицу, улучшая опорный план.
Имеем задачу (I) построим ей двойственную (II).
I. 
II. 
F=2X1+X2®min G=24Y1 + 18Y2 + 20Y3 + 6Y 4®max
Приведем ее к каноническому виду.
Введем базисные переменные 
, 
G=- G = -24Y1 - 18Y2 - 20Y3 - 6Y 4® min
Решаем симплекс–методом задачу .
1.Найдем разрешающий элемент.
1.1. Из отрицательных элементов индексной F– строки выберем наибольший по модулю, назовем соответствующий ему столбец – разрешающим.
1.2. Чтобы выбрать разрешающую строку, необходимо вычислить отношения элементов столбца свободных членов к только положительным элементам разрешающего столбца. Выбрать из полученных отношений минимальное. Соответствующий элемент, на котором достигается минимум, называется разрешающим. Будем выделять его цветом.
В нашем примере, 
(Таблица 1), элемент 3 – разрешающий. Строка, соответствующая этому элементу тоже называется разрешающей.
|
|
|
Таблица 1
| базисные | -Y1 | -Y2 | -Y3 | -Y 4 | свободные |
| Y5 | 3 | 1 | 4 | 0 | 2 |
| Y6 | 4 | 2 | 0 | 1 | 1 |
| -G | -24 | -18 | -20 | -6 | 0 |
2. Выбрав разрешающий элемент, делаем перечет таблицы по правилам:
2.1. В новой таблице, таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В данной задаче: Y 1 входит в базис, вместо
Y 5, которая выходит из базиса, и теперь свободная.
2.2. На месте разрешающего элемента записываем обратное ему число 
(Таблица 2).
2.3. Элементы разрешающей строки делятся на разрешающий элемент.
2.4. Элементы разрешающего столбца делятся на разрешающий элемент и записываются с противоположным знаком.
2.5. Чтобы заполнить оставшиеся элементы таблицы 5, осуществляем пересчет по правилу прямоугольника.
Пусть мы хотим посчитать элемент, стоящий на месте 2(Y2;Y6 )
(Таблица 1).Соединяем этот элемент мысленно с разрешающим элементом, находим произведение, вычитаем произведение элементов, находящихся на другой диагонали получившегося прямоугольника. Разность делим на разрешающий элемент.
|
|
|
Итак, 
. Записываем 
на место, где было 3(Таблица 2).
Пересчитываем так все элементы:
Таблица 2
| базисные | Y5 | Y2 | Y3 | Y 4 | свободные |
| Y1 | 
|
| 
| 0 |
|
| Y6 | 
|
| 
| 1 |
|
| -G | 8 | -10 | 12 | -6 | 16 |
Проверим целевую функцию, согласно условиям.
В индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к следующему III шагу, пересчитываем таблицу, улучшая опорный план.
Таблица 3
| базисные | -Y5 | -Y1 | -Y3 | -Y 4 | свободные |
| Y2 | 1 | 3 | 4 | 0 | 2 |
| Y6 | -2 | -2 |
| 1 | -3 |
| -G | 18 | 30 | 52 | -6 | 36 |
Таблица 4
| базисные | -Y5 | -Y1 | -Y3 | -Y 6 | свободные |
| Y2 | 1 | 3 | 4 | 0 | 2 |
| Y4 | -2 | -2 |
| 1 | -3 |
| -G | 6 | 18 | 16 | 6 | 54 |
В индексной F– строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятым с противоположным знаком. Переходим к IV этапу.
Выписываем решение согласно таблице 4:
Y1= 0; Y4=-3;
Y2= 2; Y5= 0;
Y3 = 0; Y6= 0;
Подставляем полученные решения в условия задачи:
I. 
II. 
Два условия в II системе не совпадают, выписываем из в I системы эти условия и решаем как систему уравнений.
|
|
|
F=2X1+X2®min = 2*6+6 = 18
Ответ к задаче:
Для эффективного откорма крупно рогатого скота необходимо 6 корма b1 и 6 корма b2 . При этом затраты минимальны и составят 18 руб.
Дата добавления: 2018-09-22; просмотров: 249; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!