Курсовая работа: Линейное программирование как метод оптимизации

Х1 (0,3,0,0,0,1); F1 = 9*0+14*3+15*0+10*0+0*0+0*1 = 42

Приняв этот план видим, что выпуск 2го вида продукции является наиболее выгодным, остаток сырья 2го вида продукции составит 1 единица.

Т.к. не все ∆ ≥ 0, план не является оптимальным, поэтому продолжим…..

Вектором Р3 заменим Р6 min= (3/1, 1/1) = (3,1)

6. Составим 3 симплексную таблицу

Базис	Сб	Р0	Р1	Р2	Р3	Р4	Р5	Р6
			9	14	15	10	0	0
Р2	14	2	2	1	0	3	2	-1
Р3	15	1	-1	0	1	-1	-1	1
4	0	0	17	13	1

3-1*1/1=2; 1- (-1) *1/1=2; 1-0*1/1=1; 2-1* (-1) /1=3; 1-1* (-1) /1=2; 0-1*1/1=-1

∆1 = 14*2+15* (-1) - 9 = 4; ∆ 2 = 14*1+15*0-14 = 0; ∆ 4 = 14*3+15* (-1) - 10 = 17;

∆ 5 = 14*2+15* (-1) - 0 = 13; ∆ 6 = 14* (-1) +15*1-0 = 1;

Х2 = (0,2,1,0,0,0); F2 = 9*0+14*2+15*1+0 = 43

План является оптимальным, говорим о том, что наиболее выгодным является производство 2единиц 2 вида продукции и 1единицы 3 вида продукции, причем сырье расходуется полностью.

6. Теоремы двойственности и их использование в задачах ЛП

Каждой задаче линейного программирования можно определенным образом сопоставить некоторую другую задачу (линейного программирования), называемую двойственной или сопряженной по отношению к исходной или прямой задаче. Дадим определение двойственной задачи по отношению к общей задаче линейного программирования , состоящей, как мы уже знаем, в нахождении максимального значения функции

(42)

при условиях

(43)

(44)

Определение.

Задача, состоящая в нахождении минимального значения функции

(45)

при условиях

(46)

(47)

называется двойственной по отношению к задаче (42) - (44). Задачи (42) - (44) и (45) - (47) образуют пару задач, называемую в линейном программировании двойственной парой. Сравнивая две сформулированные задачи, видим, что двойственная задача составляется согласно следующим правилам:

1. Целевая функция исходной задачи (42) - (44) задается на максимум, а целевая функция двойственной (45) - (47) - на минимум.

2. Матрица

(48)

составленная из коэффициентов при неизвестных в системе ограничений (43) исходной задачи (42) - (44), и аналогичная матрица

(49)

в двойственной задаче (45) - (47) получаются друг из друга транспонированием (т.е. заменой строк столбцами, а столбцов - строками).

3. Число переменных в двойственной задаче (45) - (47) равно числу ограничений в системе (43) исходной задачи (42) - (44), а число ограничений в системе (46) двойственной задачи - числу переменных в исходной задаче.