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

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


 

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

33061. Зародження філософії 15.38 KB
  Зародження філософії історично співпадає з виникненням зачатків наукового знання з появою громадської потреби в цілісному переконанні на світ і людину у вивченні загальних принципів буття і пізнання. онтос буття суще вчення про буття чи про першооснови усього сущого : проблема буття розуміється тут в універсальному всеосяжному сенсі чому є щось а не ніщо одне з перших філософських питань аналізуються буття сам принцип існування небуття чи можливе неіснування ніщо буття матеріальне природа і ідеальне ідея думка...
33062. Співвідношення філософії та науки 15.18 KB
  Порівняння пізнавальних можливостей філософії і конкретних наук зясування місця філософії в систему людських знань має давні традиції в європейській культурі. Ще в античності Платон і Арістотель намагалися розмежувати особливості науки і філософії. При цьому теоретична міць філософії прагнення логічно обгрунтувати знання висловити його в теоретичній формі виявлялася несумірної з можливостями конкретних наук що давало підстави протягом довгих століть від Аристотеля до Гегеля вважати філософію наукою наук .
33063. Джерела, провідні ідеї та напрями філософії Стародавньої Індії 59.26 KB
  Джерела провідні ідеї та напрями філософії Стародавньої Індії Зародки філософського мислення Індії сягають у глибоку давнину середина І тис. Канонічним духовним джерелом Стародавньої Індії є Веди із їх назвою споріднено наше слово відати знати записані на листях пальми приблизно за 1. Таким чином вже у найдавніших духовних джерелах Стародавньої Індії йдеться про фундаментальні моральні ідеї про певне осмислення становища людини у світі про різні шляхи звільнення від кармінних законів долі найкращим з яких є шлях дійового...
33064. Канонічні джерела, провідні ідеї та напрями філософії Стародавнього Китаю 57.41 KB
  Давньокитайська філософія порівняно з давньоіндійською виглядає стрункішою, деталізованішою (аж до нумерології та побудови вичерпних систем комбінаторики подвійних символічних елементів світобудови) та більше зануреною у глибину суперечливого, парадоксального мислення.
33065. Натурфілософія 13.62 KB
  ntur природа філософія природи умоглядне тлумачення природи що розглядається в її цілісності що спирається на абстрактні поняття що виробляються в ході виникнення і розвитку філософії. фюсис природа або фюсиологами а перші філософські трактати як правило були присвячені дослідженню природи її пристрої трактати Про природу були написані і Фалесом і Гераклитом і Анаксимандром і Анаксименом і Парменидом. філософія ще не існувала окремо від пізнання природи а знання про природу окремо від філософії. У центрі уваги усієї...
33066. Філософія Сократа 15.29 KB
  Платон. Платон 427347 рр. Учень Сократа Платон у 397 р. Платон долає проблему що зафіксована Сократом завдяки створенню гіпотези про існування специфічних предметів відмінних від речей навколишнього світу.
33067. Філософія Середньовіччя, її особливості 19.96 KB
  Фома Аквінський спрямовує свої зусилля на розмежування суті того у що віримо і що знаємо. Фома описує Бога як першопричину і конечну мету сущого як “чисту форму†“чисту актуальність†або буття. Фома називає таке буття субстанцією. У своїх працях Фома розділяє догмати віри на такі що осягаються розумом Бог існує Бог єдиний душа людини безсмертна і такі що розумом не можуть бути осягнені творення світу трійця першородний гріх тощо.
33068. Основні напрями в середньовічній філософії /номіналізм та реалізм/ 15.02 KB
  Однією з особливостей середньовічної філософії є боротьба між реалістами та номіналістами. Слід зазначити, що реалізм у його середньовічному розумінні не має нічого спільного з сучасним значенням цього терміна. Реалізм - це вчення, згідно з яким об'єктивна реальність
33069. Гуманізм 14.01 KB
  Гуманізм епохи Відродження це сукупність навчань що представляють людини мислячої що вміє не тільки плисти за течією але і здатного пручатися і діяти самостійно. Саме гуманізм епохи Відродження проголосив інші принципи формування особистості. Гуманізм епохи Відродження прочинив цю завісу.