Головна

Штучне початкове рішення. Метод великих штрафів.

  1. D графіка. Методи 3D моделювання, достоїнства і недоліки.
  2. Ex.7. Використовуючи текст, складіть список слів, які називають основні методи дослідження хворих і цілі їх використання. Складіть пропозиції з цими словами.
  3. G ЦИВІЛЬНО-ПРАВОВОЇ МЕТОД ПРАВОВОГО РЕГУЛЮВАННЯ Метод правового регулювання, характеризується
  4. I. Методичні вимоги до структури реферату та його змістом
  5. I. Методи прискореного виведення токсичних речовин з організму

У задачі 1 для отримання початкового базисного рішення використовувалися залишкові змінні. Однак, коли вихідне обмеження записано у вигляді рівності або має знак  , Не можна відразу ж отримати допустиме початкове базисне рішення. Покажемо це на конкретному прикладі.

Початкова форма завдання: Стандартна форма задачі:

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

ідея використання штучних змінних достатня проста. Вона передбачає включення невід'ємних змінних в ліву частину кожного з рівнянь, що не містять «очевидних» початкових базисних змінних. Забезпечуючи отримання початкового базису, ці додатково вводяться змінні виконують, по суті, ту ж роль, що і залишкові змінні. Однак, оскільки такі штучні змінні не мають відношення до змісту поставленого завдання, їх введення допустимо тільки в тому випадку, якщо відповідна схема обчислень буде забезпечувати отримання оптимального рішення, в якому все штучні змінні виявляться рівними нулю.

Для побудови необхідної схеми обчислень можна застосувати наступний прийом: накласти «штраф» за використання штучних змінних, що вводяться в цільову функцію. Розроблено два методи отримання стартової точки, в яких використовується «штрафування» штучних змінних: метод великих штрафів і двоетапний метод.

Розглянемо схему застосування методу великих штрафів в нашому прикладі. У першому і другому рівняннях немає змінних, що виконують роль залишкових. Тому введемо в кожне з цих рівнянь по одній штучної змінної, позначивши їх через и :

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

 базис с  -4  -1  -М  -М  зауваження
 
 -М  1 - min
 -М  -1
   -9М  -7М + 4  -4М + 1 М  
Z  Оскільки штучна змінна  з базису виключена, то відповідний стовпець можна вже не заповнювати.
 -4
 -М  -1  -min
   -2M-4 -  M- M    
Z Z  1-min  
 -4
 -1 -  негативні.
  - -      
Z Z    ;
 -4 -  
 -1  
  -  

 

 



Рішення завдання 1 симплексним методом | Визначення транспортної задачі.

Стандартна (канонічна) форма задачі лінійного програмування | обмеження | | | Графічне рішення задачі лінійного програмування | Симплексний метод розв'язання задачі лінійного програмування | Збалансована транспортна модель | Особливі випадки застосування симплекс-методу | Інтерпретація симплекс-таблиць - аналіз моделі на чутливість |

© um.co.ua - учбові матеріали та реферати