програмування
Лінійне програмування - математична дисципліна, присвячена теорії і методам вирішення завдань про екстремуму лінійних функцій на множинах n-мірного векторного простору, що задаються системами лінійних рівнянь і нерівностей.
Лінійне програмування є окремим випадком математичного програмування. Одночасно воно - основа декількох методів вирішення завдань цілочисельного і нелінійного програмування.
Багато властивостей завдань лінійного програмування можна інтерпретувати також як властивості багатогранників і таким чином геометрично формулювати і доводити їх.
Термін В«програмуванняВ» потрібно розуміти в сенсі В«плануванняВ». Він був запропонований в середині 1940-х років Джорджем Данцигом, одним із засновників лінійного програмування, ще до того, як комп'ютери були використані для
рішення лінійних задач оптимізації.
Формулювання задачі лінійного програмування
Потрібно максимізувати
В
за умов
В
при i = 1, 2, 3,. . ., M ..
Іноді на x i також накладається деякий набір обмежень у вигляді рівностей, але від них можна позбутися, послідовно висловлюючи одну змінну через інші і підставляючи її у всіх інших рівності і нерівності (а також у функції f).
Таке завдання називають "Основний" або "стандартної" в лінійному програмуванні. <В
1.2 Види задач лінійного програмування
В
Потік і паросполучення
Розглянемо задачу про максимальному паросполучення: є кілька юнаків і дівчат; для кожної пари відомо, чи люблять вони один одного. Потрібно одружити максимальне число пар. Введемо змінні x ij - вони відповідають парі з i-того юнаки та j-тої дівчини. Введемо обмеження: x ij ≥ 0, x ij ≤ 1 ,,,. Можна показати, що серед оптимальних рішень цього завдання знайдеться цілочисельне. Змінні, рівні 1, будуть відповідати парам, які слід одружити.
Друге важливе завдання - максимальний потік. Нехай є граф (з орієнтованими ребрами), в якому для кожного ребра вказана його пропускна здатність. І задані 2 вершини: сток і витік. Потрібно вказати для кожного ребра, скільки через нього буде протікати рідини (не більшу за його пропускної спроможності) так, щоб максимізувати сумарний потік з стоку в джерело (рідина не може з'являтися або зникати під всіх вершинах, крім стоку і витоку). Візьмемо як змінних x i - Кількість рідини, що протікають через i-тое ребро. Тоді,, де c i - пропускна здатність i-того ребра. Ці нерівності треба доповнити рівністю кількості втікає і витікає рідини для кожної вершини, крім стоку і витоку. В якості функції f природно взяти різницю між кількістю витікає і втікає рідини в джерелі.
Узагальнення попередньої задачі - максимальний потік мінімальної вартості. У цій задачі дано вартості для кожного ...
