ребра і потрібно серед максимальних потоків вибрати потік з мінімальною вартістю. Ця задача зводиться до 2 задачах лінійного програмування: спочатку потрібно вирішити завдання про максимальний потік, а потім додати до цього завдання обмеження , Де m - величина максимального потоку, і вирішити завдання з новою функцією f (x) - вартістю потоку.
Всі ці завдання можуть бути вирішені швидше, ніж за допомогою загальних алгоритмів розв'язання задач лінійного програмування, за рахунок особливої вЂ‹вЂ‹структури рівнянь і нерівностей.
Транспортна завдання
Є якийсь однорідний вантаж, який потрібно перекласти з n складів на m заводів. Для кожного складу i відомо, скільки в ньому знаходиться вантажу a i , а для кожного заводу відома його потреба b j у вантажі. Вартість перевезення пропорційна відстані від складу до заводу (всі відстані c ij від i-го складу до j-го заводу відомі). Потрібно скласти найбільш дешевий план перевезення. Вирішальними змінними в даному випадку є x ij - кількості вантажу, перевезеного з i-го складу на j-й завод.
Обмеженнями будуть і
.
Цільова функція має вигляд:, яку треба мінімізувати.
Гра з нульовою сумою
Є матриця A розміру. Перший гравець вибирає число від 1 до n, другий - від 1 до m. Потім вони звіряють числа і перший гравець отримує a ij очок, а другий (- a ij ) очок (i - число, вибране першим гравцем, j - другим). Потрібно знайти оптимальну стратегію першого гравця. Нехай в оптимальній стратегії число i потрібно вибирати з імовірністю p i . Тоді оптимальна стратегія є рішенням наступної задачі лінійного програмування:,,, (), в якій потрібно максимізувати функцію. c в оптимальному рішенні буде математичним очікуванням виграшу першого гравця в найгіршому випадку.
В
1.3 Методи вирішення завдань лінійного програмування
В
Симплекс-метод
Зведемо задачу лінійного програмування до перегляду крайніх точок допустимого безлічі. Саме спрямований перебір крайніх точок допустимого безлічі і здійснюється симплекс-методі, викладеному нижче. p> Розглянемо зв'язок між геометричним поняттям крайньої точки і його аналітичної інтерпретацією. Для обмеженої множини, описаного за допомогою системи нерівностей
В
крайніми точками є рішення невироджених підсистем види:
В
(1)
де - деяка підмножина індексів
В
і
В
і матриця, складена з рядків-векторів а i , неособлива. p> Позначимо єдине рішення системи (3) через x. Припустимо тепер, що існують і такі, що для Оскільки для
В В
то, очевидно,. У силу єдиності рішення (3). p> З іншого боку, якщо - крайня точка, то можна позначити через безліч рівностей
В
Позначимо через матрицю, складену з рядків Якщо припустит...
