Транспортная задача частный случай задачи линейного программирования

1.

Транспортная задача
частный случай
задачи линейного программирования

2. Построить экономико-математическую модель следующей задачи:

Имеются 3 поставщика и 4 потребителя.
Мощность поставщиков и спросы
потребителей, а также затраты на
перевозку единицы груза для каждой
пары «поставщик – потребитель»
сведены в таблицу поставок.
В каждой клетке стоит коэффициент
затрат – затраты на перевозку единицы
груза от соответствующего поставщика
к соответствующему потребителю.

3. Транспортная задача

Потребители и их спрос
Мощность
Поставщики поставщико
в
1
20
1
1
2
х11
60
1
2
100
х12
х21
120
х22
3
х14
2
х24
х23
7
х32
4
110
х13
5
3
х31
3
40
5
6
6
3
2
110
х33
4
х34

4. Транспортная задача

Найти объем перевозок для каждой пары
«поставщик – потребитель» так, чтобы:
мощность всех поставщиков были реализованы;
спросы всех потребителей удовлетворены;
суммарные затраты на перевозку были
минимальными.

5. Экономико-математическая модель задачи

f(х) = 1x11+2x12+5x13+…+7x33+4x34 → min
x11 x12 x13 x14 60
x21 x22 x23 x24 120
x x x x 100
33
34
31 32
x11 x21 х31 20
х12 x22 х32 110
х13 x23 х33 40
х14 x24 х34 110

6. Особенности экономико-математической модели транспортной задачи

Система ограничений есть система
уравнений, то есть транспортная задача
задана в канонической форме.
Коэффициенты при переменных системы
ограничений равны 1 или 0.
Каждая переменная входит в систему
ограничений 2 раза.

7. Два метода нахождения первоначального распределения поставок (опорного плана)

Метод северо-западного угла
Метод минимальной стоимости (или метод
наименьших затрат)

8. Важно помнить

Обязательно вычеркивается только один:
или поставщик, или потребитель.
Если на очередном шаге решения задачи совпали
потребность покупателя и мощность поставщика,
то одного (любого) вычеркиваем, а у второго
пишем в остатке 0.
На следующем шаге решения перевозим 0, тогда
эта клетка участвует в плане перевозок.

9. Важно помнить

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

10. Задача на недостаток

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

11. Задача на избыток

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

12.

Когда задача решена, цифры в строке
фиктивного поставщика показывают, какое
количество продукции, кто из потребителей не
получит, так как задача была на недостаток.
Когда задача решена, цифры в строке
фиктивного потребителя показывают, какое
количество продукции, у кого из поставщиков
останется, так как задача была на избыток.

13. СПАСИБО ЗА ВНИМАНИЕ! к.т.н., доц. Калашникова Т.В. tvkalash@tpu.ru