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

 

Ячейка а₂,b₃ становится свободной.

M =35

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	40		60
a2 = 150	35	80		35
a3 = 50				50

 

 
Итерация: 3 
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

 

	b1	b2	b3	b4
a1	5	1	3	– 5	u1 = 10
a2	1	2	6	6	u2 = 6
a3	6	6	6	2	u3 = 2
	v1 = – 5	v2 = – 4	v3 = – 7	v4 = 0

 

 

 

1) Пусть V₄ = 0 ;

2) U₃ = P_3,4 – V₄ = 2 – 0 = 2;

3) U₂ = P_2,4 – V₄ = 6 – 0 = 6;

4) V₁ = P_2,1 – U₂ = 1 – 6 = – 5;

5) V₂ = P_2,2 – U₂ = 2 – 6 = – 4;

6) U₁ = P_1,1 – V₁ = 5 – (– 5) = 10;

7) V₃ = P_1,3 – U₁ = 3 – 10 = – 7.

 

S₁₂ = P₁₂ – U₁ – V₂ = 7 – 10 – (– 4) = 1

S₁₄ = P₁₄ – U₁ – V₄ = 5 – 10 – 0 = – 5

S₂₃ = P₂₃ – U₂ – V₁ = 5 – 6 – (– 7) = 6

S₃₁ = P₃₁ – U₃ – V₁ = 3 – 2 – (– 5) = 6

S₃₂ = P₃₂ – U₃ – V₂ = 4 – 2 – (– 4) = 6

S₃₃ = P₃₃ – U₃ – V₃ = 1 – 2 – (– 7) = 6

Ячейка а₁,b₄, транспортной таблицы, должна загрузиться.

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	40 –		60	+
a2 = 150	35 +	80		35 –
a3 = 50				50

 

Ячейка а₂,b₄ становится свободной.

M = 35

 

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	5		60	35
a2 = 150	70	80
a3 = 50				50

 

Итерация: 4 
Рабочая матрица затрат с пересчитанными потенциалами и оценкам.

 

	b1	b2	b3	b4
a1	5	1	3	6	u1 = 5
a2	1	2	6	5	u2 = 1
a3	1	1	1	2	u3 = 2
	v1 = 0	v2 = 1	v3 = – 2	v4 = 0

 

1) Пусть V₄ = 0 ;

2) U₃ = P_3,4 – V₄ = 2 – 0 = 2;

3) U₁ = P_1,4 – V₄ = 5 – 0 = 5;

4) V₁ = P_1,1 – U₁ = 5 – 5 = 0;

5) U₂ = P_2,1 – V₁ = 1 – 0 = 1;

6) V₂ = P_2,2 – U₂ = 2 – 1 = 1;

7) V₃ = P_1,3 – U₁ = 3 – 5 = – 2.

S₁₂ = P₁₂ – U₁ – V₂ = 7 – 5 – 1 = 1

S₂₃ = P₂₃ – U₂ – V₃ = 5 – 1 – (– 2) = 6

S₂₄ = P₂₄ – U₂ – V₄ = 6 – 1 – 0 = 5

S₃₁ = P₃₁ – U₃ – V₁ = 3 – 2 – 0 = 1

S₃₂ = P₃₂ – U₃ – V₂ = 4 – 2 – 1 = 1

S₃₃ = P₃₃ – U₃ – V₃ = 1 – 2 – (– 2) = 1

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

	b1= 75	b2= 80	b3= 60	b4= 85
a1 = 100	5 5		60 3	35 5
a2 = 150	70 1	80 2
a3 = 50				50 2

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

P_опт=5 * 5 + 60 * 3+35 * 5 + 70 * 1 + 80 * 2 + 50 * 2 = 710

Задача 4

Решить задачи целочисленного программирования геометрическим методом.

 

F=3x₁+2x₂ max,

2x₁+x₂ 5

-2x₁+3x₂ 10

x₁ 0, x₂ 0,

x₁, x₂ – целые

 

Решение:

