Контрольная работа: Метод потенциалов для решения транспортной задачи

Числа на пересичении стоимости перевозок и обозначаются с_ij .

Математическая постановка данной задачи имеет вид: найти минимум целевой функции (показателя эффективности)

Z= 7х₁₁ + 6х₁₂ + 4х₁₃ + Зх₂₁ + 8х₂₂ + 5х₂₃ + +2х₃₁ +3х₃₂ + 7х₃₃ при ограничениях:

nnn

Σx_{1 j} =120; Σx_{2 j} =100; Σx_{3 j} =80;

j=ij=ij=i

mmm

Σx_{i 1} =90; Σx_{i 1} =90; Σx_{i 1} =120; х_ij >0

i=li=li=l

Транспортная задача относится к классу задач линейного программирования. Решение таких задач обычно связано с получением опорного (допустимого) плана и последующим его улучшением.

Опорный план может быть получен различными методами. Рассмотрим метод минимального элемента, или метод наименьших.

В соответствии с методом наименьших затрат выберем в таблице клетку, имеющую наименьший показатель затрат, т. е. клетку (3,1). Произведем поставку в эту клетку, равную 80 единицам, поскольку первому потребителю требуется .90 единиц, а у третьего поставщика в наличии лишь 80 единиц. Первому потребителю необходимо еще 10 единиц товара. Он может получить их или от первого, или от второго поставщика. Так как показатель затрат в клетке (2,1) меньше, чем в клетке (1,1), то записываем 10 единиц в клетку (2,1).

Второй поставщик, отдав 10 единиц, будет располагать 90 единицами. Их можно направить второму или третьему потребителю. В связи с тем, что показатель затрат в клетке (2, 3) меньше, чем в клетке (2, 2), направим их третьему потребителю. Недостающие 30 единиц третий потребитель получит от первого поставщика.

Оставшиеся у первого поставщика 90 единиц запишем в клетку (1, 2) и, тем самым, удовлетворим спрос второго потребителя.

На этом распределение можно считать законченным.

Поставщики	Возможности поставщиков	Потребители и их спрос
		1	2	3
		90	90	120
1	120	7	6 90	4 30
2	100	3 10	8	5 90
3	80	2 80	3	7

Получив опорный план, необходимо оценить соответствующую ему стоимость перевозок (показатель эффективности или целевую функцию). Для плана, полученного методом наименьших затрат, Z = 1300 ед.

Следующим этапом решения задачи, независимо от того, каким методом был найден опорный план, является последовательное его улучшение до получения оптимального распределения. С этой целью каждому поставщику товаров поставим в соответствие потенциалы А₁ , А₂ , А₃ и запишем их в дополнительном столбце, а каждому потребителю – потенциалы B₁ , В₂ , В₃ , которые запишем в дополнительной строке. Один из потенциалов, например A₁ приравняем к нулю, а остальные найдем с использованием:

А_ij = А_i + В_j