Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


ћетод п≥вн≥чно-зах≥дного кута




Ќе звертаючи уваги на варт≥сть перевозок, починають задовольн€ть потреби за рахунок .  л≥тинку заповнюють величиною . ќстачу перенос€ть в кл≥тинку , €кщо або в , €кщо . ѕроцес продовжуЇмо допоки вс≥ р€дки ≥ стовпц≥ не будуть заповненими. ѕокажемо метод на приклад≥ такоњ задач≥:

 

 

¬ таблиц≥ заповнено 8 кл≥тинок. «начить план не вироджений.

“ак €к в процес≥ вартост≥ перевозок не враховувались, то зрозум≥ло, що план далекий в≥д оптимального:

ћетод найменшоњ вартост≥

ћетод пол€гаЇ в тому, що ≥з ус≥Їњ таблиц≥ вибирають кл≥тинку з найменшою варт≥стю перевозок ≥ розм≥щують в н≥й менше ≥з або . ѕ≥сл€ цього ≥з подальшого розгл€ду виключають або р€док, €кщо використан≥ запаси, або стовпець, €кщо забезпечений споживач. якщо , виключають ≥ р€док ≥ стовпець.

≤з частини таблиц≥, що залишилась знову вибирають найменшу варт≥сть ≥ так продовжують до повного заповненн€ таблиц≥:

 

 

.

як бачимо, план ближчий до оптимального.

 

ћетод подв≥йноњ переваги

якщо таблиц€ велика, то реал≥зац≥€ попереднього методу ускладнюЇтьс€. ¬ цьому випадку використовують метод подв≥йноњ переваги. ¬ кожному стовпц≥ ставл€ть м≥тку в кл≥тинку з найменшою варт≥стю. “е ж саме робл€ть ≥ по р€дкам. ¬ кл≥тинки з двома м≥тками розм≥щують по можливост≥ б≥льш≥ перевозки, кожного разу виключаючи ≥з розгл€ду в≥дпов≥дн≥ р€дки ≥ стовпц≥. ѕот≥м розпод≥л€ють перевозки по кл≥тинкам з одною м≥ткою. ¬ решту кл≥тинок розм≥щують перевозки по найменш≥й вартост≥.

 

.

10.6.5. ћетод потенц≥ал≥в оптим≥зац≥њ опорного плану.

якщо план транспортноњ задач≥ оптимальний, то йому в≥дпов≥даЇ система ≥з чисел та , що задовольн€ють умовам:

1) , дл€ ;

2) , дл€ [10.8]

 

„исла та називаютьс€ потенц≥алами в≥дпов≥дно постачальник≥в ≥ споживач≥в.

якщо хоч би одна не зан€та кл≥тинка не задовольн€Ї [10.8], то опорний план не оптимальний ≥ його можна покращити, введенн€м в цю кл≥тинку перевозку.

«а перв≥сний приймемо план одержаний методом найменшоњ вартост≥:

 

 

“ак €к маЇмо лише 7 заповнених ком≥рок таблиц≥ (), то план €вл€Їтьс€ виродженим Ц р≥вн€нь на одне менше, н≥ж нев≥домих. “ому придамо перевозц≥ нульове значенн€.

ѕриймемо ≥ по заштрихованим ком≥ркам проведемо розрахунок значень потенц≥ал≥в:

ѕ≥сл€ перев≥рки умови у в≥льних ком≥рках опинилис€ з порушенн€м умови кл≥тинки “ому включимо в базис ком≥рку , в €к≥й таке порушенн€ найб≥льше, тобто в цю кл≥тинку потр≥бно зробити зан€тою перевозкою. ƒл€ цього будуЇмо цикл (позначено пунктирною л≥н≥Їю). ≤з ком≥рок, де сто€ть знаки Ђм≥нусї вибираЇмо найменше .

¬ ком≥рку внесемо нульову перевозку. ѕодальш≥ перетворенн€ таблиць подаютьс€ без коментар≥в.

.

 

.

 

 

ќдержали оптимальний базис .

ќдержанн€ розвТ€зку транспортноњ задач≥ в ≈“ Excel зд≥йснюЇтьс€ по т≥й же технолог≥њ, що ≥ дл€ симплекс-методу.

 

ѕ–» Ћјƒ

 
 

 

 


 

 

 






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


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


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

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

¬ы никогда не пересечете океан, если не наберетесь мужества потер€ть берег из виду. © ’ристофор  олумб
==> читать все изречени€...

2100 - | 1925 -


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

√ен: 0.012 с.