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

Размещено на http://www.allbest.ru/

Вариант 13

Задание 1 (Ресурсная задача)

Для изготовления изделий типа А и В используется сырье трех видов, запасы каждого из которых Р 1 =648, Р 2 = 352, Р 3 = 208. На производство одного изделия типа А требуется затратить а 1 =3 кг сырья первого вида, а₂ =4 кг сырья второго вида, а 3 =2 кг сырья третьего вида. На одно изделие типа В расходуется соответственно b 1= 9 b2 =2 b3=2 кг сырья каждого вида. Прибыль от реализации единицы изделия А составляет a =4 /ден.ед./, а изделия В - b =3 /ден.ед./. Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации. Решить задачу симплекс-методом. Дать геометрическое истолкование задачи.

Решение симплекс-метод прибыль изделие

Определим максимальное значение целевой функции

F(X) = 4x₁ + 3x₂

при следующих условиях-ограничений.

3x₁ + 9x₂?648

4x₁ + 2x₂?352

2x₁ + 2x₂?208

В 1-м неравенстве смысла вводим базисную переменную x₃. В 2-м неравенстве смысла вводим базисную переменную x₄. В 3-м неравенстве смысла вводим базисную переменную x₅.

3x₁ + 9x₂ + 1x₃ + 0x₄ + 0x₅ = 648

4x₁ + 2x₂ + 0x₃ + 1x₄ + 0x₅ = 352

2x₁ + 2x₂ + 0x₃ + 0x₄ + 1x₅ = 208

Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅,

Полагая, что свободные переменные равны 0, получим первый опорный план:

X1 = (0,0,648,352,208)

Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5
x3	648	3	9	1	0	0
x4	352	4	2	0	1	0
x5	208	2	2	0	0	1
F(X0)	0	-4	-3	0	0	0

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x₁, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i1

и из них выберем наименьшее: min (648 : 3 , 352 : 4 , 208 : 2 ) = 88

Следовательно, 2-ая строка является ведущей.

Разрешающий элемент равен (4) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x3	648	3	9	1	0	0	216
x4	352	4	2	0	1	0	88
x5	208	2	2	0	0	1	104
F(X1)	0	-4	-3	0	0	0	0

Вместо переменной x₄ в план 1 войдет переменная x₁.

Строка, соответствующая переменной x₁ в плане 1, получена в результате деления всех элементов строки x₄ плана 0 на разрешающий элемент РЭ=4

Таким образом, в новом плане 1 заполнены строка x₁ и столбец x₁.

Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника.

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

НЭ = СЭ - (А*В)/РЭ

СТЭ - элемент старого плана, РЭ - разрешающий элемент (4), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5
648-(352 * 3):4	3-(4 * 3):4	9-(2 * 3):4	1-(0 * 3):4	0-(1 * 3):4	0-(0 * 3):4
352 : 4	4 : 4	2 : 4	0 : 4	1 : 4	0 : 4
208-(352 * 2):4	2-(4 * 2):4	2-(2 * 2):4	0-(0 * 2):4	0-(1 * 2):4	1-(0 * 2):4
0-(352 * -4):4	-4-(4 * -4):4	-3-(2 * -4):4	0-(0 * -4):4	0-(1 * -4):4	0-(0 * -4):4

Получаем новую симплекс-таблицу:

Базис	B	x1	x2	x3	x4	x5
x3	384	0	71/2	1	-3/4	0
x1	88	1	1/2	0	1/4	0
x5	32	0	1	0	-1/2	1
F(X1)	352	0	-1	0	1	0

Текущий опорный план не оптимален, так как в индексной строке находятся отрицательные коэффициенты.

В качестве ведущего выберем столбец, соответствующий переменной x₂, так как это наибольший коэффициент по модулю.

Вычислим значения D_i по строкам как частное от деления: b_i / a_i2

и из них выберем наименьшее: min (384 : 7¹/₂ , 88 : ¹/₂ , 32 : 1 ) = 32

Следовательно, 3-ая строка является ведущей.

Разрешающий элемент равен (1) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	min
x3	384	0	71/2	1	-3/4	0	511/5
x1	88	1	1/2	0	1/4	0	176
x5	32	0	1	0	-1/2	1	32
F(X2)	352	0	-1	0	1	0	0

Вместо переменной x₅ в план 2 войдет переменная x₂.

Строка, соответствующая переменной x₂ в плане 2, получена в результате деления всех элементов строки x₅ плана 1 на разрешающий элемент РЭ=1

На месте разрешающего элемента в плане 2 получаем 1.

В остальных клетках столбца x₂ плана 2 записываем нули.

