Пример решения задачи. Решение транспортной задачи

Поставщики товара - оптовые коммерческие предприятия имеют запасы товаров соответственно в количестве и розничные торговые предприятия -подали заявки на закупку товаров в объемах соответственно: . Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы . Найти такой план перевозки груза от поставщиков к потребителям, чтобы совокупные затраты на перевозку были минимальными.

Решение:

Потребители

Поставщики

Запасы товаров,

7

20

3

15

225

3

14

10

20

250

15

25

11

19

125

11

12

18

6

100

Заявки на закупку товаров,

120

150

110

235


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

Ограничения для поставщиков:

Ограничения для потребителей:

Объем суммарных поставок любого поставщика к потребителю не может быть отрицательным числом, поэтому справедливы ограничения:

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

В нашем случае:

Модель транспортной задачи открытая. Вводим фиктивного потребителя, которому требуется 85 единиц груза.

Заполняем таблицу по правилу минимального элемента.

Просматривая таблицу замечаем, что наименьшие затраты соответствуют маршруту , поэтому в клетку помещаем . В этом случае 5-й столбец в расчет не принимается. Просматриваем оставшиеся таблицы клетки. Наименьшие тарифы имеют клетки и

Далее действуя по аналогичной схеме:

Число занятых клеток должно быть .

Решать задачу будем методом потенциалов. Потенциал 1-й строки принимаем равным нулю. После этого мы можем вычислить остальные потенциалы (если известны потенциал и тариф занятой клетки, то из соотношения легко определить неизвестный потенциал).

Найдем оценки свободных клеток:

S ( 1, 1)= 7-( 0+ 10)= -3

S ( 1, 2)= 20-( 0+ 21)= -1

S ( 2, 3)= 10-(-7+ 3)= 14

S ( 2, 4)= 20-(-7+ 15)= 12

S ( 2, 5)= 0-(-7+ 0)= 7

S ( 3, 1)= 15-( 4+ 10)= 1

S ( 3, 3)= 11-( 4+ 3)= 4

S ( 3, 5)= 0-( 4+ 0)= -4

S ( 4, 1)= 11-(-9+ 10)= 10

S ( 4, 2)= 12-(-9+ 21)= 0

S ( 4, 3)= 18-(-9+ 3)= 24

S ( 4, 5)= 0-(-9+ 0)= 9


Для клетки ( 3, 5) строим цикл.

Найдем оценки свободных клеток:

S ( 1, 1)= 7-( 0+ 10)= -3

S ( 1, 2)= 20-( 0+ 21)= -1

S ( 1, 5)= 0-( 0-4)= 4

S ( 2, 3)= 10-(-7+ 3)= 14

S ( 2, 4)= 20-(-7+ 15)= 12

S ( 2, 5)= 0-(-7-4)= 11

S ( 3, 1)= 15-( 4+ 10)= 1

S ( 3, 3)= 11-( 4+ 3)= 4

S ( 4, 1)= 11-(-9+ 10)= 10

S ( 4, 2)= 12-(-9+ 21)= 0

S ( 4, 3)= 18-(-9+ 3)= 24

S ( 4, 5)= 0-(-9-4)= 13


Для клетки ( 1, 1) строим цикл.

Найдем оценки свободных клеток:

S ( 1, 2)= 20-( 0+ 18)= 2

S ( 1, 5)= 0-( 0-4)= 4

S ( 2, 3)= 10-(-4+ 3)= 11

S ( 2, 4)= 20-(-4+ 15)= 9

S ( 2, 5)= 0-(-4-4)= 8

S ( 3, 1)= 15-( 4+ 7)= 4

S ( 3, 2)= 25-( 4+ 18)= 3

S ( 3, 3)= 11-( 4+ 3)= 4

S ( 4, 1)= 11-(-9+ 7)= 13

S ( 4, 2)= 12-(-9+ 18)= 3

S ( 4, 3)= 18-(-9+ 3)= 24

S ( 4, 5)= 0-(-9-4)= 13


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

Минимальные транспортные издержки оптимального плана:

При реализации оптимального плана у поставщика останется нереализованный товар в размере 85 ед.

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

Бесплатное решение задач по линейному программированиюГлавная : Примеры решения : Транспортная задача

Еще примеры решения задач






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

@mathminsk.com 2008-2015 Минск