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

Проверяем выполнение необходимого условия и достаточного условия существования решения.

Находим суммарные запасы поставщика и запросы потребителей. (900 и 1100).

Задача с неправильным балансом. Вводим фиктивного поставщика с запасами а4 = 1100 – 900 = 200

Составляем начальное опорное решение методом минимальной стоимости. Получаем таблицу.

bj ai	200	300	300	300
100	100 1	5	6	1
300	100 2	6	7	200 2
500	3	300 7	200 8	М
200	0	0	100 0	100 0

Полученное решение имеет m + n – 1 = 7 базисных переменных. Вычислим значение целевой функции.

Z(x) = 4400.

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

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

Примем u1 = 0.

c11 = u1 + v1 c21 = u2 + v1 c24 = u2 + v4 c32 = u3 + v2 c33 = u3 + v3 c43 = u4 + v3 c44 = u4 + v4

v1 = c11 – u1 = 1 – 0 = 1 u2 = c21 – v1 = 2 – 1 = 1 v4 = c24` – u2 = 2 – 1 = 1 v2 = c32 – u3 = 7 – 7 = 0 u3 = c33 – v3 = 8 – 1 = 7 v3 = c43 – u4 = 0 + 1 = 1 u4 = c44 – v4 = 0 – 1 = – 1

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

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

D12 = (u1 + v2) – c12 = (0 + 0) – 5 = – 5

D13 = (u1 + v3) – c13 = (0 + 1) – 6 = – 5

D14 = (u1 + v4) – c14 = (0 + 1) – 1 = 0

D22 = (u2 + v2) – c22 = (1 + 0) – 6 = – 5

D23 = (u2 + v3) – c23 = (1 + 1) – 7 = – 5

D31 = (u3 + v1) – c31 = (7 + 1) – 3 = 5

D34 = (u3 + v4) – c34 = (7 + 1) – M

D41 = (u4 + v1) – c41 = (– 1 + 1) – 0 = 0

D42 = (u4 + v2) – c42 = (– 1 + 0) – 0 = – 1

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

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

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

bj ai	200	300	300	300
100	100 1	5	6	1
300	100 2	6	7	200 2
500	5	3	300 7	200 8	М
200	0	0	100 0	100 0

Определяем величину груза для перераспределения по циклу.

Q = min{100, 200, 100} = 100

bj ai	200	300	300	300
100	100 1	5	6	1
300	0 2	6	7	300 2
500	100 3	300 7	100 8	М
200	0	0	200 0	0

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

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

Примем u1 = 0.

c11 = u1 + v1 c21 = u2 + v1 c24 = u2 + v4 c31 = u3 + v1 c32 = u3 + v2 c33 = u3 + v3 c43 = u4 + v3

v1 = c11 – u1 = 1 – 0 = 1 u2 = c21 – v1 = 2 – 1 = 1 v4 = c24` – u2 = 2 – 1 = 1 u3 = c31 – v1 =3 – 1 = 2 v2 = c32 – u3 = 7 – 2 = 5 v3 = c33 – u3 = 8 – 2 = 6 u4 = c43 – v3 = 0 – 6 = – 6

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

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

D12 = (u1 + v2) – c12 = (0 + 5) – 5 = 0

D13 = (u1 + v3) – c13 = (0 + 6) – 6 = 0

D14 = (u1 + v4) – c14 = (0 + 1) – 1 = 0

D22 = (u2 + v2) – c22 = (1 + 5) – 6 = 0

D23 = (u2 + v3) – c23 = (1 + 6) – 7 = 0

D34 = (u3 + v4) – c34 = (2 + 1) – M < 0

D41 = (u4 + v1) – c41 = (– 6 + 1) – 0 = – 5

D42 = (u4 + v2) – c42 = (– 6 + 5) – 0 = – 1

D44 = (u4 + v4) – c44 = (– 6 + 1) – 0 = – 5

Решение оптимальное, т. к. нет положительных оценок. Запишем оптимальное решение. Для этого увеличим объем перевозки х12 на 100 единиц и объединим объемы перевозок 4-ого и 1-ого потребителя

bj ai	500	400	300
200	100 1	100 5	6
300	300 2	6	7
500	100 3	300 7	100 8

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