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

 

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

 

	b1	b2	b3	b4
a1	5	7	3	1	u1 = 4
a2	– 6	2	5	6	u2 = 6
a3	0	6	0	2	u3 = 2
	v1 = 1	v2 = – 4	v3 = – 1	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,3 – U₂ = 5 – 6 = – 1;

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

6) U₁ = P_1,3 – V₃ = 3 – (– 1) = 4;

7) V₁ = P_1,1 – U₁ = 5 – 4 = 1.

 

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

S₁₄ = P₁₄ – U₁ – V₄  = 5 – 4 – 0 = 1

S₂₁ = P₂₁ – U₂ – V₁ = 1 – 6 – 1 = – 6

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

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

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

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

 

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

 

Ячейка а₂,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₀= .