2.5 Двойственный симплекс-метод
Метод работает с теми же симплексными таблицами, что и прямой симплекс - метод для задачи на минимум. Сначала определяется переменная, подлежащая выводу из базиса, а затем переменная, вводимая в базис.
Вычислительная схема двойственного симплекс – метода
Шаг 0. Начинаем с симплексной таблицы
|
B |
|
… |
|
L |
|
|
… |
|
|
|
|
… |
|
… |
… |
………….. |
||
|
|
|
… |
|
Таблица 4 –Исходная симплекс таблица
где
.
Шаг 1.
Проверка на оптимальность. Если
,
то решение
– оптимальное.
Шаг 2.
Выбор ведущей строки. Выбираем среди
номеров i,
для которых
,
номер k
с максимальным по модулю значением:
. (15)
Строка k объявляется ведущей.
Шаг 3.
Проверка на неразрешимость. Если в
строке
нет отрицательных элементов, то
двойственная целевая функция неограниченна
и, следовательно, прямая задача не имеет
допустимых решений. Процесс решения
завершается.
Шаг 4. Выбор ведущего столбца s. Выбираем среди отрицательных элементов строки элемент с номером s, для которого выполняется равенство:
. (16)
Столбец s
объявляется ведущим,
а элемент
- ведущим
элементом.
Шаг 5. Проводим стандартное преобразование симплексной таблицы (Шаг 6 из прямого симплекс-метода).
3 Расчетная часть
Составим оптимальную структуру посевов, максимизирующую суммарный сбор урожая.
Структура посева будет иметь следующий вид:
xij=
Введём обозначения:
x11=x1; x12=x2; x13=x3; x21=x4; x22=x5; x23=x6; x31=x7; x32=x8; x33=x9.
Зададим произвольные параметры урожайности (ц/га) по каждой культуре на каждом из участков и размера участка в гектарах.
Составим матрицу урожайности с числовыми значениями:
=
Также составим матрицу размера участка:
=
В результате получим следующую целевую функцию и ограничения:
L=64x1+40х2+56х3+100х4+130х5+30х6+5х7+75х8+100х9 → max
x1+x2+x3=1;
x4+x5+x6=1;
x7+x8+x9=1.
Далее решаем методом искусственного базиса:
Таблица 5 – Исходная симплекс-таблица:
-
B
b
x1
x2
x3
x4
x5
x6
x7
x8
x9
h
3
1
1
1
1
1
1
1
1
1
y1
1
1
1
1
0
0
0
0
0
0
y2
1
0
0
0
1
1
1
0
0
0
y3
1
0
0
0
0
0
0
1
1
1
Таблица 6 – Конечная симплекс-таблица метода искусственного базиса:
-
B
b
y1
x2
x3
y2
x5
x6
y3
x8
x9
h
0
-1
0
0
-1
0
0
-1
0
0
x1
1
1
1
1
0
0
0
0
0
0
x4
1
0
0
0
1
1
1
0
0
0
x7
1
0
0
0
0
0
0
1
1
1
Таблица 7 – Исходная таблица для прямого симплекс-метода на максимум:
-
B
b
x2
x3
x5
x6
x8
x9
f
169
24
8
-30
70
-70
-95
x1
1
1
1
0
0
0
0
x4
1
0
0
1
1
0
0
x7
1
0
0
0
0
1
1
Таблица 8 – Оптимальное решение задачи:
-
B
b
x2
x3
x4
x6
x8
x7
f
294
24
8
30
100
25
95
x1
1
1
1
0
0
0
0
x5
1
0
0
1
1
0
0
x9
1
0
0
0
0
1
1
х1=х11;
х5=х22;
х9=х33
=>
Так как полученное решение целочисленное, то применения метода Гомори не требуется. Содержательно данное решение означает, что для достижения максимального суммарного сбора урожая необходимо первый тип культур посалить на первом участке, второй тип культур посадить на втором участке и третий тип культур посадить на третьем участке. При этом все ограничения выполняются, то есть полученное решение является оптимальным.