Решение задач линейного программирования

Решение не является оптимальным, потому что  ∆5<0, следовательно, его можно улучшить.

Ключевым столбцом является столбец A5, т.к.  min ∆_k =-4. Ключевой строкой является строка x4, т.к min Ɵ =1. Ключевой элемент равен 1.

Заполняем следующую симплексную таблицу.

а) переписываем ключевую строку, разделив ее на ключевой элемент;

б) заполняем базисные столбцы;

в) остальные коэффициенты таблицы находим по правилу «прямоугольника»

Правило «прямоугольника» заключается в  следующем: 

новыйэл.=старыйэл.-   соотв.эл.кл.столбца×соответств.эл.кл.строки

                                              ключевой элемент 
 

  новыйэл.=10- =9                                          

 новыйэл.=2- =2-(-1)=3 

новыйэл.=0- =-1 

новыйэл.=-4- =-4-(-3)=-1 

новыйэл.=5- =5+1=6

новыйэл.=0- =0+1=1 

Считаем ∆_k:

∆₀= × -(-68)=4+68=72

∆₁=   × -0=0

∆₂ =   × -0=0

∆₃= × -(-17)= -12-(-17)=5

  ∆₄= × -0=4

∆₅=    × -0=0

        

Т.к  все ∆_k ≥ 0, то решение является оптимальным.

Ответ: max Z(Х) = 72 при Х = (9; 3; 0). 

1.5 Вывод 

      Максимальная  прибыль в размере 72 тыс. руб. достигается, если производить 9 станков I вида, 3 станка II вида и не производить станки III вида. При этом трудовые ресурсы используются полностью, сырья расходуется 15 единиц, а накладные ресурсы требуются в размере 15 единиц.    

 

Глава 2 Транспортная задача линейного  программирования 

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

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

      Имеется однородный груз у m-поставщиков в количестве m: a₁;a₂;…;a_m. Этот груз требуется n потребителям в размерах b₁;b₂;…;b_n. Известно С_ij(i=1,m;j=1,n) стоимость перевозки 1 единицы груза от i-го поставщика к j-му потребителю, либо время на перевозку 1 единицы груза.

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

     1)все запасы поставщиков будут вывезены полностью;

     2) все запросы потребителей удовлетворены полностью;

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

Условия транспортной задачи записываются в виде таблицы:

 

1) Выбираем  переменные задачи:

Пусть x_ij- количество едениц груза перевозимого от каждого поставщика каждому потребителю. х_ij(i= ;j= ) x_ij 0

2) Составляем систему ограничений: система будет состоять из уравнений т.к:

а) все запасы должны быть вывезены полностью

 

б) все  запросы должны быть удовлетворены  полностью:

3) Задаем  целевую функцию.

Цель  задачи: перевести груз с минимальными затратами.

Z(x)=C₁₁x₁₁+C₁₂x₁₂+…+C_mnx_mn min

Таким образом математическая модель имеет  вид:

Составить такой план перевоза Х= удовлетворяющий системе ограничений:

x_ij

Транспортные  задачи делятся на две группы:

1) задачи  закрытого типа или с правильным  балансом:

    

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

а) для разрешимости задачи вводят фиктивного потребителя с запросами b_n+1= . Стоимости перевозок от каждого поставщика равна нулю.

б) общий запас меньше требуемой величины. Вводят фиктивного поставщика с запасами: a_m+1=

C_i(m+1)=0 
 

2.2 Особенности транспортной задачи ограничениями на пропускную способность 

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l и потребителю с номером k. Возможны ограничения двух типов: 1)x_lk≥a; 2)x_lk≤b, где a и b- постоянные величины.

1. Если x_lk≥ a, то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы k-го потребителя на величину a (зарезервировать перевозку x_lk=а). В полученном оптимальном решении следует увеличить объем перевозки x_lk на величину а.
2. Если x_lk≤b, то необходимо вместо k-го потребителя с запросами b_k ввести двух других потребителей. Один из них с номером k должен иметь запросы b^,_k=b, а другои с номером n+1- запросы b_n+!=b_k-b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости c_l(n+1), которая принимается равной сколь угодно большому числу M (M<< 1). После получения оптимального решения величины грузов, перевозимых к (n+1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как c_l(n+1)=M- самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l,n+1) останется пустой (x_l(n+1)=0) и оббъем перевозки x_lk не превзойдет b.

  

2.3 Алгоритм решения транспортной задачи 

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

2) Строят начальное опорное решение. Либо методом «северо-западного угла» либо методом минимальной стоимости. Проверяют правильность заполнения клеток по количеству: их должно быть m+n-1. Проверяется линейная независимость с помощью метода вычеркивания.

3) Проверяют  решение на оптимальность с  помощью метода потенциалов: если решение оптимальное- записывают ответ.

4) Если  решение не оптимальное, то  переходят к новому опорному  решению с помощью построения  циклов и возвращаются к пункту 3.  
 

2.4 Методы построения начального опорного решения 

1) Метод «северо-западного угла»

     Распределение груза начинается с верхней клетки таблицы. Выбирают минимальное из значений: x₁₁=min{a₁;b₁}. При этом из дальнейшего рассмотрения исключается либо поставщик, либо потребитель. Из оставшихся клеток таблицы выбирают клетку в которую записывают груз величиной:

 и.т.д пока весь груз не будет распределен.

2) Метод минимальной стоимости

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

2.5. Метод потенциалов 

     Для каждого поставщика и потребителя  находят потенциал. Для этого  составляют систему уравнений U_i+V_i=C_ij для каждой заполненной решением клетки таблицы.

     В системе будет (m+n-1) уравнений с (m+n) неизвестными т.е неизвестных на 1 больше, чем уравнений. Такая система имеет бесконечное множество решений, поэтому для ее решения одной из переменных дают конкретное значение (обычно U₁=0 – система будет иметь одно единственное решение).

     Потенциалы  записывают рядом с таблицей. Для  всех не заполненных решением клеток таблицы вычисляют оценку ∆_ij=U_i+V_j-C_ij .

Если  все ∆_ij≤0, то решение оптимальное. Если хотябы одна ∆_ij>0, то решение не оптимальное и его можно улучшить. 

2.6. Переход от первого опорного решения к другому 

Переход к новому опорному решению осуществляется с помощью цикла.

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