28471

Метод найменшої вартості побудови початкового опорного плану

Доклад

Математика и математический анализ

Для даної задачі такою є клітинка А2В2 в яку записується найменше з чисел 220 230. У звуженому полі клітинок вибирається найменша вартість в клітинці А2В1 в яку записується min 10 150 =10. В цю клітинку записується min 280300=280 проставляється прочерк в А3В3 і біля запасів А1 записується залишок в 20 од. Далі заповнюється клітинка А1B4 з найменшою вартістю числом min 20 200=20 виставляються прочерки в клітинках А1В1 А1В2 і записується залишок потреб В4 в розмірі 180 од.

Украинкский

2013-08-20

17.79 KB

13 чел.

17.23.Метод найменшої вартості побудови початкового опорного плану передбачає на першому кроці вибір клітинки з найменшою вартістю перевезення одиниці вантажу (найменшого елемента матриці (cij)). Для даної задачі такою є клітинка А2В2, в яку записується найменше з чисел 220, 230. Олівцем виставляються прочерки в клітинках А1 В2, А3В2, виключаючи тим самим їх з наступного розгляду. Біля запасів А2, записуються залишки запасів в розмірі 10 од. У звуженому полі клітинок вибирається найменша вартість в клітинці А2В1 в яку записується min (10, 150) =10. В А2В3 та А2В4виставляються прочерки, бо запаси А2 вичерпані, а під потребами В1 записуються залишки потреб в розмірі 140 од. На наступному кроці серед клітинок, що залишилися незаповненими, вибирається А1 В3, в якій міститься найменша вартість. В цю клітинку записується min (280,300)=280, проставляється прочерк в А3В3 і біля запасів А1 записується залишок в 20 од. Далі заповнюється клітинка А1B4 з найменшою вартістю (числом min (20, 200)=20), виставляються прочерки в клітинках А1В1, А1В2, і записується залишок потреб В4 в розмірі 180 од. В підсумку залишаються тільки дві клітинки (А3В1, та А3В4), які не мають прочерка або чисел, що визначають величину перевезень. В першу з них (вартість менша) записуємо min (140, 320)=І40, а в другу – залишок запасів А3,. Остаточно отримаємо таблицю 3.Таблиця З

Зауважимо, що доцільно самостійно здійснювати кожен крок побудови опорного плану у власноруч намальованій транспортній сітці, а не користуючись вже готовою табл.З.Побудований опорний план методом найменшої вартості також невироджений. Знайдемо вартість перевезень згідно з ним:

Порівняння отриманих значень цільової функції на планах, побудованих різними методами, вказує на те, що опорний план, записаний в табл. З кращий (цільова функція мінімізується). Відмітимо, що можна навести багато прикладів ТЗ, в яких значення цільової функції на опорному плані, побудованому діагональним методом, е меншим, ніж на плані, побудованому методом найменшої вартості. Проте в середньому метод найменшої вартості дає краще наближення до оптимального плану в порівнянні із діагональним методом.


 

А также другие работы, которые могут Вас заинтересовать

28965. События 1991, распад СССР, образование СНГ и выбор Россией нового исторического пути 37 KB
  Процесс затягивается4 8 декабря Беловежское соглашение Ельцын Кравчук Шушкевич : СССР прекращает существование Россия Украина и Белоруссия объединяются в СНГ. 5 21 декабря АлмаАтинская встреча лидерорв 9 республик Декларация о прекращении существования СССР и о принципах деятельности СНГ.До конца 1991 к СНГ присоединились Молдова и Азербайджан всего в СНГ 11 государств 15 минут 3 прибалтийские республики6 Горбачев сложил свои полномочия.
28966. Россия на пути социально-экономической модернизации. Октябрьские события 1993, завершающий этап ликвидации советской власти 30.5 KB
  явились следствием противостояния законодательной и исполнительной ветвей власти Российской Федерации. Ельцин издал указ О поэтапной конституционной реформе в Российской Федерации в соответствии с которым Верховный Совет и Съезд народных депутатов прекращали свою деятельность. Конституционный суд РФ пришел к заключению о несоответствии данного указа российской Конституции однако Ельцин его не отменил. В 1994 арестованные участники этих драматических событий были амнистированы Государственной думой Российской Федерации.
28967. Принятие конституции РФ 1993г. Качественные изменения социально политической жизни страны 36.5 KB
  Качественные изменения социально политической жизни страны Работа Конституционной комиссии Необходимость принятия новой Конституции была осознана всеми политическими силами еще в ходе принятия Декларации о государственном суверенитете от 12 июня 1990 г. Поначалу работа комиссии проходила довольно быстро и уже через четыре месяца проект новой Конституции был не только подготовлен но и опубликован для всеобщего обсуждения. Седьмой съезд постановил вынести основные положения проекта новой Конституции на всероссийский референдум но восьмой...
28968. Реформы 60-70-х гг. XIXв., их цели и содержание 36.5 KB
  их цели и содержание Реформа местного самоуправления земская и городская Отмена крепостного права привела к необходимости проведения буржуазных реформ и в других областях государственной жизни. по типу земской была проведена городская реформа. Военная реформа Поражение России в Крымской войне показало что необходимо реконструировать всю военную систему. Военная реформа проводилась до 1874 г.
28969. Революционное народничество, его идеология и политическая практика 37 KB
  Революционное народничество его идеология и политическая практика Возникновение народничества. Три течения в народничестве Идеи общинного социализма Герцена и Чернышевского стали основой политического течения радикальной интеллигенции народничества. Народники рассматривали народ крестьянство как реальную политическую силу хотели поднять его на революцию полагали что Россия может прийти к новому справедливому строю социализму минуя капитализм. Народничество стало ведущим направлением в освободительном движении оно имело свою...
28970. Реформы и контрреформы Александра III 26.5 KB
  Реформы и контрреформы Александра III 1. Александр III правил с 1881 по 1894 гг. После убийства отца Александр III выдвинул программу своего царствования: подавление оппозиции революционного движения; укрепление основ российской жизни самодержавия православия народности. Александру III было известно что перед смертью его отец одобрил проект либеральных реформ М.
28971. Характер и особенности социально-экономического развития России во второй половине XIX в. 55 KB
  Характер и особенности социальноэкономического развития России во второй половине XIX в. Промышленный переворот в России начался в конце 30х годов XIX века он имел 2 стороны: техническую переход от мануфактуры к фабрике замена ручного труда машинным; социальную формирование промышленного рабочего класса и класса буржуазии. К 80м годам сформировались основные промышленные районы России: Московский; Петербургский; Прибалтийский; Уральский; Южный Донбасс и Криворожье; Бакинский....
28972. Внешняя политика России во второй половине XIX в. 34 KB
  Внешняя политика России во второй половине XIX в. Кроме того ввиду усиления позиций Англии Франции Германии и Японии в Китае важной задачей стало укрепление позиций России в этом регионе. По договорам с Японией было закреплено право России на Курильские острова. Его фраза: €œРоссия не сердится она сосредотачивается€ – образно выражала принципы внешней политики России того времени.
28973. Россия в начале XX века. Обострение социально- экономических и политических противоречий в стране 29 KB
  Россия в начале XX века. Геостратегическое положение было очень уязвимым и следовательно Россия была вынуждена содержать самую большую армию. Россия была многонациональным государством однако крупных конфликтов на национальной почве не было. По длине железных дорог Россия занимала 2 место в мире уступая только США однако качество было очень низким.