Метод потенциалов решения транспортной задачи. Среди задач линейного программирования особое место занимает транспортная задача

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

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

Традиционная постановка транспортной задачи такова:

Рис. 3

Имеются m поставщиков и n потребителей. У поставщиков сосредоточен однородный груз в количестве a₁, a₂,…..a_m.

Спрос потребителей на груз: в₁, в₂,….в_n.

Известны стоимости (тарифы) с_ij на перевозку единицы груза от i-го поставщика к j- му потребителю.

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

1. вывести весь груз поставщиков

2. удовлетворить весь спрос потребителей

3. минимизировать суммарные затраты на перевозку.

Построение математической модели:

Пусть х_{ij –} количество груза, перевозимого от i-го исх. пункта к j-му пункту потребления.

х₁₁ + х₁₂+ ….+х_1n= а₁

х₂₁ + х₂₂+ ….+х_2n= а₂ →все грузы должны быть вывезены

……………………..

х_m1 + х_m2+ ….+х_mn= а_m

х₁₁ + х₂₁+ ….+х_m1= b₁

х₁₂ + х₂₂+ ….+х_m2= b_{2 →} весь спрос удовлетворен

…………………….

х_1n + х_2n+ ….+х_mn= b_n

Замечание:

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

Разберем этот метод на конкретном примере:

На трех железнодорожных станциях сосредоточено топливо для пяти заводов. Необходимо составить оптимальный план перевозок топлива. Исходные данные заданы в транспортной таблице стандартного вида:

Потр.						ЗАПАСЫ
Пост.
СПРОС

Задача закрытая (почему?).

1. Нахождение начального опорного плана (угловой точки).

Используется метод минимальной стоимости. Его суть:

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

Потр.						ЗАПАСЫ
Пост.
СПРОС

б) правило: “там, где 0 вычеркиваем”

в) среди всех невычеркнутых клеток вновь находим клетку с минимальной стоимостью и вновь повторяем алгоритм.

в) контроль: общее число занятых клеток равно m + n- 1

г) F = 20*7 + 80*2+ 100*4 + 30*6 + 70*4 + 150*2 + 50*5= 1710

Дата добавления: 2014-12-27