Принятие решений о прикреплении оптовых потребителей к поставщикам

Транспортная задача
задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения. Является задачей линейного программирования специального вида.

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

Пример

Для решения задачи необходимо выполнение следующего условия:
cуммарные запасы продукции у поставщиков должны равняться суммарной потребности потребителей
30+40+20= 90
20+30+30+10=90
При несовпадении сумм вводим фиктивного поставщика/потребителя с недостающим числом

Шаг 1
Первая ячейка — с которой начинается распределение —будет «северо-западная» ячейка в левом верхнем углу таблицы X11 (1-й поставщик, 1-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя. Это 20. Поскольку спрос 1-го потребителя полностью удовлетворен, ячейки соответствующего столбца заполняться больше не будут, для ясности закрашиваем 1-й столбец.

Шаг 2
Переходим в следующую «северо-западную» ячейку. Этой ячейкой будетX12 (1-й поставщик, 2-й потребитель). Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя. Уменьшаем оставшиеся не распределенными объемы поставки и потребления в строке и столбце на 10 кг. Запасы 1-го поставщика (в 1-й — верхней — строке) теперь исчерпаны, окрашиваем эту строку в серый цвет (распределение по этой строке завершено).

Шаг 3
Переходим в следующую «северо-западную» ячейку, не считая окрашенной. Вписываем в эту ячейку максимальный объем, который позволяет запас поставщика и спрос потребителя.

4 шаг

Шаг 5. Распределение оставшихся запасов по поставщикам.
Z=40+30+40+100+20=60=290

Метод минимального элемента
правило минимальных затрат — алгоритм получения допустимого начального решения транспортной задачи . В отличие от более простого метода северо-западного угла, в этом методе расчетчик записывает отгрузки, в первую очередь, в те ячейки, где тариф на перевозку груза минимален.

Шаг 1
Находим ячейку с минимальной ценой и вписываем в нее максимально возможный объем, который позволяет запас поставщика и спрос потребителя

Шаг 2

Шаг 3
Z=20*4+2*30+2*30+10=210

Задача

Решение
Запасы поставщиков: 200 + 180 + 190 = 570 единиц продукции.
Потребность потребителей: 150 + 180 + 150 + 140 = 620 единиц продукции.
Разница в 50 единиц продукции.
Вводим фиктивного поставщика

Z=150*1 + 50*2 + 150*4 + 30*8 + 180*2 + 10*6 + 50*0 = 1510

Вопросы
1. Перечислите методы решения транспортной задачи
2. Что делать если спрос и предложение не совпадают?
3. Какой метод легче всего по вашему мнению?
4. Как найти минимальную стоимость перевозок?
5. Что значит замкнутая модель?