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. Отже, початковий опорний план невнроджений.

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


 

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

47781. КРАЇНОЗНАВСТВО (КРАЇНИ СНД). КУРС ЛЕКЦІЙ 1.08 MB
  Загарбання Московською державою нових територій підготувало грунт для проголошення Росії імперією що сталося у вересні 1721 р. Послідовне здійснення Петром І реформ і зумовлені ними успіхи як на фронтах Північної війни так і в придушенні внутрішнього опору призвели до суттєвих змін у зовнішньополітичній концепції Росії. Саме Катерина ІІ продовжила активну і наступальноагресивну зовнішньополітичну діяльність Росії. Наступним зовнішньополітичним успіхом Росії стало здобуття у союзі з Австрією перемоги у війні з Туреччиною 17871791 рр.
47782. Закономірності зовнішньої форми кристалів 83.5 KB
  Поняття про кристали. У сучасній техніці кристали широко використовуються у радіотехніці електроніці автоматиці телемеханіці оптиці. Сьогодні у промислових умовах вирощують штучні кристали алмаз кварц напвпровідникові матеріали германій кремній різноманітні сполуки.
47783. Теоретико-методологічні та історичні засади політології 815.5 KB
  у цьому ж коледжі створюється перша школа політичної науки що поклало початок активному формуванню в США системи політичних навчальних і наукових закладів.Моска публікує книгу Елементи політичної науки що дає підстави поширенню політичної науки у Європі з кінця ХІХ ст. Політика це форма суспільної діяльності спрямована на здобуття використання підтримку і повалення політичної влади реалізацію інтересів особи соціальних груп на різних рівнях інститутів політичної системи. Об'єктами політики є всі явища політичного і суспільного життя...
47784. Курс лекцій. Основи охорони праці 528 KB
  Предмет і задачі курсу Охорона праці Місце в системі наук. Правові і організаційні питання охорони праці. Система законодавчих актів з охорони праці.
47785. Основи психологічної практики (практична психологія). Курс лекцій 130.5 KB
  сихологічна практика, натомість сприяє збагаченню індивідуального досвіду, змінює рівень свідомості й характер потреб, впливає на вибір цінностей, ставлення до соціальних норм. Для цього спершу слід упредметнити (уречевити), об’єктивувати психологічний зміст суб’єкта (людини). І тут постають два шляхи для реалізації цього завдання...
47786. Основи технологій в галузях народного господарства. Курс лекцій 739 KB
  Виробничі системи створюють для виготовлення необхідної продукції. Основні переваги підвищення різноманітності та гнучкості виробництва на основі використання електродвигунів зростання якості продукції виробленої із сталі та інших метало продуктів стандартизація виробництва урбанізація. Основні переваги масове виробництво серійної продукції з використанням конверсійних технологій стандартизація виробництва розселення людей у приміських зонах. Засвоєння технологічних основ виробництва різних видів продукції стану базових галузей...
47788. Основи технологій в галузях народного господарства 2.92 MB
  Ливарне виробництво Загальні відомості про ливарне виробництво Способи виготовлення відливок Контроль якості відливокСутність ливарного виробництва полягає у виготовлення деталі або заготовки шляхом заливання рідкого металу в ливарну форму порожнина якої за розмірами і конфігурацією відповідає готовій деталі. Технології ливарного виробництва забезпечують можливість: виготовлення деталей різної форми різної маси...
47789. Психологія і педагогіка вищої школи: предмет, завдання, методи 734.5 KB
  Психологія вищої школи вивчає закономірності функціонування психіки студента як субєкта навчальнопрофесійної діяльності та закономірності науковопедагогічної діяльності викладача а також соціальнопсихологічні особливості професійнопедагогічного спілкування та взаємин викладачів і студентів. До найважливіших практичних завдань психології вищої школи в період реформування вищої освіти в Україні належать: розробка наукової психологометодичної бази для контролю за процесом повноцінністю змісту та умовами психічного розвитку студентів їх...