Пример 2.8.2

Оглавление | Назад| Глоссарий понятий

Выпуск продукции трех заводов А1 , А2 , А3 составляет соответственно 260, 240 и 300 т. Потребности четырех потребителей В1 , В, В3 , В4 равны соответственно 300, 200, 250 и 100 т. Известно, что:

  1. Продукция завода А1 не требуется пункту В4 .
  2. С завода А3 потребителю В2 должно быть доставлено груза не более 50 т.

Стоимость перевозки одной тонны продукции из Аi в Bj задана матрицей

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

Решение. Заметим, что и поэтому вводим фиктивного поставщика А4 с запасами a4 = 50 и нулевыми тарифами (4-ая строка). Получим закрытую модель ТЗ. Заполняем распределительную таблицу (табл. 2.14) в следующем порядке. В клетку А1 B4 записываем число М (блокируем), тем самым выполнив первое условие задачи. Далее в столбце B2 записываем потребности b2 = 50, остальные b*ij = 150 заносим в дополнительный столбец B*2 . Все тарифы в нем такие же, как и в B2 , лишь в клетке A3 B*2 ставим число М. Далее по принципу минимальной стоимости заполняем клетки таблицы.

Таблица 2.15

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

X= проверяем его на оптимальность, для чего составляем систему уравнений потенциалов:

u1 + v1 = 3, u4 + v3 = 0, Получаем u3 = 0, найдём: v1 = 4, u1 = - 1,
u1 + v2 = 4, u4 + v4 = 0.   v2 = 3, u2 = - 4,
u2 + v3 = 2,   v3 = 6, u3 = 0,
u3 + v1 = 4,   v4 = 6, u4 = - 6.
u3 + v2 = 3,    
u3 + v4 = 6,    

Проверив свободные клетки, убеждаемся, что для них выполнятся условие (2.23) теоремы 5, следовательно, план X является оптимальным и Zmin = 2680 (ед.).

Оглавление | Назад| Глоссарий понятий

Hosted by uCoz