UCBL, MIM Mastery, Operational Research Linear Programming

1.1 Що таке лінійне програмування

1.1.1 Приклад: проблема дієти Поллі [1, с.3]

Щоденні потреби: Енергія 2000 ккал Білок 55г Кальцій 800 мг

Їжа доступна

Порція	Енергія (ккал)	Білки (г)	Кальцій (мг)	Ціна/порція
Крупи	28г	110	4	2	3
Курка	100г	205	32	12	24
Яйця	2 великі	160	13	54	13
Незбиране молоко	237 куб	160	8	285	9
Пиріг	170г	420	4	22	20
Свинина та квасоля	260г	260	14	80	19

Який вибір для Полі ?

Обмеження: Крупи не більше 4 порцій на день Курка не більше 3 порцій на день Яйця не більше 2 порцій на день Молоко не більше 8 порцій на день Пиріг не більше 2 порцій на день Свинина і квасоля не більше 2 порцій на день

Як формалізувати проблему? (моделювання)

Що робить проблему такою конкретною ?

Чи знаєте ви, як вирішити подібні проблеми ?

1.1.2 Стандартна форма задачі лінійного програмування

З обмеженнями: 2 * x1 + 3 * x2 + x3

4 * x1 + x2 + 2 * x3

3 * x1 + 4 * x2 + 2 * x3

Згорнути: 3 * x1 - x2

З обмеженнями: - x1 + 6 * x2 - x3 + x4> = -3

7 * x2 + 2 * x4 = 5

З обмеженнями:

Вибір змінних (x 1, ..., x n) називається рішенням задачі.

Рішення можливо, якщо воно перевіряє обмеження.

z називається цільовою функцією. З кожним рішенням воно пов'язує значення.

Рішення є оптимальним, якщо воно здійсненне та максимізує цільову функцію.

1.1.3 Наявність оптимальних рішень ?

Розглянемо наступні чотири стандартні задачі лінійного програмування, написані із синтаксисом системи алгебри MuPAD:

