28487

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

Доклад

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

Рекомендуємо олівцем проставити прочерки в клітинках А2 В1 і А3 В1 потреби В1 задоволені а біля 300 справа записати залишки запасів в розмірі 150 од. запасів і 220 од. В напрямку який визначає діагональ переходимо до А2В2 в яку записуємо min70 230=70 виставивши прочерк в А3 В2 закресливши залишок потреб під В2 і записавши справа від 230 залишок запасів 23070=160. В клітинку А2В3 заносимо min 160 280= 160 виставляємо прочерк в А2В4 закреслюємо залишок запасів А2 160 а під потребами В3 записуємо залишок потреб В3 в розмірі...

Украинкский

2013-08-20

21.99 KB

6 чел.

15. Методи побудови початкового опорного плану транспортної задачі

Як і для симплексного методу, при розв'язуванні транспортної задачі необхідно мати початковий опорний план. В якості ілюстрації алгоритмів методів побудови початкового опорного плану розглянемо транспортну задачу з такими даними

Оскільки  = то робимо висновок, що дана транспортна задача закрита Побудуємо транспортну сітку для цієї задачі.Таблиия 2

Ідея діагонального методу (північно-західного кута) полягає в послідовному заповненні клітинок, починаючи з АД і завершуючи клітинкою А1В1.Отже, в клітинку А1 В1 запишемо мінімальне з чисел 150, 300 (проаналізуйте чому). В постачальника А, внаслідок цього залишиться 150 одиниць вантажу.

Рекомендуємо олівцем проставити прочерки в клітинках А2 В1 і А3 В1 (потреби В1 задоволені), а біля 300 справа записати залишки запасів в розмірі 150 од. Переходимо до заповнення клітинки А1В2, якій відповідають 150 од. запасів і 220 од. потреб. Знову мінімальне з цих двох чисел (150) заносимо в А1 В2, проставивши олівцем прочерки в А1В3 та А1В4 (запаси вичерпані)" і записавши під числом 220 залишок потреб 70 од. В напрямку, який визначає діагональ, переходимо до А2В2, в яку записуємо min(70, 230)=70, виставивши прочерк в А3 В2 закресливши залишок потреб під В2 і записавши справа від 230 залишок запасів 230-70=160. В клітинку А2В3, заносимо min (160, 280)= 160, виставляємо прочерк в А2В4, закреслюємо залишок запасів А2 (160), а під потребами В3 записуємо залишок потреб В3 в розмірі 120 од. В клітинку А3В3 записуємо min (120,320)=120, закреслимо 120 під потребами В3 і біля запасів А3 записуємо залишок запасів в розмірі 320-120=200 од. Нарешті, в клітинку А3В4 заносимо 200. Рекомендуємо здійснити перевірку правильності побудови опорного плану шляхом додавання величин перевезень по рядкам і колонкам - кожний раз необхідно отримати відповідну величину запасів або потреб. Після перевірки записи олівцем знищуються (табл.2). Охарактеризуємо отриманий опорний план. Заповненим клітинкам відповідають базисні змінні, значення яких дорівнюють вмістимому клітинки: х11=150, х12=150, ..., х34 =200, а порожнім клітинкам відповідають вільні змінні, значення яких дорівнюють нулю (х1314=...=х32=0). Суттєвою характеристикою кожного опорного плану є його виродженість чи невиродженість.оОзначення.оОпорнийоплан називається невиродженим, якщо число базисних змінних (заповнених клітинок) дорівнює рангу матриці обмежень (системи обмежень), тобто m + n-1, і виродженим, якщо це число менше від m + n-1. В нашому випадку  = 3 + 4 - І = 6 і число базисних змінних також дорівнює 6. Отже, початковий опорний план невнроджений.

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


 

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

52693. Здоровьесберегающие технологии в начальной школе 68.5 KB
  А так как дети находятся в школе до вечера важное значение имеет воспитание у детей потребности в здоровье как жизненно важной ценности сознательного стремления к ведению здорового образа жизни. Здоровье одна из сущностных характеристик человека наряду с духовностью интеллектуальностью определяющая степень жизнеспособности устойчивости организма в соответствие среде обитания возможности реализовать свои биологические и социальные требования. На первый план выступает не только задача физического развития детей сохранения и укрепления...
52694. Суть та структура проектно-технологтчної діяльності учнів 78.5 KB
  Суть та структура проектно-технологтчної діяльності учнів В останні десятирічча в центрі уваги психолого-педагогічної науки знаходиться вивчення особливостей і можливостей людини умов цілеспрямованої дії на розвиток її творчого потенціалу створення повноцінного навчаючого і розвиваючого середовища. Вона допомагая сформувати в учнів життєво важливі основи технологічних знань і вмінь залучити їх до різних видів практичної діяльності з...
52695. Новое время: встреча Америки и Европы. 4-й класс 44 KB
  – Зачем люди отправлялись в путешествия ответы детей– Что вы знаете об открытии Америки ответы детей слайд 1 см. На пути Колумба оказалась земля которую он принял за Индию слайд 2. Фернан Магеллан был португальцем слайд 3. Даниэль Дефо 1660–1731 написал знаменитый приключенческий роман “Жизнь и удивительные приключения Робинзона Крузо†восславивший труд и волю к жизни слайд 4.
52696. Венерические болезни и меры профилактики 31.5 KB
  Проблемное обучение Тема: Венерические болезни и меры профилактики. Цель: сформировать понятия венерические болезни гонорея сифилис генитальный герпес знание мер профилактики симптомов возбудителей болезни. Планируемый результат: знать понятия венерические болезни гонорея сифилис генитальный герпес знание мер профилактики симптомов возбудителей болезни. На всем Земном шаре люди сталкиваются независимо от их желания с такой проблемой как венерические болезни а столкнувшись с ней не очень компетентны в данной области.
52697. Сценарій свята, присвяченого останньому дзвонику «Хай доля ваша буде дзвінка та крилата»! 111 KB
  Хай відкривають двері у майбутнє. На все життя запам’ятайте мить чудову Ми радо запрошуємо на свято 53 випуск Манвелівської середньої загальноосвітньої школи щоб їх благословити на доросле життя В Під рушниками – оберегами Хай перший ваш проляже шлях Хай біжить він не по тернах по квітучих вже полях випускники зупиняються В. Побажаємо щастя хай доля стелиться їм світлим полотном танцюристи передають рушники батькам які роблять почесний коридор.
52699. Повторение изученного материала. (Сложение и вычитание многозначных чисел) 51 KB
  Проверка выполнения домашнего задания. В течение урока мы будем помогать строителям дома выполняя разные математические задания тем самым будем закреплять изученный материал. а Подготовка площадки для строительства нового дома: 1.10кг б как вы думаете с чего начинается строительство дома ответы детей с планапроекта грамотное составление плана проекта способствует правильному строительству дома поэтому внимание: расшифруйте фразу из ответов решив эти примеры по 2 командам.