Решение задачи линейного
программирования симплекс-методомЛадовер Татьяна МихайловнаНовороссийский колледж строительства и экономики
Отличительной особенностью ЗЛП, образующих подмножество задач математического программирования, является то, что цель задачи записывается в виде линейной функции f(X) и ограничения её также линейны.
Основной задачей линейного программирования являетсянахождение
таких значений переменных Х= (х
1, х
2, х
3, …, х
n), которые приводят целевую
функцию f(X) к экстремальному значению.
Общий вид записи модели ЗЛП:
f(X) = c
1x
1 + c
2x
2+ … +c
nx
n → extrem
при условиях-ограничениях:
a
11x
1 + a
12x
2 + … +a
1nx
n ≤ b
1 a
21x
1+ a
22x
2 + … +a
2nx
n ≤ b
2 .
.
a
m1x
1 + a
m2x
2 + … +a
mnx
n≤b
m,
где
x
i ≥ 0, i = 1 ÷ n – искомые величины,
a
ij, b
j, c
i– заданные постоянные величины,
b
j - запасы сырья, энергии и т.д., j= 1 ÷ m.
Совокупность чисел Х= (х
1, х
2, х
3, .. х
n), удовлетворяющих ограничениям
задачи, называется допустимым решением или планом или областью допустимых
решений (ОДР).
Допустимое решение, максимизирующее или минимизирующее целевую функцию, называется оптимальным решением или оптимальным планом.
Решить ЗЛП в частном случае при наличии двух переменных можно графическим методом.
Если в ЗЛП более двух переменных, то самым распространённым методом решения является симплекс-метод.
Симплексом называется выражение вида
c
1x
1 + c
2x
2 + …+ c
nx
n или сумма парных произведений векторов
Методика решения задач с f(x)→ min отличается от методики решения задач c f(x)→ max
. Для удобства решения задач обоих типов по единому алгоритму их модели необходимо привести к т.н. канонической форме (КФ).
Считается, что ЗЛП записана в канонической форме, если:
a) её целевая функция максимизируется;
b) ограничения задачи имеют вид равенства с неотрицательной правой частью (b
j ≥ 0);
c)
все переменные в модели задачи неотрицательные (≥ 0).
Таким образом, каноническая форма модели ЗЛП имеет вид:
f(x) = c
1x
1 + c
2x
2 + …+ c
nx
n → max
a
11x
1+ a
12x
2 + …+ a
1nx
n = b
1a
21x
1+ a
22x
2 + …+ a
2nx
n = b
2 .
a
m1x
1+ a
m2x
2 + …+ a
mnx
n = b
m x
i ≥ 0, i = 1 ÷ n
b
j≥ 0, j = 1 ÷ m
Рассмотрим два типа математических моделей ЗЛП.
I.
Приведём к КФ ЗЛП, заданную моделью, в которой все ограничения вида ≤:
f(x) = c
1x
1+ c
2x
2 + …+ c
nx
n → max
a
11x
1 + a
12x
2+ …+ a
1nx
n ≤ b
1(*) a
21x
1 + a
22x
2+ …+ a
2nx
n ≤ b
2 .
.
a
m1x
1+ a
m2x
2 + …+ a
mnx
n ≤ b
m x
i ≥ 0, i = 1 ÷ n
b
j≥ 0, j = 1 ÷ m
Во всех неравенствах системы ограничений левая часть меньше либо равна правой (≤). Для того чтобы уравнять их (как того требует каноническая форма), необходимо к левой части каждого ограничения
прибавить, соответственно, неотрицательные целые переменные x
n+1, x
n+2,…, x
n+m. Чтобы не изменилось значение целевой функции, эти переменные вводятся в неё с нулевыми коэффициентами.
Т.о. после приведения к канонической форме наша
задача будет иметь вид:
f(x) = c
1x
1 + c
2x
2 + …+ c
nx
n + 0* x
n+1 + 0* x
n+2 … +0* x
n+m → max
a
11x
1+ a
12x
2 + …+ a
1nx
n + x
n+1 = b
1 a
21x
1+ a
22x
2 + …+ a
2nx
n + x
n+2 = b
2 ·
·
a
m1x
1+ a
m2x
2 + …+ a
mnx
n + x
n+m = b
m x
i ≥ 0, i = 1 ÷ n+m
b
j≥ 0, j = 1 ÷ m
Переменные x
n+1 ÷
x
n+m называются дополнительными.
Если ограничение в исходной математической модели задачи задано знаком строго равенства (=), то в него не вводят дополнительную переменную, а только искусственную (см.ниже).
Пример1.
Пусть экономическая задача описывается следующей моделью
f(x) = 10x
1 +13x
2 → max
6x
1+ 5x
2 ≤ 30
4x
1 + 8x
2 ≤ 32
2x
1 + 4x
2 ≤ 12
х
i ≥ 0, i = 1 ÷
Приведём эту математическую модель к КФ:
f(x) = 10x
1 +13x
2 + 0* x
3 + 0*x
4 + 0* x
5 → max
6x
1+ 5x
2 + x
3 = 30
(*) 4x
1 + 8x
2 + x
4 = 32
2x
1 + 4x
2 + x
5 = 12
x
i ≥0, i = 1 ÷ 5.
II.
Рассмотрим второй частный случай: f(x)→min и хотя бы одно из ограничений вида ≥ (или даже все). Модель этой задачи имеет вид:
f(x) = c
1x
1+ c
2x
2 + …+ c
nx
n → min
a
11x
1 + a
12x
2+ …+ a
1nx
n ≥ b
1(**) a
21x
1 + a
22x
2+ …+ a
2nx
n ≥ b
2 ·
·
a
m1x
1+ a
m2x
2 + …+ a
mnx
n ≥ b
m x
i ≥0, i = 1 ÷ n
b
j≥ 0, j = 1 ÷ m
Определение минимального значения функции f(x) можно свести к нахождению максимального значения функции -f(x).
Т.о. в подобных случаях коэффициенты при неизвестных в f(x) → min надо умножить на (-1).
Чтобы привести к строгому равенству ограничения вида ≥, надо из левой части каждого ограничения такого вида
вычесть, соответственно, неотрицательные целые переменные x
n+1, x
n+2, …., x
n+m.Тогда после приведения к КФ задача (**) будет иметь вид:
f(x) = -(c
1x
1 + c
2x
2 + …+ c
nx
n) + 0* x
n+1 + 0* x
n+2 …+0* x
n+m → max
a
11x
1+ a
12x
2 + …+ a
1nx
n - x
n+1 = b
1a
21x
1+ a
22x
2 + …+ a
2nx
n - x
n+2 = b
2 ·
·
a
m1x
1+ a
m2x
2 + …+ a
mnx
n - x
n+m = b
m x
i ≥ 0, i = 1 ÷ n+m
b
j≥ 0, j = 1 ÷ m.
Все переменные в математической модели делятся на два типа:
-
базисные (зависимые), которые могут быть выражены через все остальные
переменные. Переменная является базисной, если она входит
только в одно из уравнений системы с коэффициентом равным 1 (так в системе (*)базисными являются переменные х
3, х
4, х
5).
- все остальные переменные являются
небазисными (независимыми).
Частное решение, т.е. нахождение базисных переменных при приравнивании небазисных переменных нулю (х
i= 0), называется базисным. Базисное решение называется вырожденным, если хотя бы одна из базисных переменных = 0, такая задача называется вырожденной. В противном случае - задача называется невырожденной.
Выше мы рассмотрели два частных случая I и II.
В случае I базисное решение является допустимым решением:
x
n+1 = b
1x
n+2 = b
2 ·
x
n+m= b
m .
Во II-м случае (см. КФ модели (**)) базисное решение имеет вид
- x
n+1 = b
1- x
n+2 = b
2 .
.
- x
n+m= b
m и не является допустимым, т.к. противоречит условию неотрицательности переменных (x
i ≥ 0).
В таких случаях для выделения базисных переменных и нахождения допустимого решения используют метод искусственного базиса, заключающийся в следующем:
1) в каждое ограничение вида ≥ или = вводят искусственную неотрицательную переменную у
1, у
2,… у
m;2) в целевую функцию искусственные переменные входят с коэффициентом (-М), где М – очень большое положительное число (отсюда и название - М-метод).
После ввода искусственных переменных КФ задачи (**) будет иметь вид:
f(x)= -(c
1x
1+ c
2x
2+ …+c
nx
n) + 0* x
n+1 + 0* x
n+2 …+ 0* x
n+m– М*у
1 …–М*у
m → max
a
11x
1+ a
12x
2 + …+ a
1nx
n - x
n+1 + у
1 = b
1a
21x
1+ a
22x
2 + …+ a
2nx
n - x
n+2 + у
2 = b
2·
·
a
m1x
1+ a
m2x
2 + …+ a
mnx
n - x
n+m + у
m = b
mx
i ≥0, i = 1 ÷ n+m,
b
j ≥ 0,
y
j ≥ 0, j = 1 ÷ m
Набор искусственных переменных у
1, у
2,…,у
m в М-методе образует искусственный базис. Искусственные переменные вводятся только для получения исходного базисного плана при решении задач ЛП симплекс-методом. Решение ЗЛП удобно производить в т.н. симплекс-таблицах следующего вида:
Значение целевой функции f(x) вычисляют как сумму парных произведений элементов столба С и элементов столбца В. Относительные оценки
- как сумму парных произведений элементов столба С и элементов соответствующего i-го столбца.
Алгоритм решения ЗЛП симплекс-методом1. Привести математическую
модель к канонической форме. Заполнить симплекс-таблицу и вычислить значения
целевой функции и относительных оценок.
2. – если все относительные
оценки неотрицательные и среди базисных переменных нет искусственных, то план
оптимален, т.е. задача решена. Решение находим в столбце В:
x
n+1 = b
1x
n+2 = b
2 ·
x
n+m= b
m ;
- если все относительные оценки неотрицательные и среди них есть равные нулю, а среди базисных переменных нет искусственных, то задача решена и имеет бесконечное множество решений,
одно из которых вышло в базис (находится в столбце В);
- если все относительные оценки неотрицательные, но среди базисных переменных есть искусственные, то задача решений не имеет;
- если среди относительных
оценок есть отрицательные, то решение задачи неоптимально, необходим переход к
следующему базисному плану (к пункту 3).
3. Из всех отрицательных относительных оценок выбирается наибольшая по модулю. Соответствующий ей
столбец называется
главным. Для определения
главной строки надо поэлементно разделить столбец В на главный столбец
(на нули и отрицательные числа главного столбца не делят). Наименьшее частное
соответствует главной строке. На пересечении главной строки и главного столбца
находится
главный элемент симплекс-таблицы. Это число может быть только
положительным.
Далее необходимо произвести перерасчёт таблицы.
4. В новой таблице переменные главной строки и главного столбца (вместе со своими коэффициентами) меняются местами. Остальные переменные и их коэффициенты переписываются без изменений.
Вместо главного элемента записывается обратное ему число: 1/главный элемент.
Элементы главного столбца старой таблицы делят на (- главный элемент).
Элементы главной строки старой таблицы делят на (главный элемент).
Все остальные элементы пересчитывают по
правилу прямоугольника:из произведения элементов главной диагонали, проходящей через главный элемент, вычитают произведение элементов побочной диагонали и результат делят на главный элемент; получившееся число записывают в соответствующую клетку новой симплекс-таблицы. Если в главной строке или главном столбце есть нули, то
элементы соответствующих этим нулям столбца и строки переписываются без
изменения в новую таблицу.
5. В новой таблице вычисляются значения целевой функции и относительных
оценок. Переход к пункту 2.
Пример 2.Решим следующую задачу симплекс-методом.
Мастер делает мельхиоровые ложки двух видов: без чеканки (Л1) по цене 2 евро и с чеканкой (Л2) по цене 3 евро. За день мастер делает не менее одной ложки. Дневной запас сырья не более 12 дм
3: при этом на ложку вида Л1 идёт 3 дм
3, а на ложку вида Л2 - 2 дм
3 мельхиора.
На какой максимальный доход в день может рассчитывать мастер при соблюдении указанных норм?
Обозначим:
x
1 – количество ложек вида Л1
, x
2 – количество ложек вида Л2
.По условию задачи составим её математическую модель:
доход от продажи ложек вида Л1 составит 2*x
1 (евро);
доход от продажи ложек вида Л2 составит 3*x
1 (евро). Сумма этих чисел равна доходу мастера - целевая функция.
На производство ложек вида Л1 расходуется 3*x
1 дм
3 м мельхиора, а на производство ложек вида Л2 расходуется 2*x
1 дм
3 м , причем мастер не может использовать в день больше 12 дм
3 м - это первое ограничение. Из условия, что мастер в день делает не менее одной ложки, запишем второе ограничение и получим модель задачи:
f(X) = 2x
1 + 3x
2 → max
3x
1+ 2x
2 ≤ 12
x
1 + x
2 ≥ 1
х
1 ≥ 0
х
2 ≥ 0
Для решения задачи симплекс-методом приведём математическую модель к канонической форме:
f(x) = 2x
1 + 3x
2 + 0* x3 + 0* x4 - М* у → max
3x
1 + 2x
2 +
x3 =12
x
1 + x
2 -
x4 +
y =1
x
i ≥0, i = 1 ÷ 4
y ≥ 0.
На основании канонической формы построим начальный базисный план задачи:
Задача не решена, т.к. в базисе есть искусственные переменные, а среди относительных оценок - отрицательные. Среди отрицательных относительных оценокmso-fareast-font-family:Calibri;mso-ansi-language:RU;mso-fareast-language:EN-US;
выбираем наибольшую по модулю (-М-3) - ей соответствует главный столбец; находим главную строку (вторая, т.к.1/1 Отрицательная относительная оценка одна (-3), ей соответствует главный столбец; главная строка - первая, соответственно, главный элемент равен двум (ячейка выделена голубым цветом). Выполнив перерасчёт таблицы, перейдём к новому базисному плану.
Все относительные оценки неотрицательные, в базисе нет искусственных переменных, следовательно, задача решена.
Решение:
X1 = 0 (т.к. эта переменная не вышла в базис), в базис вышла X2 = 6, максимальный доход при таком плане выпуска изделий равен
f(X) = 2*0 + 3*6 = 18 (евро).
Список рекомендуемой литературы1 Кремер Н.Ш.,Путко Б.А. и др. Под ред. проф. Кремера Н.Ш. Исследование операций в экономике.– М: ЮНИТИ, 2002.- 407 с.2 Малик Г.С. Основы экономики и математические методы в планировании/ – М.: Высшая школа, 1988.-
279 с.3 Миркин Б.Г., Фаенсон А.И. Экономико-математические методы в планировании
жилищно-коммунального хозяйства./ – М: Стройиздат,1990. – 137 с.4 Палий И.А. Линейное программирование/ - М: ЭКСМО, 2008. – 255 с.