Контрольная работа по "Методам оптимальных решений"

Поскольку среди векторов Рj имеется три единичных вектора, то для данной задачи можно записать опорный план

Х=(0, 0,0,0,35, 50, 100) определяемый системой трехмерных единичных векторов (Р5;Р6;Р7), которые образуют базис трехмерного векторного пространства.  

Составляем симплексную таблицу I итерации, подсчитываем значение F0, Zj-cj и проверяем исходный опорный план на оптимальность:

F₀ = (c,P₀)=0*50+0*40+0*100=0

          Z₁ =(c,P₁)=0*3+0*4+0*1=0,

          Z₂=(c,P₂)=0,  Z₃=(c,P3)=0,  Z₄=(c,P4)=0,

Z₅= Z₆= Z₇=0.

          Z₁-c₁=0-3,5 = -3,5     Z₂-c₂=0-7= -7, Z₃-c₃=0-9 = -9, Z₄-c₄=0 -11= -11

Zj-cj=0, для j=5, 6, 7.

                                                                Таблица I итерации

Cбаз	Базис	План P0	3,5	7	9	11	0	0	0
			P1	P2	P3	P4	P5	P6	P7
0	P5	35	6	3	1	8	1	0	0
0	P6	50	10	5	2	9	0	1	0
0	P7	100	4	6	15	10	0	0	1
Zk		0	0	0	0	0	0	0	0
k = Zk - ck			-3,5	-7	-9	-11	0	0	0

 

	Нормы расхода ресурсов на единичное  изделие				Запас ресурсов
	изделие 1	изделие 2	изделие 3	изделие 4
Ресурс 1	6	3	1	8	35
Ресурс 2	10	5	2	9	50
Ресурс 3	4	6	15	10	100
Ценность	3,5	7	9	11

 

Как видно из таблицы I итерации, значения всех основных переменных х1, х2, х3, х4 равны нулю, дополнительные переменные принимают свои значения в соответствии с ограничениями задачи. Эти значения переменных отвечают такому «плану», при котором ничего не производится, сырье не используется и значение целевой функции равно нулю (т.е. стоимость произведенной продукции отсутствует).

Этот план не может  быть оптимальным!

В пятой строке таблицы I итерации имеются четыре отрицательных числа: Z₁-c₁=0-3,5= -3,5    Z₂-c₂=0-7= -7, Z₃-c₃=0 - 9 = -9, Z₄-c₄=0-11= -11

Отрицательные числа  не только свидетельствуют о возможности  увеличения общей стоимости производимой продукции, но и показывают, на сколько увеличится эта сумма при введении в план единицы того или иного вида продукции.

Так, число – 3,5 означает, что при включении в план производства одного изделия 1-го вида обеспечит увеличение выпуска продукции на 6р. Если включить в план производства по одному изделию 2-го, 3-го и 4-го вида, то общая стоимость произведенной продукции возрастет соответственно на 7; 9 и 11 р. соответственно.

Поэтому с экономической  точки зрения наиболее целесообразно включить в план производства изделия третьего вида.

Это же необходимо сделать  и на основании формального признака симплексного метода, поскольку максимальное по абсолютной величине отрицательное  число стоит в пятой строке столбца Р3. Следовательно, введем в базис вектор Р3.

Данную задача частично решена в задаче 2

Поэтому данные возьмём  из  задачи 2 и добавим недостающие  параметры.

 

Cбаз	Базис	План P0	3,5	7	9	11	0	0	0
			P1	P2	P3	P4	P5	P6	P7
11	P4	35/8	3/4	3/8	1/8	1	1/8	0	0
0	P6	85/8	13/4	13/8	7/8	0	-9/8	1	0
0	P7	225/4	-7/2	9/4	55/4	0	-5/4	0	1
Zk		385/8	8,25	33,8	11/8	11	11/8	0	0
k = Zk - ck			4,75	-23/8	-61/8	0	11/8	0	0

 

 

_k = Z_k - c_k  => Z_k = _k  + c_k              c₁=3,5, c₂=7, c₃=9, c₄ = 11, c₅=0

 

Z₁-c₁= 4,75 + 3,5 = 8,25     Z₂-c₂= -23/8 + 7 = 33/8    Z₃-c₃= -61/8 + 9 = 11/8,

Z₄-c₄=0 + 11= 11                 Z₅-c₅=11/8 + 0 =11/8

 

