b> +
y i = b i , де і = 1, 2, 3
. . . , m;
j = 1
a 11 x 1 + A 12 x 2 + . . . + a 1n x n + x n +1 = B 1 ,
a 21 x 1 + A 22 x 2 + . . . + a 2n x n + x n +2 = B 2 ,
a m1 x 1 + A m2 x 2 + . . . + a mn x n + x n + m = B m ,
кількість невідоміх МОДЕЛІ x j Ві 0 збільшілась до n + m.
слушно зауваження у підручніку - ЯКЩО знак нерівності Ві, так додаткові Невідомі треба відніматі від лівої Частини нерівності.
Будь-яку задачу лінійного програмування Можливо звесті до стандартної задачі лінійного програмування Шляхом віднімання з лівої Частини рівняння Додатковий невід'ємніх невідоміх частин.
Таким чином ми навч зводіті завдання лінійного програмування від мінімізації до максімізації; переходіті від функціональніх обмежень у вігляді нерівностей до обмежень - рівностей и навпаки; замінюваті Невідомі змінні від'ємні на невід'ємні. Введені додаткові Невідомі змінні мают чіткій економічний Зміст. так, Наприклад, ЯКЩО у обмеженності задачі лінійного програмування (нерівність) відбіваються витрати ресурсу та їх наявність, так додаткова зміна задачі (у ФОРМІ рівняння) дорівнює ОБСЯГИ невітраченого відповідного ресурсу. Слушно зауваження у підручніку - ЯКЩО змінні НЕ є невід'ємною, так ее Можливо замініті на Дві невід'ємні:
x i = u i - v i .
Система обмежень у вігляді рівностей Сумісна, ЯКЩО є хочай б одне решение; несумісна, ЯКЩО ранг матріці ВЅ a ij , i = 1,2, . . . n дорівнює (r), а ранг розшіреної матріці (додан стовбець "b i ") больше чем (r); надмірна, ЯКЩО Одне з рівнянь Можливо отріматі як лінійну комбінацію других. У Системі: n - кількість невідоміх,
m - кількість рівнянь.
Если система Сумісна та не є надмірною, так будемо вважаті, что ранг ее д орівнює (m); тоді:
m - базісні змінні,
(n - m) - Вільні змінні, m
Система у даним випадка має нескінченну кількість розв'язків, так як ми маємо можлівість надаваті вільним зміннім будь-які значення.
Рішення системи рівнянь (обмежень) має Назву базисного решение , ЯКЩО УСІ Вільні змінні дорівнюють нулеві. Сукупність значень невідоміх (чисел) задачі математичного програмування, Які задовольняють усім обмеженності задачі, мают Назву Припустиме решение або планом.
Сукупність усіх Припустиме РІШЕНЬ системи рівнянь є опукло множини. Або множини розв'язків задачі лінійного програмування є опукло.
базисних Припустиме решение задачі лінійного програмування відповідає одній з вершин або граней множини розв'язків.
Оптимальне решение задачі лінійного програмування відповідає одному з базисних Припустиме РІШЕНЬ , тоб досягається у вершіні множини розв'язків, має другу Назва - оптимальний план задачі лінійного програмування.
геометричність Інтерпретація множини допустимих розв'язків задачі лінійного програмування та графічний метод ее розв'язування. /2/стор. 165.
Розглянемо задачу лінійного програмування У ФОРМІ стандартної задачі - З ОБМЕЖЕНОЮ у вігляді нерівностей. З метою наочності розглянемо простішій випадок з двома невідомімі зміннімі. Прігадаємо завдання про планування випуску ПРОДУКЦІЇ малим підпріємством.
Z = 10 x 1 + 20 x 2 ; Z В® max;
х 1 + 3,5 х 2 ВЈ 350;
2 х 1 + 0,5 х 2 ВЈ 240;
х 1 + х 2 ВЈ 150;
х 1 + х 2 Ві 110;
10 х 1 + 20 х 2 Ві 1400;
х 1 Ві 0;
х 2 Ві 0.
Нерівність - обмеження графічно Відображається півплощіною, а границя - граничній прямій, рівняння Якої утворюється перетворенням нерівності на рівняння.
l 1 В® x 1 + 3,5 x 2 = 350;
x 1 = 0, x 2 = 350/3,5 = 100; x 2 = 0, x 1 = 350.
Щоб з'ясувати, яка напівплощіна задовольняє нерівності, перевірімо, Наприклад, чі Включає точку (0,0) 0 + 3,5 Г— 0 ВЈ 350 напівплощіна нижчих граничної прямої - нерівність віконується - напівплощіна нижчих границі.
Таким же чином перевірімо та побуд...
