Математична постановка задач лінійного програмування. Система гіпотез.
ЗАГАЛЬНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ ТА МЕТОДИ ЇЇ РОЗВ'ЯЗУВАННЯ
Приклади економічних проблем, які доцільно розв’язувати, використовуючи методи і моделі математичого програмування.
ТЕМА 2
Загальна лінійна математична модель економічних процесів і явищ — так звана загальна задача лінійного програмування (ЛП) подається у вигляді:
знайти максимум (мінімум) функції
або
за умов
Отже, потрібно знайти значення змінних , які задовольняють умови (2.2) і (2.3), тоді як цільова функція набуває екстремального (максимального чи мінімального) значення.
Задачу (2.1)—(2.3) легко звести до канонічної форми, тобто до такого вигляду, коли в системі обмежень (2.2) всі невід'ємні, а всі обмеження є рівностями.
Якщо якесь bi від'ємне, то, помноживши i-те обмеження на (–1), дістанемо у правій частині відповідної рівності додатне значення. Коли i-те обмеження має вигляд нерівності то останню завжди можна звести до рівності, увівши допоміжну змінну .
Аналогічно обмеження виду зводимо до рівності, віднімаючи від лівої частини допоміжну змінну , тобто .
Приклад 2.1. Записати в канонічній формі таку задачу ЛП:
за умов
Розв'язування. Помножимо другу нерівність на (–1) і введемо відповідно допоміжні змінні x4 і x5 для другого та третього обмеження:
Неважко переконатися, що допоміжні змінні, у цьому разі x4 і x5, є невід'ємними, причому їх уведення не змінює цільової функції.
Отже, будь-яку задачу ЛП можна записати в такій канонічній формі:
знайти максимум функції
за умов
Задачу (2.4)—(2.6) можна розв'язувати на мінімум, якщо цільову функцію помножити на (–1), тобто