Основы математического программирования (стр. 15 )

· В плюсовых клетках добавляем Х.

· Из минусовых клеток вычитаем Х.

· Все остальные клетки вне цикла остаются без изменения.

Получаем новую таблицу.

Склады	Магазины											ЗАПАС
B1	B2	B3	B4	B5
А1	1	0	3	4	2	15
5		10
А2	5	1	2	3	3	25
		2			8		15
А3	4	8	1	4	3	20
15			5
Потребность	20	12	5	8	15

Шаг 1. Нахождение потенциалов.

Найдем потенциалы поставщиков ui и потребителей vJ,

Примем u1 = 0.

c11 = u1 + v1 c12 = u1 + v2 c22 = u2 + v2 c24 = u2 + v4 c25 = u2 + v5 c31 = u3 + v1 c33 = u3 + v3

v1 = c11 – u1 = 1 – 0 = 1 v2 = c12 – u1 = 0 – 0 = 0 u2 = c22` – v2 = 1 – 0 = 1 v4 = c24 – u2 = 3 – 1 = 2 v5 = c25 – u2 = 3 – 1 = 2 u3 = c31 – v1 = 4 – 1 = 3 v3 = c33 – u3 = 1 – 3 = – 2

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

Найдем оценки свободных ячеек следующим образом:

D13 = (u1 + v3) – c13 = (0 – 2) – 3 = – 5

D14 = (u1 + v4) – c14 = (0 + 2) – 4 = – 2

D15 = (u1 + v5) – c15 = (0 + 2) – 2 = 0

D21 = (u2 + v1) – c21 = (1 + 1) – 5 = – 3

D23 = (u2 + v3) – c23 = (1 – 2) – 2 = – 3

D32 = (u3 + v2) – c32 = (3 – 0) – 8 = – 5

D34 = (u3 + v4) – c34 = (3 + 2) – 4 = 1

D35 = (u3 + v5) – c35 = (3 + 2) – 3 = 2

Среди оценок есть положительные, следовательно, решение не оптимальное.

Положительные оценки записываем в правый нижний угол – красный цвет.

Из положительных оценок выбираем максимальную. Это ячейка А3В5. Ее оценка D35 = 2.

Шаг 3. Улучшение плана.

Склады	Магазины												ЗАПАС
B1	B2	B3	B4	B5
А1	1	0	3	4	2	15
5		10
А2	5	1	2	3	3	25
		2			8		15
А3	4	8	1	4	3	20
15			5				2
Потребность	20	12	5	8	15

X = min(Xij). = 10,

Получаем новую таблицу.

Склады	Магазины												ЗАПАС
B1	B2	B3	B4	B5
А1	1	0	3	4	2	15
15
А2	5	1	2	3	3	25
		12			8		5
А3	4	8	1	4	3	20
5			5			10
Потребность	20	12	5	8	15

Шаг 1. Нахождение потенциалов.