Поскольку число неизвестных  задачи равно двум, то решение данной задачи можно найти, используя ее геометрическую интерпретацию. Для  этого, прежде всего, построим многоугольник  решений задачи, состоящей в определении  максимального значения функции  F_max = 3x₁+2x₂ при выполнении условий 2x₁+x₂ 5 и -2x₁+3x₂ 10 (см. рисунок 2).

Координаты всех точек  построенного многоугольника решений OABC удовлетворяют системе линейных неравенств 2x₁+x₂ 5 и -2x₁+3x₂ 10

и условию не отрицательности  переменных x₁ 0, x₂ 0. Кроме того, точка С является точкой пересечения прямых 2x₁+x₂ 5 и -2x₁+3x₂ 10 , заданных уравнениями: 2x₁+x₂ 5 и -2x₁+3x₂ 10 соответственно. На этих прямых находятся граничные точки системы ограничений 2x₁+x₂ 5 и -2x₁+3x₂ 10 и x₁ 0, x₂ 0.

Уточним границу области допустимых решений задачи F=3x₁+2x₂ и x₁, x₂ – целые целочисленного программирования. Для этого придадим переменной x₁ целочисленные значения от 0 до 6 и вычислим соответствующие целочисленные значения x₂ (интервал изменения x₁ от 0 до 3 получается из многоугольника решений).

2x₁+x₂ 5 и -2x₁+3x₂ 10 , при x₁ = 0 x₂ 5 x₂ 10/3 => так как x2 – целочисленная переменная. x₂ 5. Получаем граничную точку К(0;5).

2x₁+x₂ 5 и -2x₁+3x₂ 10 , при x₁ = 1 x₂ 3 x₂ 12/3 => так как x2 – целочисленная переменная. x₂ 3. Получаем граничную точку M(1;3).

2x₁+x₂ 5 и -2x₁+3x₂ 10 , при x₂ = 2 x₂ 1 x₂ 14/3 => так как x2 – целочисленная переменная. x₂ 1. Получаем граничную точку P(2;1).

Придав переменной x₁ последовательные значения 2x₁+x₂ 5 и -2x₁+3x₂ 10 найдем координаты оставшихся граничных точек L(0;3), N(1;1), Q(2;0),

Таким образом, границей области  допустимых решений данной задачи целочисленного программирования является ступенчатая  линия 

OKLMNPQ.

 

Строим график

 

Рис 2.

 

Для нахождения максимума функции  F_max = 3x₁+2x₂ рассмотрим вектор,

=(3;2) где  3 и 2 – коэффициенты при неизвестных x₁ и x₂ целевой функции.

Будем рассматривать линии уровня функции F, т.е. прямые F= const.

Например, положим F=5.

Построим прямую F=3x₁+2x₂ с уравнением F=5 или F=3x₁+2x₂ =5.

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

В данном случае искомой является точка K(0;5) в которой целевая функция принимает максимальное значение Fmax = 0*3 +2*5 = 0.

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

Задача 5

Решить задачу линейно численным  программированием

 

	Нормы расхода ресурсов на единичное изделие				Запас ресурсов
	изделие 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

 

Решение:

Составим математическую модель. Обозначим:

х₁ – выпуск изделия 1;

х₂ – выпуск изделия 2;

х₃ – выпуск изделия 3.

x₄ – выпуск изделия 4.

 

Запишем систему ограничений:

Общая ценность произведенных товаров  составляет:

F =

По экономическому содержанию переменные х₁, х₂, х₃, х₄ могут принимать только неотрицательные значения: х₁, х₂, х₃, х₄ 0

Приводим поставленную задачу линейного  программирования к канонической форме (вводим в ограничения переменные x5, x6, x7 ) и решаем задачу симплекс-методом без учета целочисленности переменных.

Для этого перейдем от ограничений-неравенств к ограничениям- равенствам и запишем систему с учетом новых переменных в векторной форме:

x₁* P₁ + x₂* P₂ + x₃* P₃ + x₄* P₄ + x₅* P₅ + x₆* P₆ + x₇* P₇ = P₀

где

P₁= ; P₂= ; P₃= ; P₄= ; P₅= ; P₆= ; P₇= ; P₀= .

Поскольку среди векторов Р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