Как видно из таблицы II итерации новым опорным планом задачи является план Х=(0;0; 0; 35/8;0;85/8;225/4). Этот план не является оптимальным, так как на пересечении столбца Р3 и пятой строки стоит отрицательный элемент

-61/8.

 

Значит, в базис следует  ввести вектор P₃, т. е. в новом плане следует предусмотреть выпуск изделий 3.

При определении возможного числа изготовления изделий 1 следует учитывать имеющееся количество сырья каждого вида, а именно: возможный выпуск изделий 1 определяется для т.е. находим min( / /) для a_i2>0

₀ min(35/8/1/8; 85/8/7/8; 225/4/55/4) = 225/4/55/4 = 45/11

Следовательно, исключению из базиса подлежит вектор Р₇ иными словами, выпуск изделий 3 ограничен имеющимся в распоряжении предприятия ресурсом III вида. С учетом имеющихся объемов этого сырья предприятию следует изготовить (45/11) 4 изделия 3. Число 55/4 является разрешающим элементом, а столбец вектора P3 и 3-я строка таблицы 2 являются направляющими.         

 

 

                            

 

Cбаз	Базис	План P0	3,5	7	9	11	0	0	0
			P1	P2	P3	P4	P5	P6	P7
11	P4	85/22	43/55	39/110	0	1	3/22	0	-1/110
0	P6	155/22	191/55	163/110	0	0	-23/22	1	-7/110
9	P3	45/11	-14/55	9/55	1	0	-1/11	0	4/55
Zk		1745/22	6,3	591/110	0	0	15/22	0	61/110
k = Zk - ck			2,8	-179/110	0	0	15/22	0	61/110

                                                              

_k = Z_k - c_k  => Z_k = _k  + c_k              c₁=3,5, c₂=7, c₃=9, c₄ = 11, c₅=0, c₇=0

 

Z₁-c₁= 2,8 + 3,5 = 6,3            Z₂-c₂= -179/110 + 7 = 591/110    Z₃-c₃= 0 + 9 = 9,

Z₄-c₄=0  + 11= 11          Z₅-c₅=15/22 + 0 = 15/22    Z₇-c₇=61/110 + 0 = 61/110

 

Найденный на III итерации план задачи не является оптимальным.

Это видно и из 5-й строки таблицы 2, поскольку в столбце вектора P₂ этой строки стоит отрицательное число – 179/110 

Значит, в базис следует  ввести вектор P₂ т. е. в новом плане следует предусмотреть выпуск изделия 2.

Исключению из базиса подлежит вектор Р₆

Cбаз	Базис	План P0	3,5	7	9	11	0	0	0
			P1	P2	P3	P4	P5	P6	P7
11	P4	355/163	-8/163	0	0	1	63/163	-39/163	-1/163
7	P2	775/163	382/163	1	0	0	-115/163	110/163	-7/163
9	P3	540/163	-104/163	0	1	0	4/163	-18/163	13/163
Zk		14190/163	10,12	7	9	11	-76/163	179/163	79/163
k = Zk - ck			6,62	0	0	0	-76/163	179/163	79/163

                                                              

_k = Z_k - c_k  => Z_k = _k  + c_k              c₁=3,5, c₂=7, c₃=9, c₄ = 11, c₅=0, c₆=0, c₇=0

 

Z₁-c₁= 6,62 + 3,5 = 10,12  Z₂-c₂= 0+ 7 = 7    Z₃-c₃= 0 + 9 = 9, Z₄-c₄=0  + 11= 11          Z₅-c₅= -76\163 + 0 = -76\163 Z₆-c₆=179/163 + 0 = 179/163 Z₇-c₇=79/163 + 0 = 79/163

 

Найденный на IV итерации план задачи не является оптимальным.

Это видно и из 5-й строки таблицы 2, поскольку в столбце вектора P₅ этой строки стоит отрицательное число – 76/163

Значит, в базис следует  ввести вектор P₅ 

Исключению из базиса подлежит вектор Р₄

Cбаз	Базис	План P0	3,5	7	9	11	0	0	0
			P1	P2	P3	P4	P5	P6	P7
0	P5	355/63	-8/63	0	0	163/63	1	-13/21	1/63
7	P2	550/63	142/63	1	0	115/63	0	5/21	-2/63
9	P3	200/63	-40/63	0	1	-4/63	0	-2/21	5/63
Zk		5650/63	10,06	7	9	769/63	0	17/21	31/63
k = Zk - ck			6,56	0	0	76/63	0	17/21	31/63