Линейное программирование

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

     Однородный  продукт, сосредоточенный в m пунктах производства (хранения) в количествах a1,a2,…..a_m единиц, необходимо распределить между n пунктами потребления, которым необходимо соответственно   b1,b2,….b_n единиц. Стоимость перевозки единицы продукта из i-го пункта отправления в j-ый пункт назначения равна c_ij и известна для всех маршрутов.

                  1 4 3 4   45

            C= 3 4 2 2 A=  50 B= (31,40,44,20)

                  4 5 6 3   53

A - вектор объемов производства

B - вектор потребностей потребителей

C - матрица транспортных издержек

      Найти: оптимальное решение транспортной  задачи (необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными) 

Решение:

Обозначим через x_ij количество груза, планируемого к перевозке от i-го поставщика j-му потребителю.

Задача имеет решение при наличие баланса производства и потребления:

       - закрытая модель транспортной задачи

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

найти план перевозок 

Х*=(x_ij),   i= 1,m;   j = 1,n   

минимизирующий  общую стоимость всех перевозок

R= c_ij*x_ij  min

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

Xij = a_i , i= 1,m 

и любому потребителю доставляется необходимое количество груза:

Xij = b_j , j= 1,n 

причем  по смыслу задачи 

X₁₁>0,….,X_mn>0

Так как  общий объем производства 45+50+53=148 (ед.)  больше суммарных запросов всех потребителей  31+40+44+20 = 135(ед.), имеем открытую модель транспортной задачи. Для сведения задачи к замкнутой модели введем фиктивный пункт потребления с потребностью b5=13(ед.). Будем считать, что тарифы на перевозку в этот пункт = 0.

Транспортная  задача решается методом потенциалов. Первое базисное допустимое решение строим по правилу "северо-западного угла, при этом максимально загружаем северо-западную клетку с координатами (1;1)

X₁₁ = min (a₁;b₁) = b₁ 

                                                                                                         Таблица 1

 

Принимаем Р1 = 0 и из отношения P = C - Q находим все последующие значения P и Q. 

P1+Q1-C11=0 0 + Q1 – 1 = 0 Q1=1

P1+Q2-C12=0 0 + Q2 – 4 = 0 Q2=4

P2+Q2-C22=0 P2 + 4  – 4 = 0   P2=0

P2+Q3-C23=0 0 + Q3 – 2 = 0 Q3=2

P3+Q3-C33=0 P3+ 2  – 6 = 0   P3=4

P3+Q4-C34=0 4 + Q4 – 3 = 0 Q4=-1

P3+Q5-C35=0 4 + Q5 – 0 = 0 Q5=-4 

Затем по формуле ∆ij = Pi + Qj - Cij вычисляем оценки всех свободных клеток;

Для найденной  свободной клетки 32 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Производим перераспределение поставок вдоль цикла пересчета. Продолжаем процесс до тех пор, пока не придем к таблице, для которой все ∆ij>0 

Находим наибольшую положительную оценку max(Δij>0)= 3 = Δ32

Цикл перерасчета: 

26-λ     24+λ                     6 4 4 

     λ      20-λ                     20 

                λ_max = 20

           

  Получаем второе базисное решение:

                                                                                                         Таблица2

 

P1+Q1-C11=0 0 + Q1 – 1 = 0 Q1=1 

P1+Q2-C12=0 0 + Q2 – 4 = 0  Q2=4

P2+Q2-C22=0 P2 + 4 – 4 = 0  P2=0 

P2+Q3-C23=0 0 + Q3 – 2 = 0 Q3=2

P3+Q2-C32=0 P3 + 4 – 5  = 0 P3=1

P3+Q4-C34=0 1 + Q4 – 3 = 0 Q4=2

P3+Q5-C35=0 1 + Q5 – 0 = 0 Q5=-1 

 

В данной таблице все ∆ij 0,  i = 1,m; j = 1,n .