Задача№18

На двух складах А и В имеется соответственно 50 и 40 тн. груза. Требуется спланировать перевозки к трем потребителям (С, D и E) так, чтобы потребитель С получил 50 тн., D–10 тн., E–30 тн., а затраты на перевозку были минимальными.

Решение: Составим математическую модель этой задачи.

Математическая модель для решения транспортной задачи

Таблица 1.

Потреб Постав	С	D	Е	Итог
А
В
Итог

Найдем множество решений системы:

(15)

, то есть все значения должны быть неотрицательными.

Найдем минимальное значение целевой функции

(16)

Составим методом северо-западного угла первое распределение поставок, начиная с заполнения верхней левой (северо-западной) клетки таблицы. Примем объем перевозки со склада А к потребителю С максимально возможным, исходя из условий задачи, равным 50. Потребитель С полностью удовлетворил свою потребность, соответственно столбец С в табл. 2 можно исключить из дальнейшего рассмотрения.

В таблице поставок найдем новый северо-западный угол – это клетка AD и укажем в ней максимально возможное значение, которое рассчитывается следующим образом: со склада А уже перевезено 30 тн. груза, значит, остаток составляет 50-10=40 тн. Весь груз со склада А перевезен потребителям, и первая строка таблицы поставок исключается из дальнейшего рассмотрения. Потребитель D полностью удовлетворил свою потребность в грузе, и столбец D в табл.2 можно исключить из дальнейшего рассмотрения. В оставшейся части таблицы найдем новый северо-западный угол – это клетка ВЕ и укажем в ней максимально возможное значение (30 тн.). Итак, табл.2 является исходным распределением поставок: .

Первое распределение поставок

Таблица 2.

Получим следующее значение целевой функции:

F=3*50+2*0+0+3*0+5*10+6*30=380 (руб.).

Проверим полученный результат на оптимальность.

В этой задаче два поставщика (m =2) и три потребителя (n =3). Вычисляем значение выражения для нашей задачи: m+n –1=4.

Из построенной таблицы видно, что число занятых мест равно 3, т.е. меньше значения m+n –1.

Если число занятых клеток после некоторого распределения поставок (совсем необязательно, чтобы это происходило после первого распределения) окажется меньше, чем m+n –1, то с помощью условных поставок, равных нулю, надо заполнить недостающие для выполнения условия клетки, а затем решать как обычно.

Таким образом, по полученному оптимальному плану надо 10 тн. груза со склада А отправить потребителям С и D и 30 тн. – потребителю Е. Со склада В отправляется 40 тн. потребителю С.

Проверка результатов на оптимальность

Таблица 3.

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

F=3*10+2*10+30+3*40+5*0+6*0=200 (руб.).

Поиск по сайту: