Раздел 4. Оптимизация задач линейного программирования
Задача условной оптимизации называется задачей линейного программирования (ЛП), если все функции – целевая и ограничений - являются линейными:
при ограничениях
(4.1)
где
.
Это - стандартная форма задачи ЛП. В
общем случае ограничения могут иметь
знак „
"
или „=". Однако, умножая неравенство
на -1 и
заменяя равенство двумя неравенствами , можно придти к стандартной форме.
Кроме того, взяв вместо f(x) функцию –f(x), можно получить задачу на минимум.
Приведем основные свойства задачи ЛП.
Допустимое множество решений задачи ЛП либо пусто, либо является выпуклым многогранником в Rn (как пересечение полупространств, описываемых ограничениями-неравенствами). Оно может быть как ограниченным, так и неограниченным; в любом случае это замкнутый многогранник.
Если допустимое множество не пусто, а целевая функция ограничена сверху (для задачи максимизации, а для задачи минимизации - ограничена снизу) на этом множестве, то задача ЛП имеет оптимальное решение.
Оптимальные решения задачи ЛП (если они существуют) всегда находятся на границе допустимого множества. Точнее, если существует единственное оптимальное решение, то им является какая-либо вершина многогранника допустимых решений; если две или несколько вершин являются оптимальными решениями, то любая их выпуклая комбинация также является оптимальным решением (т.е. существует бесконечно много точек максимума или минимума).
Универсальный метод решения задач ЛП называется симплекс-методом. Применение этого метода и его наиболее часто встречающейся модификации - двухфазного симплекс-метода мы поясним на примерах.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи
Рис. 4.1 Задача линейного программирования
ЛП) за конечное число "шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Для ускорения решения необходимо при переходе от одной вершины к другой двигаться по такому ребру многогранника, при перемещении по которому изменение значения целевой функции максимально.
Пример решения 4.1
Решить следующую задачу ЛП в канонической форме симплекс-методом, изображенную на рис. 4.1. Составим систему линейных неравенств, образующих допустимое множество решений.
Заменим обозначение целевой функции f(x) на обозначение переменной X0, приравняем её значение нулю и перенесём её переменные 2X1 и 3X2 влево от знака равно со знаком минус.
X0 - 2X1 - 3X2 = 0 .
Выпишем ограничительные неравенства в виде системы.
X0 - 2X1 - 3X2 = 0
X2 ≤ 8
X1 + 3 X2 ≤ 27
X1 + 2 X2 ≤ 20
X1 + X2 ≤ 14
2 X1 + X2 ≤ 24
X1 ≤ 11
.
Рис. 4.2 Значение целевой функции в оптимальной точке (8, 6)
В каждое неравенство введём по одной положительной переменной X3, …, X8, дополняющей значение левой части каждого неравенств до равенства правой части.
X0 - 2 X1 - 3X2 = 0
X2 + X3 = 8
X1 + 3X2 + X4 = 27
X1 + 2X2 + X5 = 20
X1 + X2 + X6 = 14
2 X1 + X2 + X7 = 24
X1 + X8 = 11
Для однозначного решения системы из шести уравнений с восемью переменными присвоим двум переменным X1 и X2 значение, равное нулю. Остальные (базисные) переменные станут равными значениям правых частей уравнений. Решение системы соответствует вершине А выпуклого многоугольника (симплекса) допустимых решений системы, совпадающей с началом координат (см. рис. 4.2). Такой вид системы, в которой целевая функция выражена через переменные с нулевыми значениями (X1 и X2), а в остальных ограничительных уравнениях по одной ненулевой переменной (X3, …, X8), называется базисным. Он позволяет определить значение целевой функции в вершине симплекса A и ребро многоугольника, при движении по которому значение целевой функции увеличивается максимально. Это ребро совпадает с X2. Переместимся по нему до следующей вершины B. Значение X2 определяем, как минимальное отношение правой части в каждом уравнении к коэффициенту при переменной X2.
X2 = min (8/1, 27/3, 20/2 , 14/1, 24/1, 11/0) = 8
Уравнение, которому соответствует минимальное отношение, называется опорным и выделяется цветом. Умножая его на соответствующее число и складывая с целевой функцией или с каждым из остальных уравнений, добиваемся того, чтобы в них коэффициент при X2 был равен нулю. Тогда система снова примет базисный вид для следующей вершины симплекса B и по знакам коэффициентов в целевой функции можно будет определить, оптимальная ли эта вершина, или нет. Для оптимальной вершины все коэффициенты в целевой функции будут положительными и задача будет решена. Если коэффициенты отрицательны, то выбирается отрицательный коэффициент, наибольший по абсолютной величине. Ему соответствует ребро симплекса, при перемещении по которому значение целевой функции увеличивается максимально. В нашем случае это переменная Х1 (ребро ВС). По аналогии с X2 определяется минимальное значение X1, при котором текущая точка перемещается в следующую вершину С. Выделяется соответствующее ей опорное уравнение и с помощью него обнуляются коэффициенты при X1 в целевой функции и в остальных ограничительных уравнениях. Получив тем самым базисный вид системы для этой вершины симплекса, определяем по виду целевой функции, оптимальна ли эта вершина. И если нет, повторяем выбор переменной с отрицательным коэффициентом, исключая её из числа нулевых (небазисных) в системе до тех пор, пока в уравнении целевой функции все переменные не будут с положительными коэффициентами.
Первое преобразование системы в базисную форму для вершины B.
X0 - 2X1 + 3X3 = 24
X2 + X3 = 8
X1 - 3 X3 + X4 = 3
X1 - 2 X3 + X5 = 4
X1 - X3 + X6 = 7
2X1 - X3 + X7 = 16
X1 + X8 = 11
X1 = min (8/0, 3/1, 4/1 , 7/1, 16/2, 11/1) = 3
Второе преобразование системы в базисную форму для вершины C.
X0 - 3X3 + 2X4 = 30
X2 +X3 = 8
X1 -3X3 +X4 = 3
X3 -X4 + X5 = 1
2 X3 -X4 + X6 = 4
5 X3 -2X4 + X7 = 10
3 X3 - X4 + X8 = 8
X3 = min (8/1, 3/-3, 1/1 , 4/2, 10/5, 8/3) = 1
Третье преобразование системы в базисную форму для вершины D.
X0 -X4 + 3X5 = 33
X2 + X4 - X5 = 7
X1 -2X4 +3X5 = 6
X3 - X4 +X5 = 1
2 X4 -2X5 +X6 = 2
3 X4 -5X5 +X7 = 5
2 X4 - 3X5 +X8 = 5
X4 = min (7/1, 6/-2, 1/-1 , 2/2, 5/3, 5/2) = 1
Четвёртое преобразование системы в базисную форму для вершины E.
X0 2X5 + 1/2X6 = 34
X2 - X6 = 6
X1 + 2X5 + 3X6 = 8
Это последнее преобразование системы в базисную форму, потому что в уравнении целевой функции коэффициенты при нулевых переменных X5 и X6 – положительны. Максимальное значение целевой функции равно 34, а оптимальные значения перменных X1 и X2 равны соответственно 8 и 6.
Этим значениям, полученным аналитически, соответствуют значения X0, X1 и X2, полученные графически (см.рис.4.2)
Преобразования системы уравнений в базисную форму удобно выполнять в приложении Excel.
На рис.4.3 показана исходная система уравнений. Нулевую переменную X2 изменяем до 8.
Рис. 4.3 Значение целевой функции в точке (0, 0)
На рис. 4.4 показано первое преобразование системы в канонический вид для следующей вершины.
Нулевую переменную X1 увеличиваем до 3.
Рис. 4.4 Значение целевой функции в точке (0, 8)
На рис. 4.5 показано второе преобразование системы в канонический вид для следующей вершины.
Нулевую переменную X3 увеличиваем до 1.
Рис.4.5 Значение целевой функции в точке (3, 8)
На рис 4.6 показано третье преобразование системы в канонический вид для следующей вершины.
Нулевую переменную X4 увеличиваем до 1.
Рис. 4.6 Значение целевой функции в точке (6, 7)
На рис. 4.7 показано последнее преобразование системы в канонический вид для следующей вершины.
Коэффициенты при нулевых переменных X5 и X6 - положительны. Значит целевая функция – максимальна, а переменные X1 и X2 – оптимальны и равны соответственно 8 и 6.
Рис. 4.7 Значение целевой функции в оптимальной точке (8, 6)
Варианты заданий для этого примера приведены в приложении 4.1