Учебная работа № 6287. «Контрольная Симплекс 11
Учебная работа № 6287. «Контрольная Симплекс 11
Содержание:
«1) Исходные данные
Вид ресурсов Вид продукции Ограничение по сырью
А1 А2
А1 1 3 300
А2 3 4 447
А3 4 1 441
Прибыль 52 39
»
Выдержка из похожей работы
преобразований (привести систему
ограничений к диагональному виду),
Пример
7,Следующую задачу ЛП решить
двухфазным симплекс-методом:
minf(x)=x1-x2+1 (13)
при
ограничениях
(14)
x1,
x2,
x3≥0 (15)
Первая
фаза (цель: при- помощи искусственного
базиса и симплекс-метода определить
базисные переменные из числа исходных
переменных),
В
систему (14)вводим
искусственные переменныеx3≥0,×5≥0,×6≥0
(предварительно умножив обе части
второго неравенства на -1),новую целевую функцию как сумму всех
искусственных переменных, а старую
присоединяем к ограничениям:
minz(x)
=x4 +x5 +x6
(16)
при
ограничениях
(17)
Искусственные
переменные x4,x5,x6выбираем в качестве
базисных, а все
остальныеx1,x2,x3
-небазисных, По правилу симплекс-метода
исключаем базисные переменные из целевой
функции (16)(при помощи
уравнений системы (17), содержащих эти
переменные):
z(x)=
-2×1- 15×2- 5×3+ 15
или,
что все равно
z(x)+2×1+15
x2+5
x3=15
(19)
Начальное
д,б,р,
x0=(x10,x20,x30,x40,x50,x60)=(0, 0, 0, 1,
3,11)
называется
искусственным базисом, При помощи этого
базиса, и выражений (19), (17)строим начальную симплекс-таблицуI-ой
фазы,
x1
x2
x3
x4
x5
x6
z
15
2
15
5
0
0
0
f
1
-1
1
0
0
0
0
x4
1
2
(1)
3
1
0
0
x5
3
-1
3
-1
0
1
0
x3
11
1
11
3
0
0
1
До
конца Iфазы роль нулевой
строки играет строка для z,все остальное как в симплекс-методе
(см, примеры 5,6),Следует
только заметить, что строка для
fне участвует в выборе ведущей
строки,
Из
(16)видно, чтоminz(x)
= 0и достигается приx4=x5 =x6=0,те, задача (16)-(18) будет решена, если все
искусственные переменные будут вытеснены
из базиса, а z=0,Это и будет
означать конец первой фазы и переход
ко второй фазе,
Обратите
внимание, что в первой таблице ведущей
может быть любая из последних трех строк
(предвестник зацикливания), В таких
случаях можно выбрать любой из них
-выберем первую строку, Так как
искусственная переменнаяx4выходит из базиса, то соответствующий
столбик в дальнейшем можно исключить,
В результате соответствующих преобразований
получим вторую симплекс-таблицу,
x1
x2
x3
x4
x5
z
0
-28
0
-40
0
0
f
0
-3
0
-3
0
0
x2
1
2
1
3
1
0
x5
0
-7
0
-10
0
1
x6
0
-21
0
-30
0
0
Из
таблицы следует, что minzдостигнут, однако искусственные
переменныеx5иx6еще не выведены из базиса