Власов В.И. Шарипов О.А.
Сборник задач
По линейному программированию
Методические указания
для самостоятельной работы по курсу
“Математическое моделирование и планирование процессов”
Москва 2011 г.
Задача линейного программирования
Линейное программирование - раздел математического программирования, в котором изучаются методы нахождения условных экстремумов линейных функций многих переменных при наличии дополнительных линейных ограничений на эти переменные, имеющих форму неравенств.
Задача линейного программирования: определить такие значения переменных xj, которые обращают линейную целевую функцию этих переменных в экстремум
, j = 1 … n
при условии выполнения линейных ограничений-неравенств, накладываемых на эти переменные
, i = 1 … m, m ≥ n.
Метод решения задач линейного программирования
Наиболее эффективным методом решения задачи линейного программирования является симплекс-метод. При решении задачи линейного программирования этим методом:
1) Ограничения-неравенства приводят к одному виду. Если критерием оптимальности является максимум целевой функции, то ограничения-неравенства должны иметь вид
,
а если критерием оптимальности является минимум целевой функции, то ограничения неравенства приводят к виду
.
Переход от одного вида ограничений к другому осуществляется путем изменения знаков коэффициентов aij и свободных членов bi на противоположные.
2) Систему линейных ограничений-неравенств заменяют системой линейных ограничений-равенств путем введения дополнительных переменных yi. При этом свободный член целевой функции полагают равным нулю
,
.
3) Дополнительные переменные yi выражают через основные xj
,
и полагают все основные переменные xj равными нулю (базисное решение). Однако это решение не оптимально.
4) Для нахождения оптимального решения необходимо поменять местами n основных переменных xj с равным количеством дополнительных переменных yi, т.е. перевести n дополнительных переменных yi в базисные, равные нулю.
Для этого поочередно в каждом столбце коэффициентов aij определяют разрешающий элемент apq, т.е. положительный элемент столбца, имеющий максимальное отношение к абсолютной величине свободного члена
aij / | bi | = max.
и меняют местами основную переменную xj=q и соответствующую дополнительную переменную yi=p. Полученное значение xj=q подставляют в остальные уравнения.
Задача считается решенной, если в строке целевой функции, не считая свободного члена, нет ни одного положительного элемента (признак оптимальности).
Если после перевода всех основных переменных из базиса в строке целевой функции есть положительный элемент, то соответствующую дополнительную переменную переводят из базисной в свободную, а свободную в базисную, т.е. меняют местами две дополнительные переменные.