ІІІ. Умови невід’ємності змінних

На базі наведеного математичного опису можна проілюструвати суть цієї моделі так: необхідно визначити значення n невід’ємних змінних , які задовольняють обмеженням 2.2та забезпечують екстремальне значення (максимальне або мінімальне) цільової функції, яка виражена рівнянням 2.1.

До методів вирішення задач ЛП відносяться симплекс-метод, графічний метод.

Симплекс-метод є аналітичним методом знаходження рішення задач ЛП.

Як прави­ло, задачу зводять до канонічної форми. Вважають, що задача лінійного програмування записана в канонічній формі, якщо вона має вигляд

(2.3)

Щоб перевести задачу лінійного програмування з загальної форми (2.1–2.2) до канонічної форми (2.3) необхідно зро­бити такі кроки.

1-й крок.До кожної лівої частини нерівностей (2.2) додаємо нову невід'ємну невідому змінну х_п+і (i= 1,2,...,l–k), яка дорів­нює:

або:

Тоді група нерівностей(2.2)перетвориться на рів­няння.

Введені нові змінні, х_п+і, ... , х_т–k будемо вважати базови­ми, а змінні
x₁, ... , х_п – вільними.

Дістаємо однорідну систему основних обмежень задачі:

2-й крокполягає у зведенні до однорідної системи обмежень на знак. Умови недодатності легко перетворюються в умови невід'ємності за допомогою заміни змінних

Змінну, на знак якої не накладено обмежень, подають у ви­гляді різниці двох невід'ємних змінних:

Ранг сумісної системи обмежень (1.3) r можна вважати та­ким, що дорівнює т, оскільки в іншому разі частину, а саме т – r = k рівнянь треба було б відкинути, бо вони були б лінійними комбі­націями r базових рівнянь. Однак на практиці інколи такі зайві рі­вняння можуть включати в систему обмежень на стадії формуван­ня реальної задачі. Такі обмеження називають неістотними і їх відкидають, що звичайно відбувається при побудові довільного базового розв'язку системи рівнянь. Отже, знайти множину планів задачі – означає знайти множину невід'ємних розв'язків си­стеми лінійних рівнянь.

Означення. Задачу лінійного програмування вважають записаною у канонічній формі, якщо вона задовольняє такі умови:

1. Система обмежень зведена до системи рівнянь виду (2.3).

2. Система рівнянь зображена в такому вигляді, де кожна ба­зова невідома входить тільки в одне рівняння системи з коефіцієн­том рівним одиниці, при чому немає рівнянь, в які не входила хоча б одна базова невідома. Якщо деякі рівняння системи поміняти місцями так, щоб нумерація базових невідомих була строго зрос­таючою, то базовий мінор в цьому випадку складає одиничну мат­рицю.

3. Вільні члени системи обмежень невід'ємні;

4. Оптимізуюча форма залежить тільки від вільних невідомих.

Отже, для того, щоб задачу лінійного програмування можна було розв'язувати симплексним методом потрібно загальну форму(2.1–2.2)звести до канонічної форми. Іншими словами її потріб­но певним способом записати в такій формі, щоб система рівнянь була з базисом.

(2.4)

(2.5)

Для того, щоби базовий план системи обмежень (2.4)був опорним, необхідно і достатньо, щоб всі вільні члени (2.5) були невід'ємні. Отже, для зведення задачі до канонічної форми потріб­но так підібрати базові невідомі, щоб у загальному розв'язку сис­теми обмежень не було від'ємних вільних членів.

Приклад.

Для виготовлення двох видів продукції А і В використову­ють три види сировини: I, II та III.

На виробництво одинці продукції А знадобиться витратити:

сировини I виду – 15 кг,

сировини II виду – 12 кг,

сировини III виду – 3 кг.

На виробництво одинці продукції В знадобиться витратити:

сировини I виду – 2 кг,

сировини II виду – 6 кг,

сировини III виду – 12 кг.

Запаси сировини:

I виду – 300 кг,

II виду – 306 кг,

III виду – 360 кг

Прибуток від реалізації оди­ниці продукції виду А становить 9 грн.,
виду В– 6 грн.

Скласти план виробництва продукції, який забезпечить максимальний прибуток від реалізації при наявності даних запасів сировини.

Розв'язування

Позначимо кількість виготовленої продукції першого виду Ачерез х₁, другого – х₂. Враховуючи витрати сировини I, II та III виду на виготовлення одиниці продукції видів АтаВ, а також обмежені запаси сировини, запишемо систему обмежень (6.1). Прибуток, одержаний з виготовлення продукції у вигляді функції мети (6.2).

(2.6)

(2.7)

Зведемо задачу лінійного програмування (2.6, 2.7) до ка­нонічної форми додавши невідомі х₃, х₄ та х₅ до лівої сторони двох нерівностей відповідно:

(2.8)

;

.

