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

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


 

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

460. Мастерская по ремонту тракторов города Тюмень 668 KB
  Потребность в механизмах, инвентаре, материалах, рабочих по профессиям и квалификации. Выбор методов и способов производства работ с их обоснованием. Расчет численности работающих и определение площадей административно-бытовых помещений. Обеспечение качества СМР, техники безопасности.
461. Теорія грошей, грошові та кредитні системи 615 KB
  Сутність та економічна основа грошового обороту. Методи державного регулювання грошового обороту. Сутність і закономірності розвитку інфляції. Грошові потоки та їх балансування. Кон'юнктурна теорія цінності грошей. Внесок Дж.Кейнса і М.Фрідмана у розвиток теорії грошей.
462. Небесные тела в астрофизике 636 KB
  Электромагнитное излучение, исследуемое в астрофизике. Фотоэлектрические приемники излучения. Физические свойства Планет земной группы и планет гигантов. Распределение звезд в Галактике. История развития космонавтики.
463. Інформаційні системи і технології 570 KB
  Визначення інформаційної системи, структура, принципи створення. Класифікація інформаційних систем за ступенем структурованості. Економічна інформація як об'єкт обробки в інформаційних системах. Форми представлення економічної інформації, носії і засоби її передачі. Ієрархічний та фасетний метод класифікації.
464. Мікроконтроллери 3x3x3 LED куб 643.5 KB
  3x3x3 LED куб це фігура яка складаються з 27 світлодіодів, яку використовують переважно для дизайну інтер'єру. Різні сфери використання 3x3x3 LED куба. Розробка програмного і технологічного продукту, створення мікросхеми та розробка програми.
465. Построение современных систем автоматизации теплоэнергетического оборудования на базе свободно-программируемых контроллеров (ПЛК) 565 KB
  Структура подсистем автоматизации отопительного котла. Котлоагрегат как объект регулирования. Задачи контура регулирования разрежения в топке котла. Разработка программы оценки экономии электроэнергии при внедрении ЧРП. Расчет эксплуатационных затрат на автоматизацию.
466. Знакомство с операционной системой MS DOS та Windows XP 315 KB
  Основные команды MS DOS. Основные команды работы с файлами и каталогами. Знакомство с программой Volkov Commander. Принципы организации многозадачной работы в системе. Исследование методов запуска программы Проводник.
467. Градієнтний метод числової оптимізації задач нелінійного програмування 1.16 MB
  Застосування градієнтного методу, коли обмеження на область зміни змінних х відсутні. Застосування градієнтного методу, коли наявні обмеження на область зміни змінних х. ознайомлення з градієнтним методом числової оптимізації, набуття навиків розв’язку та аналізу задач нелінійного програмування градієнтним методом.
468. Инженерные решения постройки много квартирных домов старого образца 197.5 KB
  Ознакомление с постройками много квартирных домов старого образца, инженерными системами этих домов, системами энергосбережения этих домов (до реконструкции, после реконструкции).