Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


ћетод решени€ транспортной задачи




«адача (3.1.1), (3.1.6), (3.1.7), (3.1.4) €вл€етс€ задачей Ћѕ. ¬ силу услови€ (3.1.5) одно из уравнений (3.1.6), (3.1.7) оказываетс€ зависимым, т.е. транспортна€ модель содержит независимых уравнений. ѕоэтому начальное Ѕƒ– должно иметь базисных переменных. ќпишем основные шаги алгоритма решени€ “«.

1) Ќайти начальное Ѕƒ–.

2) Ќайти из числа небазисных переменных вводимую в базис. ≈сли все небазисные переменные удовлетвор€ют условию оптимальности (симплекс-метода), закончить вычислени€; иначе перейти на п.3.

3)¬ыбрать выводимую из базиса переменную (использу€ условие допустимости) из числа переменных текущего базиса. «атем найти новое базисное решение. ѕерейти на п.2.

»сходные данные “« записывают в виде таблицы:

ѕункты пункты назначени€ производство
ќтправлени€ 1   j   n  
1    
             
i      
             
m      
ѕотребление      

 

ћетод решени€ “« рассмотрим на примере. ¬ таблицу внесем данные “«: , , .

 

пункты ѕункты назначени€
ќтправлени€    
  4 - 10 1 +  
  3 + 2 2 -  
       

 

ќпределение Ѕƒ–. Ќачальное Ѕƒ– можно найти, например, по правилу северо-западного угла.

1. ќпределить перевозку дл€ левого верхнего угла, определ€емую величиной исчерпани€ либо пункта потреблени€, либо пункта производства.

2. ¬ зависимости от исчерпани€ пункта производства (потреблени€) удалить строку (столбец) из таблицы, задав ненулевыми объемы перевозок удал€емых клеток. ¬ случае исчерпани€ как пункта потреблени€, так и пункта производства удал€етс€ произвольно либо строка, либо столбец, а на следующем шаге будет получена нулева€ базисна€ переменна€.

3. ѕовторить действи€ дл€ оставшейс€ части таблицы.

¬ таблицу внос€тс€ значени€ объемов перевозок только дл€ базисных переменных.

¬ычисление критери€ оптимальности. ¬ “« вычисление критери€ оптимальности (2.8.1) осуществл€етс€ по схеме (2.8.2), а коэффициенты p вычисл€ютс€ посредством решени€ системы (2.8.3).

ќбозначим , , коэффициенты соответственно дл€ уравнений (3.1.7), (3.1.6). ѕоскольку одно из уравнений (3.1.6), (3.1.7) лишнее, произвольно полагают одно из значений либо заданным, например, . ”равнени€ (2.8.3) дл€ базисных переменных приобретают вид

. (3.2.1)

”словие оптимальности (2.4.7) в форме (2.8.2), с учетом представлени€ вектора записываютс€ в виде

(3.2.2)

ƒл€ ввода в базис выбираетс€ переменна€ xij с наибольшим положительным значением величины . –ешение получено, если выполн€ютс€ неравенства (3.2.2).

ƒл€ таблицы запишем уравнени€ (3.2.1) и их решение, полага€ .

,


¬ычислим значени€ критери€ дл€ небазисных переменных

ќтсюда следует, что переменную x13 следует вводить в базис.

¬ыбор переменной, выводимой из базиса. ¬ симплекс-методе при вводе переменной в базис измен€ютс€ только базисные переменные, одна, или несколько из которых обращаютс€ в нуль. ¬ “« строитс€ замкнутый цикл, состо€щий из горизонтальных и вертикальных линий, узлы которого наход€тс€ в клетках таблицы, соответствующих базисным переменным и переменной, вводимой в базис. ƒл€ каждого базисного решени€ и соответствующей небазисной переменной можно построить лишь один цикл.

Ќебазисна€ переменна€ цикла будет возрастать. ƒл€ сохранени€ объемов перевозок в соседних к ней узлах цикла клетках значени€ должны убывать.  летки, в которых переменные убывают, помечаютс€ знаком С-С, в других - знаком С+Т.

ќбща€ величина убывани€ определ€етс€ минимальным значением базисных переменных, которые убывают. ќбозначим эту величину . ѕосле определени€ величины производитс€ изменение переменных в соответствии со знаком, поставленным при обходе цикла. ѕосле этого одна из нулевых базисных переменных удал€етс€ из базиса. –езультаты свод€тс€ в новую таблицу:

 

   
     
     

 

ѕроцесс заканчиваетс€, когда будут выполнены услови€ (3.2.2).





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-02-12; ћы поможем в написании ваших работ!; просмотров: 543 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

“ак просто быть добрым - нужно только представить себ€ на месте другого человека прежде, чем начать его судить. © ћарлен ƒитрих
==> читать все изречени€...

2099 - | 1853 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.016 с.