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