- •Нижегородский институт управления
- •Курсовая работа по применение методов математического программирования для выработки и принятия управленческих решений
- •Г.Нижний Новгород
- •Теоретическая часть
- •Линейное программирование
- •Динамическое программирование
- •Транспортная задача
- •Практическая часть
- •2.1 Задача линейного программирования
- •Задача динамического программирования
- •2.3 Транспортная задача
- •2.3 Транспортная задача
2.3 Транспортная задача
Задача. Фирма имеет три магазина розничной торговли, расположенные в разных районах города (А, В, С). Поставки продукции в эти магазины осуществляются с четырех складов (1,2,3,4). Найти оптимальные распределение поставок, при котором суммарные затраты на перевозку были бы минимальными.
Решение. Данные приведены в матрице ниже:
Номер склада |
Магазины |
Запасы | |||
А |
В |
С |
| ||
1 |
2 |
4 |
3 |
30 | |
2 |
2 |
5 |
2 |
25 | |
3 |
4 |
1 |
4 |
15 | |
4 |
5 |
3 |
5 |
30 | |
Спрос |
40 |
20 |
40 |
|
Проверим закрытость ТЗ (транспортной задачи):
40+20+40=30+25+15+30=100
Общий спрос равен сумме всех запасов, следовательно, ТЗ закрытая.
Произведем первоначальное распределение первоначально методом северо-западного угла и затем методом минимального элемента, чтобы увидеть разницу, как быстрее получить оптимальный план поставок.
Распределяем методом северо-западного угла. Получаем матрицу:
|
V1=2 |
V2=5 |
V3=8 |
Запас |
U1=0 |
30 2 |
4 |
3 |
30 |
U2=0 |
10 2 |
15 5 |
2 |
25 |
U3=-4 |
4 |
5 1 |
10 4 |
15 |
U4=-3 |
5 |
3 |
30 5 |
30 |
Спрос |
40 |
20 |
40 |
|
Воспользуемся следующей формулой для проверки количества занятый ячеек:
n+m-1, где:
n – количество потребителей,
m - количество поставщиков.
Применим это формулу для нашей задачи: 3+4-1=6. Вводить дополнительных нули не надо.
По заполненным клеткам ищем транспортные издержки:
T=30*2+10*2+15*5+5*1+10*4+30*5=350.
Теперь считаем потенциалы по формуле (i- производитель, j- потребитель) :
Ui+Vj=Cij.
Предполагаем, что U1=0, тогда:
U1+V1=2; U2+V1=2; U2+V2=5;
|
U3+V2=1; U3+V3=4 U4+V3=5.
|
Для проверки оптимальности данного плана находим оценки по незаполненным клеткам, используя формулу:
∆ij=Ui+Vj-Cij.
Применяем данную формулу:
∆12=0+5-4= 1; ∆13=0+8-3= 5; ∆23=0+8-2= 6;
|
∆31=-4+2-4= -6; ∆41=-3+2-5= -6 ∆42=-3+5-3= -1.
|
Условия оптимальности не выполняются.
Произведем распределение методом минимального элемента:
|
V1=2 |
V2=0 |
V3=2 |
Запас |
U1=0 |
30 2 |
4 |
3 |
30 |
U2=0 |
2 |
5 |
25 2 |
25 |
U3=1 |
4 |
15 1 |
4 |
15 |
U4=3 |
10 5 |
5 3 |
15 5 |
30 |
Спрос |
40 |
20 |
40 |
|
Рассчитываем транспортные издержки:
T=30*2+25*2+15*5+5*3+10*5+15==265.
Как мы может заметить, сразу издержки сократились. Возможно, найден оптимальный план поставок. Проверим это, найдя потенциалы и затем оценки.
Потенциалы находим и записываем в таблицу по вышеприведенной формуле.
Затем считаем оценки, получаем:
∆12=0+0-4= -4; ∆13=0+2-3= -1; ∆21=0+2-2= 0;
|
∆22=0+0-5= -5; ∆31=1+2-4= -1; ∆33=1+2-4= -1.
|
Как мы видим, оптимальный план поставок найден, все оценки или отрицательные или равны нулю.
Ответ: Фирма должна производить шесть перевозок следующим образом, для того, чтобы затраты на транспортировку товаров были минимальны в размере 265 ден. ед.:
от первого поставщика – 30 единиц продукции к первому потребителю,
второй поставщик 25 единиц к третьему,
третий поставщик 15 единиц второму потребителю,
четвертый поставщик производит три перевозки: 10 единиц первому потребителю, 5 единиц второму, и 15 единиц третьему потребителю.