Chvatal7b: = [[x1 + x2

Chvatal7c: = [[-2 * x1 + x2

Перший випадок: унікальне оптимальне рішення
Другий випадок: відсутність можливого рішення
Третій випадок: немає оптимального рішення, оскільки ми можемо змусити цільову функцію прагнути до нескінченності за допомогою можливих рішень.
Четвертий випадок: нескінченність оптимальних рішень.

1.2 Симплексний алгоритм

1.2.1 Дотик до лінійної алгебри

11 = s2 + 4 * x1 + x2 + 2 * x3

8 = s3 + 3 * x1 + 4 * x2 + 2 * x3

Це лінійна система з 6 невідомими та 3 рівняннями.

1.2.2 Перша проблема

4 * x1 + x2 + 2 * x3

3 * x1 + 4 * x2 + 2 * x3

5 * x1 + 4 * x2 + 3 * x3,

Удосконалення рішення ?

Введення змінних відхилень:

11 = s2 + 4 * x1 + x2 + 2 * x3

8 = s3 + 3 * x1 + 4 * x2 + 2 * x3

z = 5 * x1 + 4 * x2 + 3 * x3

Збільшуючи x1 до 5/2, ми опускаємо s1 до нуля.

Ми трансформуємо систему, щоб повернути нас до ситуації, подібної до попередньої:

1 = s2 - 5 * x2 - 2 * s1

1/2 = s3 - 1/2 * x2 + 1/2 * x3 - 3/2 * s1

z = 25/2 - 7/2 x2 + 1/2 * x3 - 5/2 * s1

Збільшуємо x3 до 1, що зменшує s3 до 0:

2 = x1 + 2 * x2 + 2 * s1 - s3

1 = s2 - 5 * x2 - 2 * s1

z = 13 - 3 * x2 - s1 - s3

А тепер що ми робимо ?

1.2.3 Змінні відхилення

1.2.4 Таблиці

2 * x1 + 3 * x2 - x3

2 * x1 - x2 + 2 * x3],

5 * x1 + 5 * x2 + 3 * x3,

Або у матричній формі:

2 = s2 - x1 + 3 x3

2 = s3 + 2 x1 + 3 x2 - x3

4 = s4 + 2 x1 - x2 + 2 x3

z = 0 + 5 x1 + 5 x2 + 3 x3

| "лінопт", "restr", slk [1], slk [2], slk [3], slk [4], x3, x1, x2 |

| "obj", 0, 0, 0, 0, 0, 3, 5, 5 |

| slk [1], 3, 1, 0, 0, 0, 1, 1, 3 |

| slk [2], 2, 0, 1, 0, 0, 3, -1, 0 |

| slk [3], 2, 0, 0, 1, 0, -1, 2, 3 |

| slk [4], 4, 0, 0, 0, 1, 2, 2, -1 |

2 = s1 + 3/2 x2 + 3/2 x3 - 1/2 s4

3 = s2 + 3/2 x2 + 5/2 x3 + 1/2 s4

2 = s3 - 4 x2 + 3 x3 - s4

z = 5 - 5/2 x2 + 11/2 x3 - 5/2 s4

Ось словник, що відповідає попередній таблиці:

x4 = 2 - 3/2 x2 - 3/2 x3 + 1/2 x7

x5 = 3 - 3/2 x2 - 5/2 x3 - 1/2 x7

x6 = 2 + 4 x2 - 3 x3 + x7

z = 5 - 5/2 x2 + 11/2 x3 - 5/2 x7

Рівняння масиву описують афінний підпростір E ℝ n + m .

Точка p цього простору характеризується своїми координатами в неосновних змінних.

Що ми можемо сказати про два афінні підпростори ℝ n + m, які вони визначають ?

Кожен вибір неосновних змінних відповідає афінному базису цього підпростору.

Масив здійсненний, якщо базове рішення (0,…, 0) є можливим рішенням.

Аналогічно, масив є можливим, якщо константи у верхніх рівняннях всі додатні або нульові.

Повернемось до прикладу [1, с. 19]:

t: = linopt: Transparent: userstep (t, slk [3], x3);

Використовуйте симплексний алгоритм для вирішення таких лінійних програм:

3 * x1 + 2 * x2 + 4 * x3,

1.3 Пастки та як їх уникнути

1.3.1 Короткий зміст попередніх епізодів

У нас є алгоритм, який працює на кількох прикладах.

Є три речі, щоб перевірити, чи працює це взагалі:

Ініціалізація
Ітерація
Припинення

1.3.2 Ітерація

Зробіть висновок про те, що система має унікальне оптимальне рішення, обчисліть його та сертифікуйте;
Зробіть висновок про те, що система має нескінченність оптимальних рішень, обчисліть і сертифікуйте їх;
Зробіть висновок про необмеженість системи та підтвердьте її, описуючи півлінію рішень, для яких z приймає величини, як завгодно.
Знайдіть вхідну змінну, вихідну змінну та виконайте зведення. За побудовою отримана таблиця еквівалентна попередній таблиці і досі є здійсненною. Крім того, z збільшився в широкому розумінні (тобто константа z * у новому виразі для z більша або дорівнює старому).

Доказ. Просто проаналізуйте можливу таблицю. Позначимо через S 1, ..., S m основні змінні, X 1,…, X n неосновні змінні, а C 1,…, C n, z * - коефіцієнти, такі що z = z * + ∑ C i X i .

Якщо C i i, то основним рішенням таблиці координат X 1 * = ⋯ = X n * = 0 є унікальне оптимальне рішення. Перевірте це, довівши, що будь-яке можливе рішення координат X 1, ..., X n, що надає однакове значення z = z * цільовій функції, дорівнює базовому рішенню масиву.
Якщо C i ≤0 для всіх i, основне рішення таблиці є оптимальним, а набір оптимальних рішень описується лінійними нерівностями системи та скасуванням неосновних змінних X i, для яких маємо C i X i, неосновна змінна з коефіцієнтом C i> 0. Якщо рівняння таблиці не накладають обмеження на X i, система необмежена: півлінія, описана (0,…, 0, X i, 0,…, 0) для X i ≥0, складена здійсненно рішення, що дають величини, як завгодно, бажані a z .
В іншому випадку одна з основних змінних S j падає до нуля, і ми можемо здійснювати поворот між вхідною змінною X i та вихідною змінною S j. За побудовою нове базове рішення відповідає здійсненному рішенню (0,…, 0, X i, 0,…, 0) для X i ≥0. Зокрема, нова таблиця є можливою, і оскільки C i ≥0, константа z * зросла в широкому розумінні.

- x1 + 3 * x2 + 4 * x3

2 * x1 - 4 * x2 + 6 * x3],

2 * x1 - x2 + 8 * x3,

t1: = linopt: Transparent: userstep (t0, slk [1], x3);

t2: = linopt: Transparent: userstep (t1, slk [3], x1);

t3: = linopt: Transparent: userstep (t2, slk [2], x2);

t4: = linopt: Transparent: userstep (t3, x3, slk [1]);