Таким образом, в новом плане 2 заполнены строка x₂ и столбец x₂.

Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника.

Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5
384-(32 * 71/2):1	0-(0 * 71/2):1	71/2-(1 * 71/2):1	1-(0 * 71/2):1	-3/4-(-1/2 * 71/2):1	0-(1 * 71/2):1
88-(32 * 1/2):1	1-(0 * 1/2):1	1/2-(1 * 1/2):1	0-(0 * 1/2):1	1/4-(-1/2 * 1/2):1	0-(1 * 1/2):1
32 : 1	0 : 1	1 : 1	0 : 1	-1/2 : 1	1 : 1
352-(32 * -1):1	0-(0 * -1):1	-1-(1 * -1):1	0-(0 * -1):1	1-(-1/2 * -1):1	0-(1 * -1):1

Получаем новую симплекс-таблицу:



Базис	B	x1	x2	x3	x4	x5
x3	144	0	0	1	3	-71/2
x1	72	1	0	0	1/2	-1/2
x2	32	0	1	0	-1/2	1
F(X2)	384	0	0	0	1/2	1

Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5
x3	144	0	0	1	3	-71/2
x1	72	1	0	0	1/2	-1/2
x2	32	0	1	0	-1/2	1
F(X3)	384	0	0	0	1/2	1

Оптимальный план можно записать так:

x₁ = 72 x₂ = 32

F(X) = 4*72 + 3*32 = 384

Область допустимых решений представляет собой многоугольник

Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых(2) и (3), то ее координаты удовлетворяют уравнениям этих прямых:

4x₁+2x₂=352

2x₁+2x₂=208

Решив систему уравнений, получим: x₁ = 72, x₂ = 32

Откуда найдем максимальное значение целевой функции:

F(X) = 4*72 + 3*32 = 384

Задание 2. (Транспортная задача)

Имеются 3 пункта поставки однородного груза А 1 , А 2 , А 3 и 5 пунктов потребления этого груза В 1 , В 2 , В 3 , В 4 , В 5 . На пунктах А I ( I = 1,2,3 ) груз находится соответственно в количествах а 1 , а 2 , а 3 условных единиц. В пункты В J (J=1,2,3,4,5) требуется доставить соответственно b J единиц груза. Стоимость перевозки единицы груза (с учетом расстояний) из А I в В J определена матрицей С={c ij}. Решить задачу тремя методами (северо-западного угла, минимальной стоимости и методом Фогеля) и найти такой план закрепления потребителей и поставщиков, чтобы общие затраты на перевозки были минимальны.

а 1 =150, а 2 = 230, а 3 = 250, b 1 =110, b 2 =100, b 3 = 200, b 4 = 140, b 5 = 80,

Решение

1. Метод северо-западного угла

	1	2	3	4	5	Предложение
1	8	3	5	7	5	150
2	7	9	3	7	4	230
3	8	7	5	6	9	250
Спрос	110	100	200	140	80

Проверим необходимое и достаточное условие разрешимости задачи.

?a = 150 + 230 + 250 = 630

?b = 110 + 100 + 200 + 140 + 80 = 630

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

x₁₁ = min (150,110) = 110

x₁₂ = min (40,100) = 40.

x₂₂ = min (230,60) = 60.

x₂₃ = min (170,200) = 170.

x₃₃ = min (250,30) = 30.

x₃₄ = min (220,140) = 140.

x₃₅ = 80.

	1	2	3	4	5	Предложение
1	110 8	40 3	5	7	5	150
2	7	60 9	170 3	7	4	230
3	8	7	30 5	140 6	80 9	250
Спрос	110	100	200	140	80

число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Стоимость перевозок по этому плану:

Z1 = 8*110 + 3*40 + 9*60 + 3*170 + 5*30 + 6*140 + 9*80 = 3760

Проверим оптимальность опорного плана, полагая, что u₁ = 0.

u₁ + v₁ = 8; 0 + v₁ = 8; v₁ = 8

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₂ + v₂ = 9; 3 + u₂ = 9; u₂ = 6

u₂ + v₃ = 3; 6 + v₃ = 3; v₃ = -3

u₃ + v₃ = 5; -3 + u₃ = 5; u₃ = 8

u₃ + v₄ = 6; 8 + v₄ = 6; v₄ = -2

u₃ + v₅ = 9; 8 + v₅ = 9; v₅ = 1

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(2;1): 6 + 8 > 7; ?₂₁ = 6 + 8 - 7 = 7

(2;5): 6 + 1 > 4; ?₂₅ = 6 + 1 - 4 = 3

(3;1): 8 + 8 > 8; ?₃₁ = 8 + 8 - 8 = 8

(3;2): 8 + 3 > 7; ?₃₂ = 8 + 3 - 7 = 4

max (7,3,8,4) = 8

Перспективная клетка (3;1).

Сдвиг цикла 30.

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

Проверим оптимальность опорного плана.

u₁ + v₁ = 8; 0 + v₁ = 8; v₁ = 8

u₃ + v₁ = 8; 8 + u₃ = 8; u₃ = 0

u₃ + v₄ = 6; 0 + v₄ = 6; v₄ = 6

u₃ + v₅ = 9; 0 + v₅ = 9; v₅ = 9

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₂ + v₂ = 9; 3 + u₂ = 9; u₂ = 6

