стандартної форми, має наступний вигляд:
Максимізувати
Z = X 1 + 25X 2 + 0S 1 + 0S 2
При обмеженнях
5X 1 + 100X 2 + S 1 = 1000
- X 1 + 2 X 2 + S 2 = 0
X 1 => 0, X 2 => 0 , S 1 => 0, S 2 => 0
Кожну точку простору рішень даної завдання, представлену на рис.1, можна визначити за допомогою змінних X 1 , X 2 , S 1 і S 2 , фігурують у моделі стандартної форми. При S 1 = 0 і S 2 = 0 обмеження моделі еквівалентні равенствам, які представляються відповідними ребрами простору рішень. Збільшення змінних S 1 і S 2 буде відповідати зсуву допустимих точок з кордонів простору рішень у його внутрішню область. Змінні X 1 , X 2 , S 1 і S 2 , асоційовані з екстремальними точками А, В, і С можна порядок, виходячи з того, яке значення (нульове або ненульове) має дана змінна в екстремальній точці.
Екстремальна точка
Нульові змінні
Ненульові змінні
А
S 2 , X 2
S 1 , X 1
В
S 1 , X 2
S 2 , X 1
З
S 1 , S 2
X 1 , X 2
В
Аналізуючи таблицю, легко помітити дві закономірності:
1. Стандартна модель містить два рівняння і чотири
невідомих, тому в кожній з екстремальних точок дві (= 4 - 2) змінні повинні мати нульові значення.
2. Суміжні екстремальні точки відрізняються тільки однієї пе-
пасової в кожній групі (нульових і ненульових змінних),
Перша закономірність свідчить про можливість визна-
ділення екстремальних точок алгебраїчним способом шляхом при-
равніванія нулю такої кількості змінних, яке дорівнює
різниці між кількістю невідомих і числом рівнянь.
У цьому полягає сутність властивості однозначності екстремальних
точок . На рис. 1 кожної неекстремальному точці відповідає
не більше однієї нульової змінної . Так , будь-яка точка внутрішньої
області простору рішень взагалі не має ні однієї нульової
змінної, а будь-яка неекстремальні точка , лежача на кордоні ,
завжди має лише одну нульову зміну .
Властивість однозначності екстремальних точок дозволяє визна-
ділити їх алгебраїчним методом. Будемо вважати , що лінійна
модель стандартної форми містить т рівнянь і п ( т <= п ) НЕ-
відомих ( п равие частини обмежень - невід'ємні ) . Тоді
всі допустимі екстремальні точки визначаються як всі одно-
значні невід'ємні рішення системи m рівнянь , в ко-
торих п - m змінних дорівнюють нулю.
Однозначні рішення такої системи рівнянь, одержувані
шляхом прирівнювання до нулю ( п - т ) змінних , називаються
базисними рішеннями . Якщо базисне рішення задовольняє
вимогу невід'ємності правих частин , воно називається
допустимим базисним рішенням. Змінні , мають нульове
значення , називаються небазисними змінними , решта -
бази...
