* x1 + 3 * x2? 160? 0; x2? 0.
Введемо на площині прямокутну декартову систему координат x10x2. Відомо, що геометричне місце точок на площині, координати яких задовольняють системі лінійних нерівностей, утворюють опуклий багатокутник.
Цей багатокутник називається багатокутником рішень даної системи нерівностей. Сторони цього багатокутника розташовуються на прямих, рівняння яких виходять, якщо в нерівностях системи знаки нерівностей замінити на знаки рівностей. А сам цей багатокутник є загальна частина напівплощин, на які ділить площину кожна із зазначених прямих.
Викреслити ці прямі (рис 7.2).
x 2
100 -
90 - (2)
80 -
70 -
60 - (1)
50 - P
40 -
30 - M R
20 -
10 - ® grad f F (3)
0 ? ? ? ? ? ? ? ? ? ? x 1
10 20 30 40 50 60 70 80 90 100
Рис. 7.2
Напівплощини в перетині дають багатокутник рішень 0PRF. При цьому, будь-яка точка з нутрощі багатокутника задовольняє всім нерівностям (7.7).
Розглянемо лінійну форму (7.6)
(x1, x2)=10 * x1 + 12 * x2.
Виберемо внутрішню точку M0 (x1, x2), наприклад x1=10, x2=30, і обчислимо значення цільової функції Z0=F (10,30)=10 * 10 + 12 * 30=460.
Рівняння 10 * x1 + 12 * x2=Z0 визначає на площині геометричне місце точок, в яких пряма f (x1, x2) приймає постійне значення Z0. Міняючи значення Z0, отримуємо різні прямі, проте всі вони паралельні між собою, тобто утворюють сімейство паралельних прямих. Ці прямі перпендикулярні вектору ® grad f=10 ® e1 + 12 ® e2. Вектор ® grad f вказує напрямок, рухаючись по якому, ми переходимо від менших значень форми до великих. Тепер має бути ясним, що оптимальне рішення визначається точкою R (35,30) (мал.7.2), і найбільше значення форми f одно 10 * 35 + 12 * 35=710.
Отже, оптимальне рішення задачі знайдено x1=30, x2=35.
7.2 Симплекс метод розв'язання задач лінійного програмування
На практиці в задачах планування доводиться вирішувати задачі лінійного програмування з дуже великим числом змінних. При великому числі змінних ми не можемо скористатися графічним методом, і потрібні інші способи вирішення завдання.
Канонічний вид задачі ЛП. Насамперед задачу лінійного програмування (ЛП) призводять до деякого стандартного вигляду, званому канонічним.
Як ми знаємо, загальна постановка задачі ЛП включає цільову функцію
f (x1, x2, x3, ..., xn)=c1x1 + c2x2 + ... + cnxn ® max (min)
обмеження типу рівностей
gi=ai1x1 + ai2x2 + ... + ain xn + bi=0 i=1,2, ..., k
і обмеження типу нерівностей
gi=ai1x1 + ai2x2 + ... + ain xn + bi? 0 i=k + 1, k + 2, ..., n
Усюди нижче ми будемо вважати, що на змінні накладено умова
xj? 0, i=1, ..., n
Насамперед відзначимо, що при розробці методів розв'язання задач ЛП досить розглядати задачі мінімізації, оскільки будь-яка задача на максимум зводиться до задачі на мінімум шляхом заміни цільової функції f на нову цільову функцію F=-f.
Далі, ми можемо виключити зі складу обмежень нерівності. Для цього вводяться l додаткових позитивних змінних xn + 1, xn + 2, ..., xn + l, і завдання набуває вигляду
min f (x1, ..., xn, xn + 1, ..., xn + l)=c1 * x1 + c2 * x2 + ... + cn + l * xn + l (7.8)
(тут cn + 1=cn + 2=...=cn + l=0),
a11x1 + a12x2 + ... + a1, n xn=b1
............. x1 + ak2x2 + ... + ak, n xn=bk (7.9) + 1,1x1 + ak + 1,2x2 + ... + ak + 1, n + 1xn + 1=bk + 1
............. + l, 1x1 + ak + l, 2x2 + ... + ak + l, n + lxn + l=bk + l? 0, j=1, ..., n + l. (7.10)
Як ми бачимо, канонічна форма задачі ЛП (7.8) - (7.10) є окремий випадок її загальної постановки, який відрізняється від загального тим, що тут немає обмежень типу нерівностей, крім умов позитивності, і відшукуються лише точки мін...