u₂ + v₃ = 3; 6 + v₃ = 3; v₃ = -3

Опорный план не является оптимальным, так как:

(1;5): 0 + 9 > 5; ?₁₅ = 0 + 9 - 5 = 4

(2;1): 6 + 8 > 7; ?₂₁ = 6 + 8 - 7 = 7

(2;4): 6 + 6 > 7; ?₂₄ = 6 + 6 - 7 = 5

(2;5): 6 + 9 > 4; ?₂₅ = 6 + 9 - 4 = 11

max (4,7,5,11) = 11

Перспективная клетка (2;5). Сдвиг цикла 30

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

Проверим оптимальность опорного плана

u₁ + v₁ = 8; 0 + v₁ = 8; v₁ = 8

u₃ + v₁ = 8; 8 + u₃ = 8; u₃ = 0

u₃ + v₄ = 6; 0 + v₄ = 6; v₄ = 6

u₃ + v₅ = 9; 0 + v₅ = 9; v₅ = 9

u₂ + v₅ = 4; 9 + u₂ = 4; u₂ = -5

u₂ + v₃ = 3; -5 + v₃ = 3; v₃ = 8

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

Опорный план не является оптимальным, так как

(1;3): 0 + 8 > 5; ?₁₃ = 0 + 8 - 5 = 3

(1;5): 0 + 9 > 5; ?₁₅ = 0 + 9 - 5 = 4

(3;3): 0 + 8 > 5; ?₃₃ = 0 + 8 - 5 = 3

max (3,4,3) = 4

Перспективная клетка (1;5). Сдвиг цикла 50

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

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₁ + v₅ = 5; 0 + v₅ = 5; v₅ = 5

u₂ + v₅ = 4; 5 + u₂ = 4; u₂ = -1

u₂ + v₃ = 3; -1 + v₃ = 3; v₃ = 4

u₃ + v₅ = 9; 5 + u₃ = 9; u₃ = 4

u₃ + v₁ = 8; 4 + v₁ = 8; v₁ = 4

u₃ + v₄ = 6; 4 + v₄ = 6; v₄ = 2

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

Zmin = 3*100 + 5*50 + 3*200 + 4*30 + 8*110 + 6*140 = 2990

2. Метод Фогеля

Получим таблицу:

	1	2	3	4	5	Предложение	Разности по столбцам
1	0 8	100 3	5	7	50 5	150	2	2	2	2
2	7	9	200 3	7	30 4	230	1	1	3
3	110 8	7	5	140 6	9	250	1	1	2	2
Спрос	110	100	200	140	80
Разности по строкам	1	4	2	1	1
	1		2	1	1
	1			1	1
	1			1	4

Стоимость перевозок по этому плану:

Z1=100*3+50*5+200*3+30*4+110*8+140*6=300+250+600+120+880+840=2990

Проверим оптимальность опорного плана.

u₁ + v₁ = 8; 0 + v₁ = 8; v₁ = 8

u₃ + v₁ = 8; 8 + u₃ = 8; u₃ = 0

u₃ + v₄ = 6; 0 + v₄ = 6; v₄ = 6

u₁ + v₂ = 3; 0 + v₂ = 3; v₂ = 3

u₁ + v₅ = 5; 0 + v₅ = 5; v₅ = 5

u₂ + v₅ = 4; 5 + u₂ = 4; u₂ = -1

u₂ + v₃ = 3; -1 + v₃ = 3; v₃ = 4

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

Z min = 2990

3. Метод минимальной стоимости

Минимальный тариф

c₁₂=3, x₁₂ = min (150,100) = 100.

c₂₃=3, x₂₃ = min (230,200) = 200.

c₂₅=4, x₂₅ = min (30,80) = 30.

c₁₅=5, x₁₅ = min (50,50) = 50.

c₃₄=6, x₃₄ = min (250,140) = 140.

x₃₁ = min (110,110) = 110.



	1	2	3	4	5	Предложение
1	8	100 3	5	7	50 5	150
2	7	9	200 3	7	30 4	230
3	110 8	7	5	140 6	9	250
Спрос	110	100	200	140	80

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m + n - 1 = 7. Следовательно, опорный план является вырожденным.

Значение целевой функции для этого опорного плана равно:

Z1 = 3*100 + 5*50 + 3*200 + 4*30 + 8*110 + 6*140 = 2990

Следовательно, заполняем числом «0» пустую клетку (3,3), т.к. она имеет минимальный тариф (с₃₃ = 5), и не образует с занятыми клетками замкнутого прямоугольного контура.

Получаем опорный план:

	v1=8	v2=3	v3=4	v4=6	v5=5
u1=0	8	100 3	5	7	50 5
u2=-1	7	9	200 3	7	30 4
u3=0	110 8	7	0 5	140 6	9

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию

u_i + v_i <= c_ij.

Минимальные затраты составят:

Zmin = 3*100 + 5*50 + 3*200 + 4*30 + 8*110 + 6*140 = 2990

Размещено на Allbest.ru