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

 

Для определения остальных  элементов таблицы II применим правило треугольника. 

Вычислим элементы таблицы II, стоящие в столбце Р0.

 

Первый  элемент был вычислен ранее ₀ = 35/8)

 

Второй элемент - находим три числа

1) число, стоящее в т. 1 на пересечении столбца Р₀ и 2-ой строки (50);

2) число, стоящее в т. 1 на пересечении столбца Р₄ и 2-ой строки (9);

3) число, стоящее в т. 2 на пересечении столбца Р₀ и 1-ой строки (35/8).

50 - 9*35/8 = 85/8

Третий элемент

1) число, стоящее в т. 1 на пересечении столбца Р₀ и 3-ей строки (100);

2) число, стоящее в т. 1 на пересечении столбца Р₄ и 3-ей строки (10);

3) число, стоящее в т. 2 на пересечении столбца Р₀ и 1-ой строки (35/8).

100 - 10*35/8 = 225/4

Четвёртый элемент -

1) число, стоящее в т. 2 на пересечении столбца Р₀ и 4-ой строки (0);

2) число, стоящее в т. 2 на пересечении столбца Р₄ и 4-ой строки (0);

3) число, стоящее в т. 3 на пересечении столбца Р₀ и 1-ой строки (35/8).

0 - 0*35/8 = 0

 

Значение F0 в 5-ой строке этого же столбца можно найти двумя способами:

1) по формуле  F₀ = (C,P₀) =  11* 35/8  + 0 * 85/8 + 0 * 225/4  = 385/8

2) по правилу треугольника: 11* 35/8  = 385/8

 

Вычислим элементы вектора Р1 т.2. Первые два числа берем из столбцов Р1 и Р4  т.1, а третье число – из т.2 на пересечении 1- ой строки и столбца Р1

10 – 9 * 3/4 = 13/4  ,   4 – 10 * 3/4 = -7/2 , 0 - 0 * 3/4  = 0

 

Значение z₁ – c₁ в 5-ой строке столбца вектора Р1

можно найти двумя  способами:

1) по формуле  z₁ – c₁ = (C,P₁)-с₁ =  11 * 3/4  + 0 * 13/4  + 0 * (-7/2)  – 3,5  =  4,75

2) по правилу треугольника: - 3,5 -  (-11) * 3/4     = 4,75

 

Аналогично находим  элементы столбца вектора P₂, P₃, P₄

5 - 9* 3/8  = 13/8         6 – 10 * 3/8  = 9/4                0 - 0 * 3/8  = 0

- 7 -  (- 11) * 3/8  = -23/8

 

2 - 9* 1/8  = 7/8           15 – 10 * 1/8  = 55/4                0 - 0 * 1/8  =  0

- 9 -  (-11) * 1/8  = -61/8

 

Элементы столбца вектора Р₅ вычисляем по правилу треугольника.

Однако построенные  для определения этих элементов  треугольники вы- глядят иначе.

При вычислении элемента 2-й строки указанного столбца получается

треугольник, образованный числами 0;9 и 1/8. Следовательно, искомый элемент равен

0 – 9* 1/8 = - 9/8  

Элемент, стоящий в 3-й  строке данного столбца, равен 

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 имеется четыре единичных вектора, то для дан- ной задачи можно записать опорный план