4. Постановка задачі лінійного програмування
Зада́ча ліні́йного програмува́ння — задача оптимізації з лінійною цільовою функцією та допустимою множиною обмеженою лінійними рівностями або нерівностями.
Тобто, необхідно мінімізувати
(1)
при обмеженнях
,
(2)
,
(3)
,
(4)
де cj (j = 1, …, n), aij(i = 1, …, m) — задані числа.
Задача максимізації функції (1) зводиться до задачі мінімізації шляхом заміни знаків всіх коефіціентів cj на протилежні.
Методи розв’язання:
Метод потенціалів — розроблений в 1940 радянськими вченими Канторовичем та Гавуріним Л. В. в застосуванні до транспортної задачі;
Симплекс-метод — цей метод є узагальненням методу потенціалів для випадку загальної задачі лінійного програмування. Розроблений американським вченим Данциґом Дж.-Б. в 1949 році.
двоїстий симплекс-метод розроблений згодом після прямого симплекс-методу, і який є, по суті, симплекс-методом розв'язання двоїстої задачі лінійного програмування, але сформульованої в термінах вихідної задачі.
5. Рішення симплекс-методом, використовуючи перетворення Йордана-Гаусса.
Шляхом введення нових змінних yi (i=1,2) переходимо до канонічної форми у наступному вигляді:
Y1=-3x1-2x2+32≥0
Y2=-x1-2x2+24≥0
xi≥0 (i=1,2)
yj≥0 (j=1,2)
3x1+2x2+y1=32
X1+2x2+y2=24
xi≥0 (i=1,2)
yj≥0 (j=1,2)
Складемо повну симплекс-таблицю, яка відповідає даній задачі.
|
X1 |
X2 |
Y1 |
Y2 |
F |
1 |
Y1 |
3 |
2 |
1 |
0 |
0 |
32 |
Y2 |
1 |
2 |
0 |
1 |
0 |
24 |
F |
-2 |
-3 |
0 |
0 |
1 |
0 |
Так як у Fрядку є від’ємні елементи, обираємо найбільший по модулю від’ємний елемент (-3) - отже 2 стовпець буде розрахунковим. Для визначення розрахункового рядка знайдемо найменше невід’ємне відношення вільних членів до елементів розрахункового (2-го) стовпця.
Min={32/2; 24/2}=24/[2]
Розрахунковим рядком є 2 рядок: R22=a22=2
Для переходу до нового базису над повною симплекс-таблицею з вибраним розрахунковим елементом зробимо перетворення Йордана-Гаусса. Елементи розрахункового рядка ділимо на розрахунковий елемент. У розрахунковому стовпці всі елементи нулі і тільки замість розрахункового елемента ставимо одиницю. Всі інші елементи шукаємо за правилом прямокутника.
Наприклад елемент а11=а11-a12*а21/а22=3-1*2/2=2
Ця операція робиться до тих пір, поки у F рядку всі елементи не будуть додатніми.
|
X1 |
X2 |
Y1 |
Y2 |
F |
1 |
Y1 |
2 |
0 |
1 |
-1 |
0 |
8 |
X2 |
0,5 |
1 |
0 |
0,5 |
0 |
12 |
F |
-0,5 |
0 |
0 |
1,5 |
1 |
36 |
|
X1 |
X2 |
Y1 |
Y2 |
F |
1 |
X1 |
1 |
0 |
0,5 |
-0,5 |
0 |
4 |
X2 |
0 |
1 |
-0,25 |
0,75 |
0 |
10 |
F |
0 |
0 |
0,25 |
1,25 |
1 |
38 |
Відповідь: x1=4, x2=10, Fmax=38.
Перевірка: F=2x1+3x2=2*4+3*10=8+30=38
6.
Білет №18