в€™ 3 = 22.
Отже, найдешевший набір для профілактичного прийому полягає з 2 гр . комплексу А і 3 гр . комплексу В , і його вартість дорівнює 22 руб.
Тепер нескладно сформулювати геометричний спосіб вирішення стандартних задач ЛП з двома змінними:
зображується допустимий багатокутник - перетин півплощини, які є рішеннями відповідних нерівностей;
зображується цільової вектор;
В· через допустиме безліч проводиться перпендикуляр до цільового вектору - це лінія рівня цільової функції;
шляхом переміщення лінії рівня паралельно самій собі в напрямку цільового вектора доти, поки не виявиться по одну сторону від переміщуваної прямий, візуально визначається точка (або точки) максимуму;
В· обчислюються координати точки максимуму (рішенням відповідної системи рівнянь, задають прямі, точка перетину яких і є шукана точка) і максимальне значення цільової функції.
Зауваження. Для визначення точки мінімуму слід переміщати изолинию проти напрямку цільового вектора.
У розібраних прикладах оптимальний план знаходився в єдиній вершині багатокутника допустимих планів. Однак при вирішенні задач ЛП можуть зустрітися й інші випадки. p> Нескінченна безліч оптимальних планів. На рис.1.4 цільова функція приймає одне і те ж максимальне значення в будь-якій точці відрізка AB , з'єднує дві вершини безлічі планів Х . Така ситуація виникає, якщо лінії рівня паралельні граничній прямій. p> Відсутність обмеженого рішення . На рис.1.5 зображений випадок, коли цільова функція не обмежена зверху на безлічі планів і вирішення завдання на максимум не існує. При цьому рішення задачі на мінімум може існувати, (як у задачі про вітаміни). p> Відсутність допустимих планів. На рис.1.6 області, допустимі по кожному з обмежень, не мають спільних точок. У цьому випадку кажуть, що обмеження несумісні, безліч планів порожньо і завдання ЛП рішення не має. br/>В
Рис. 1.4 Рис. 1.5 Рис. 1.6
2. Симплекс-метод
2.1 Ідея симплекс-методу
Розглянемо універсальний метод вирішення канонічної задачі лінійного програмування
,,,
з n змінними і m обмеженнями-рівностями, відомий як симплекс-метод. p> Безліч планів канонічної завдання - опукле багатогранне безліч, що має кінцеве число кутових точок. І якщо це завдання має оптимальне рішення, то воно досягається хоча б в одній кутовий точці.
З будь кутовий точкою пов'язаний базисний план завдання, в якому змінних дорівнюють нулю, а решті змінним відповідають лінійно незалежні стовпці матриці умов. Ці лінійно незалежні стовпці утворюють невироджених базисну матрицю.
Перебір всіх кутових точок пов'язаний з великими обчислювальними витратами і тому не ефективний. У 1947 році Дж. Данциг запропонував упорядковану процедур...
