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

0 – 10 * 1/8 = - 10/8 = - 5/4

0 - (-11) * 1/8 = 11/8

По окончании расчета  всех элементов таблица II в ней получены новый опорный план и коэффициенты разложения векторов Рj через базисные векторы P₃, P₅, P₆, P₈ и значения

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

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

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

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

 

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

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

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

Составим таблицу для III итерации.

Таблица III

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P4	11	85/22	43/55	39/110	0	1	3/22	0	-1/110	0
2	P6	0	155/22	191/55	163/110	0	0	-23/22	1	-7/110	0
3	P3	9	45/11	-14/55	9/55	1	0	-1/11	0	4/55	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			1745/22	2,8	-179/110	0	0	15/22	0	61/110	0

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

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

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

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

 

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P4	11	355/163	-8/163	0	0	1	63/163	-39/163	-1/163	0
2	P2	7	775/163	382/163	1	0	0	-115/163	110/163	-7/163	0
3	P3	9	540/163	-104/163	0	1	0	4/163	-18/163	13/163	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			14190/163	6,62	0	0	0	-76/163	179/163	79/163	0

 

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

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

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

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

j	Базис	Сб	P0	3,5	7	9	11	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	355/63	-8/63	0	0	163/63	1	-13/21	1/63	0
2	P2	7	550/63	142/63	1	0	115/63	0	5/21	-2/63	0
3	P3	9	200/63	-40/63	0	1	-4/63	0	-2/21	5/63	0
4	P8	0	0	0	0	0	0	0	0	0	1
5			5650/63	6,56	0	0	76/63	0	17/21	31/63	0

 

В результате в таблице V получаем новый опорный план

X=(0; 550/63; 220/63; 0; 355/63; 0; 0; 0). и коэффициенты разложения векторов Рj через базисные векторы P₁, P₂, P_3, P₄ соответствующие значения

Проверяем, является ли данный опорный  план оптимальным или нет.

Для этого рассмотрим 5-ю строку, таблицы 3 . В этой строке среди чисел нет отрицательных. Это означает, что найденный опорный план является оптимальным и F_max = 5650/63 = 89,68

Следовательно, план выпуска  продукции, включающий изготовление 550/63(8) изделий 2 и 200/63 (3)изделий 3, является оптимальным. При данном плане выпуска изделий полностью используется сырье II и III видов и остается неиспользованным 355/63 (5,63) ресурсов I вида, а ценность производимой продукции равна 5650/63 = 89,68

Оптимальным планом производства продукции не предусматривается  изготовление изделий 1 и 4 . Введение в план выпуска продукции изделий вида 1 привело бы к уменьшению указанной общей стоимости. Это видно из 5-й строки столбца вектора P1, где число 6,56 показывает, что при данном плане включение в него выпуска единицы изделия 1 приводит лишь к уменьшению общей величины стоимости на 6,56.

Введение в план выпуска  продукции изделий вида 4 привело бы к уменьшению указанной общей стоимости. Это видно из 5-й строки столбца вектора P4, где число 76/63 (1,21) показывает, что при данном плане включение в него выпуска единицы изделия 4 приводит лишь к уменьшению общей величины стоимости на 1,21.

Построить двойственную задачу и решить ее симплекс-методом 

F_max = F =

x_j 0 (j = 1,2,3,4)

 

A =

 

A^T = =

 

=

y_j 0 (j = 1,2,3,4)

Умножим целевую функцию на -1 и  будем искать

S' = -S = -35*y₁ - 50*y₂ - 100*y₃ → MAX 
Cистема ограничений в форме Такера примет вид:  
y₄ = -3,5- ( -6*y₁ - 10y₂ - 4*y₃ ) 
y₅ = -7 - ( -3*y₁ - 5*y₂ - 6*y₃ ) 
y₆ = -9 - (-y₁ - 2*y₂ - 15*y₃ ) 
y₇ = -11 - ( -8*y₁ - 9*y₂ - 10*y₃ ) 
Целевая функция: 
S' = 0 - ( 35*y₁ + 50*y₂ + 100*y₃ )

y₁* P₁ + y₂* P₂ + y₃* P₃ + y₄* P₄ + y₅* P₅ + y₆* P₆ + y₇* P₇ + y₈* P₈

P₁= ; P₂= ; P₃= ; P₄= ; P₅= ; P₆= ; P₇= ; P₈= ;

P₉= .

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

Y=(0, 0, 0,0,3,5, 7, 9;11 )

Составляем симплексную таблицу  I итерации и подсчитываем значения

F₀, z_j – c_j.

Проверяем исходный план на оптимальность:

F₀ = (C,P₀) = 0; z₁ = (C,P₁) = 0 ; z₂ = (C,P₂) = 0; z₃ = (C,P₃) = 0; z₄ = (C,P₄) = 0

z₁ – c₁ = 0 = ; z₂ – c₂ = 0 = ; z₃ – c₃ = 0 = ;

z₄ – c₄ = 0 = .

Для векторов базиса z_i – c_i = 0 (j = 5,6,7,8).

Составим таблицу I итерации

Таблица I

j	Базис	Сб	P0	35	50	100	0	0	0	0	0
				P1	P2	P3	P4	P5	P6	P7	P8
1	P5	0	-3/5	-6	-10	-4	0	1	0	0	0
2	P6	0	-7	-3	-5	-6	0	0	1	0	0
3	P7	0	-9	-1	-2	-15	0	0	0	1	0
4	P8	0	-11	-8	-9	-10	0	0	0	0	1
5			0	35	50	100	0	0	0	0	0