Розв'яжемо систему рівнянь методом Гаусса-Джордана, то­му запишемо систему обмежень (2.8) у вигляді початкової розра­хункової таблиці, яку назвемо ітерацією 1.

Для знаходження початкового базового плану розділимо змінні на дві групи – базові і вільні. Для вибору базових змінних доцільно скористатися таким правилом: в якості базових змінних ітерації симплекс-таблиці необхідно вибрати такі змінні (їх кіль­кість визначається числом основних обмежень), кожна з яких тіль­ки раз входить у рівняння основних обмежень. Решту змінних бу­демо вважати вільними.

Запишемо цільову форму f у вигляді рівняння

Таблиця заповнюється формально за вибраною канонічною формою.

1. Заповнюємо базові стовпчики: на перетині однойменних ряд­ків і стовпчиків ставимо 1, а в усіх інших клітинках будуть нулі.

2. В інших рядках виписуємо коефіцієнти, що стоять біля відповідних невідомих. Нульовий рядок відповідає оптимізуючій формі і служить для визначення ступеня оптимальності опорного плану.

Ітерація 1

Критерій оптимальності. Якщо задача максимізується і в нульовому рядку відсутні від'ємні числа (за винятком хіба що сто­впчика "опорний розв'язок (план)"), то опорний план є оптималь­ним (при мінімізації задачі для оптимальності плану достатньо відсутності додатних чисел у нульовому рядку, за винятком, мож­ливо, опорного розв'язку).

Коефіцієнт рядка "0" можна інтерпретувати як приріст фун­кції f при збільшенні вільної невідомої на одиницю. Приріст буде додатним, якщо коефіцієнт від'ємний, і від'ємним – якщо коефіці­єнт додатний.

В нашому випадку є два від'ємні числа (–9), (–6), беремо най­більше за модулем від'ємне число (–9) (при мінімізації задачі – найбільше додатне), тоді стовпчик "х₁"будемо називати ключовим стовпчиком.

Для вибору ключового елемента складаємо відношення ві­льних членів (чисел стовпчика "опорний розв'язок") до відповід­них додатних чисел ключового стовпчика (усі інші відношення будемо вважати рівними нескінченності):

.

Перше відношення менше, тому число (15) першого рядка буде ключовим елементом. Ключовий елемент в таблиці позначаємо рамкою і переходимо до другої ітерації.

Ітерація 2

f 0
Базові невідомі	№ рядка	План (опорний розв'язок)	x1	x2	x3	x4	x5
х1
x4
x5

Послідовність заповнення другої та наступних ітерацій така (використовуємо метод Гаусса-Жордана):

1. Замість базової невідомої х₃ (ключовий рядок), вводимо
нову базову невідому х₁ (невідому ключового стовпчика),

2. Формально заповнюємо базові стовпчики (пункт 1 ітерації 1).

3. Ключовий рядок одержуємо від ділення його елементів
попередньої ітерації на ключовий елемент.

4. Усі інші комірки ітерації заповнюємо за правилом прямо­кутника:

(2.9)

де a_ij', b_i ' відповідно шукані елементи нової ітерації, а а_ij, b_i – попе­редньої,
а_qs – ключовий елемент.

Рядок 0: ; ; .

Рядок 2: ; ; ; .

Рядок 3: ; ; ;

.

Після заповнення таблиці 2-ої ітерації перевіряємо її опорний план на оптимальність. Бачимо, що потрібно перейти до на­ступного опорного плану, оскільки в нульовому рядку стовпчика "х₂" знаходиться від'ємне число ( ).

.

За ключовий елемент слід взяти число " ".

Ітерація 3

f 0
Базові невідомі	№ рядка	План (опорний розв'язок)	x1	x2	x3	x4	x5
х1
х2
x5

В ітерації 3 замість базової змінної х₄ тепер буде нова базо­ва х₂, ключовим буде рядок 2. Над таблицею виконуємо ті ж опе­рації, що й під час другої ітерації.

Після III-ої ітерації перевіряємо опорний план на оптимальність. Бачимо, що потрібно перейти до на­ступного опорного плану, оскільки в нульовому рядку стовпчика "х₃" знаходиться від'ємне число ( ).

.

За ключовий елемент слід взяти число " ".

Ітерація 4

f 0
Базові невідомі	№ рядка	План (опорний розв'язок)	x1	x2	x3	x4	x5
х1
х2
х3

В рядку 0 вже немає від'ємних чисел, тому опорний план останньої таблиці оптимальний і виписуємо його із стовпчика "опорний розв'язок"

.

*Зауваження 1. Кожній таблиці відповідає своя канонічна форма стандартного запису. Так, наприклад, за останньою табли­цею можна записати таку канонічну форму:

*Зауваження 2. Контролювати правильність обчислення опо­рних планів і оптимального значення можна за значенням функції мети:

*Зауваження 3. При розв'язуванні задачі для зручності ітера­ції послідовно записують одну під одною.