Метод решения задач линейного программирования

Власов В.И. Шарипов О.А.

Сборник задач

По линейному программированию

Методические указания
для самостоятельной работы по курсу

“Математическое моделирование и планирование процессов”

 

 

Москва 2011 г.

 

Задача линейного программирования

 

Линейное программирование - раздел математического программирования, в котором изучаются методы нахождения условных экстремумов линейных функций многих переменных при наличии дополнительных линейных ограничений на эти переменные, имеющих форму неравенств.

Задача линейного программирования: определить такие значения переменных x_j, которые обращают линейную целевую функцию этих переменных в экстремум

, j = 1 … n

при условии выполнения линейных ограничений-неравенств, накладываемых на эти переменные

,   i = 1 … m, m ≥ n.

 

Метод решения задач линейного программирования

Наиболее эффективным методом решения задачи линейного программирования является симплекс-метод. При решении задачи линейного программирования этим методом:

1) Ограничения-неравенства приводят к одному виду. Если критерием оптимальности является максимум целевой функции, то ограничения-неравенства должны иметь вид

,

а если критерием оптимальности является минимум целевой функции, то ограничения неравенства приводят к виду

.

Переход от одного вида ограничений к другому осуществляется путем изменения знаков коэффициентов a_ij и свободных членов b_i на противоположные.

2) Систему линейных ограничений-неравенств заменяют системой линейных ограничений-равенств путем введения дополнительных переменных y_i. При этом свободный член целевой функции полагают равным нулю

 ,

.

3) Дополнительные переменные y_i выражают через основные x_j

 ,

и полагают все основные переменные x_j равными нулю (базисное решение). Однако это решение не оптимально.

4) Для нахождения оптимального решения необходимо поменять местами n основных переменных x_j с равным количеством дополнительных переменных y_i, т.е. перевести n дополнительных переменных y_i в базисные, равные нулю.

Для этого поочередно в каждом столбце коэффициентов a_ij определяют разрешающий элемент a_pq, т.е. положительный элемент столбца, имеющий максимальное отношение к абсолютной величине свободного члена

a_ij / | b_i | = max.

и меняют местами основную переменную x_j=q и соответствующую дополнительную переменную y_i=p. Полученное значение x_j=q подставляют в остальные уравнения.

Задача считается решенной, если в строке целевой функции, не считая свободного члена, нет ни одного положительного элемента (признак оптимальности).

Если после перевода всех основных переменных из базиса в строке целевой функции есть положительный элемент, то соответствующую дополнительную переменную переводят из базисной в свободную, а свободную в базисную, т.е. меняют местами две дополнительные переменные.