Симплекс-метод
– это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.
Назначение сервиса
. Сервис предназначен для онлайн решения задач линейного программирования (ЗЛП) симплекс-методом в следующих формах записи:
- в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
- модифицированным симплекс-методом ; в столбцовой форме; в строчечной форме.
Инструкция
. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word
и Excel
.
При этом ограничения типа x i ≥0 не учитывайте. Если в задании для некоторых x i отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом . При решении автоматически определяется использование М-метода
(симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода
.
Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.
| Объем товара Х (в партиях) | Доход G(X) | ||
| 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 |
| 1 | 28 | 30 | 32 |
| 2 | 41 | 42 | 45 |
| 3 | 50 | 55 | 48 |
| 4 | 62 | 64 | 60 |
| 5 | 76 | 76 | 72 |
Алгоритм симплекс-метода
включает следующие этапы:
- Составление первого опорного плана . Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
- Проверка плана на оптимальность
. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить. - Определение ведущих столбца и строки
. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца. - Построение нового опорного плана
. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана-Гаусса .
Если необходимо найти экстремум целевой функции, то речь идет о поиске минимального значения (F(x) → min , см. пример решения минимизации функции) и максимального значения (F(x) → max , см. пример решения максимизации функции)
Экстремальное решение достигается на границе области допустимых решений в одной из вершин угловых точек многоугольника, либо на отрезке между двумя соседними угловыми точками.
Основная теорема линейного программирования
. Если целевая функция ЗЛП достигает экстремального значения в некоторой точке области допустимых решений, то она принимает это значение в угловой точке. Если целевая функция ЗЛП достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой из выпуклой линейной комбинации этих точек.
Суть симплекс-метода
. Движение к точке оптимума осуществляется путем перехода от одной угловой точки к соседней, которая ближе и быстрее приближает к X опт. Такую схему перебора точек, называемую симплекс-метод
, предложил Р. Данцигом.
Угловые точки характеризуются m базисными переменными, поэтому переход от одной угловой точки к соседней возможно осуществить сменой в базисе только одной базисной переменной на переменную из небазиса.
Реализация симплекс-метода в силу различных особенностей и постановок задач ЛП имеет различные модификации .
Построение симплекс-таблиц продолжается до тех пор, пока не будет получено оптимальное решение.
Как с помощью симплекс-таблицы определить, что решение задачи линейного программирования является оптимальным?
Если последняя строка (значения целевой функции) не содержит отрицательных элементов, следовательно, найдет оптимальный план.
Замечание 1
. Если одна из базисных переменных равна нулю, то крайняя точка, соответствующая такому базисному решению – вырожденная. Вырожденность возникает, когда имеется неоднозначность в выборе направляющей строки. Можно вообще не заметить вырожденности задачи, если выбрать другую строку в качестве направляющей. В случае неоднозначности нужно выбирать строку с наименьшим индексом, чтобы избежать зацикливания.
Замечание 2
. Пусть в некоторой крайней точке все симплексные разности неотрицательные D k ³ 0 (k = 1..n+m),т.е. получено оптимальное решение и существует такой А k – небазисный вектор, у которого D k = 0. Тогда максимум достигается по крайней мере в двух точках, т.е. имеет место альтернативный оптимум. Если ввести в базис эту переменную x k , значение целевой функции не изменится.
Замечание 3
. Решение двойственной задачи находится в последней симплексной таблице. Последние m компонент вектора симплексных разностей(в столбцах балансовых переменных) – оптимальное решение двойственной задачи. Значение целевых функций прямой и двойственной задачи в оптимальных точках совпадают.
Замечание 4
. При решении задачи минимизации в базис вводится вектор с наибольшей положительной симплексной разностью. Далее применяется тот же алгоритм, что и для задачи максимизации.
Если задано условие «Необходимо, чтобы сырье III вида было израсходовано полностью», то соответствующее условие представляет собой равенство.
Аналитическое введение в симплекс-метод
Симплексный метод является универсальным методом линейного программирования.
Итак, если мы решаем ЗЛП в канонической форме , то система ограничений – это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений.
Например, пусть дана система
Здесь число уравнений равно 2, а неизвестных – 3, уравнений меньше. Выразим x 1 и x 2 через x 3:
Это общее решение системы. если переменной x 3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x
3 =1 → x
1 =1 → x
2 =6. Имеем (1, 6, 1) – частное решение. Пусть x
3 =2 → x
1 =-3, x
2 = 1, (-3, 1, 2) – другое частное решение. Таких частных решений бесконечно много.
Переменные x
1 и x
2 называются базисными
, а переменная x
3 – не базисная, свободная
.
Совокупность переменных x
1 и x
2 образует базис: Б
(x
1 , x
2). Если x
3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б
(x
1 , x
2).
Базисным называется решение, соответствующее нулевым значениям свободных переменных
.
В качестве базисных можно было взять и другие переменные: (x
1 , x
3) или (x
2 , x
3).
Как переходить от одного базиса Б
(x
1 , x
2) к другому базису Б
(x
1 , x
3)?
Для этого надо переменную x
3 перевести в базисные, а x
2 – в небазисные т. е. в уравнениях надо x
3 выразить через x
2 и подставить в 1-е:
Б
(x
1 , x 3
), таково: (-19/5; 0; 11/5).
Если теперь от базиса Б
(x
1 , x
3) нам захочется перейти к базису Б
(x
2 , x
3), то
Базисное решение, соответствующее базису Б
(x
2 , x
3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б
(x
1 , x
3) – отрицательное x
1 < 0, нас в ЗЛП интересуют только неотрицательные решения.
Если задача ЛП имеет решение, то оно достигается на множестве базисных неотрицательных решений системы ограничений канонической формы.
Поэтому идея симплекс-метода и состоит в последовательном переходе от одного базиса к другому, лучшему с точки зрения значения целевой функции.
Пример
. Решить задачу ЛП.
Функцию F
= x
2 – x
1 → min необходимо минимизировать при заданной системе ограничений:
-2x
1 + x
2 + x
3 = 2
x
1 + x
2 + x
5 = 5
x
1 – 2x
2 + x
4 = 12
x
i ≥ 0, i
= 1, 5
Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x
3 , x
5 , x
4 – как дополнительные.
Запишем ограничения, выбрав базис из переменных Б
{ x
3 , x
4 , x
5 }:
Этому базису соответствует базисное неотрицательное решение
x
1 = 0,
x
2 = 0,
x
3 = 2,
x
4 = 2,
x
5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить
F
через небазисные переменные, в нашем случае это уже сделано:
F
=
x
2 –
x
1 .
Проверим, достигла ли функция
F
своего минимального значения. Для этого базисного решения
F
= 0 – 0 = 0 – значение функции равно 0. Но его можно уменьшить, если
x
1 будет возрастать, т. к. коэффициент в функции при
x
1 отрицателен. Однако при увеличении
x
1 значения переменных
x
4 ,
x
5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная
x
1 не может быть увеличена больше чем до 2, иначе
x
4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе
x
5 – отрицателен. Итак, из анализа равенств следует, что переменную
x
1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б 2 , введя переменную
x
1 в базис вместо
x
4 .
Б
2 {
x
1 ,
x
3 ,
x
5 }.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим
x
1 из второго уравнения и подставим в остальные, в том числе и в функцию.
Базисное решение, соответствующее базису
Б
3 {
х
1 ,
х
2 ,
х
3 }, выписывается (4, 1, 9, 0, 0), и функция принимает значение
F
= -3. Заметим, что значение
F
уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции
, заметим, что улучшить, т. е. уменьшить значение
F
нельзя и только при
x
4 = 0,
x
5 = 0 значение
F
= -3. как только
x
4 ,
x
5 станут положительными, значение
F
только увеличится, т. к. коэффициенты при
x
4 ,
x
5 положительны. Значит, функция
F
достигла своего оптимального значения
F
* = -3. Итак, наименьшее значение
F
, равное -3, достигается при
x
1 * = 4,
x
2 * = 1,
x
3 * = 9,
x
4 * = 0,
x
5 * = 0.
На этом примере очень наглядно продемонстрирована идея метода: постепенно переходя от базиса к базису, при этом всегда обращая внимание на значения целевой функции, которые должны улучшиться, мы приходим к такому базису, в котором значение целевой функции улучшить нельзя, оно оптимально. Заметим, что базисов конечное число, поэтому количество шагов, совершаемых нами до того нужного базиса, конечно.
Если вам понадобится решить задачу линейного программирования с помощью симплекс-таблиц, то наш онлайн сервис вам окажет большую помощь. Симплекс-метод подразумевает последовательный перебор всех вершин области допустимых значений с целью нахождения той вершины, где функция принимает экстремальное значение. На первом этапе находится какое-нибудь решение, которое улучшается на каждом последующем шаге. Такое решение называется базисным. Приведем последовательность действий при решении задачи линейного программирования симплекс-методом:
Первый шаг.
В составленной таблице перво-наперво необходимо просмотреть столбец со свободными членами. Если в нем имеются отрицательные элементы, то необходимо осуществить переход ко второму шагу, есле же нет, то к пятому.
Второй шаг.
На втором шаге необходимо определиться, какую переменную изключить из базиса, а какую включить, для того, что бы произвести перерасчет симплекс-таблицы. Для этого просматриваем столбец со свободными членами и находим в нем отрицательный элемент. Строка с отрицательным элементом будет называться ведущей. В ней находим максимальный по модулю отрицательный элемент, соответсвующий ему столбец – ведомый. Если же среди свободных членов есть отрицательные значения, а в соответсвующей строке нет, то такая таблица не будет иметь решений. Переменая в ведущей строке, находящаяся в столбце свободных членов исключается из базиса, а переменная соответсвующая ведущему столцу включается в базис.
Таблица 1.
| базисные переменные |
Свободные члены в ограничениях | Небазисные переменные | |||||
| x 1 | x 2 | … | x l | … | x n | ||
| x n+1 | b 1 | a 11 | a 12 | … | a 1l | … | a 1n |
| x n+2 | b 2 | a 21 | a 22 | … | a 2l | … | a 2n |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+r | b2 | a r1 | a r2 | … | a rl | … | a rn |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| . | . | . | . | . | . | . | . |
| x n+m | b m | a m1 | a m2 | … | a ml | … | a mn |
| F(x) max | F 0 | -c 1 | -c 2 | … | -c 1 | … | -c n |
Третий шаг.
На третьем шаге пересчитываем всю симплекс-таблицу по специальным формулам, эти формулы можно увидеть, воспользовавшись .
Четвертый шаг.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то к пятому.
Пятый шаг.
Если Вы дошли до пятого шага, значит нашли решение, которое допустимо. Однако, это не значит, что оно оптимально. Оптимальным оно будет только в том случае, если положительны все элементы в F-строке. Если же это не так, то необходимо улучшить решение, для чего находим для следующего перерасчета ведущие строку и столбец по следующему алгоритму. Первоначально, находим минимальное отрицательное число в строке F, исключая значение функции. Столбец с этим числом и будем ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они положительны. Минимальное отношение позволит определить ведущую строку. Вновь пересчитываем таблицу по формулам, т.е. переходим к шагу 3.
Найти наибольшее значение функции
x 1 ≥ 0 x 2 ≥ 0
1. Свободные члены системы должны быть неотрицательными.
Данное условие выполнено.
2. Каждое ограничение системы должно представлять собой уравнение.
| 2 | x 2 | ≤ | 4 | |||
| – | x 2 | ≥ | 1 | |||
| + | ≤ | 8 |
| 2 | x 2 | + | = | 4 | |||||||||||
| – | x 2 | – | S 2 | = | 1 | ||||||||||
| + | + | = | 8 |
S 1 ≥ 0, S 2 ≥ 0, S 3 ≥ 0. Введенные переменные S 1 , S 2 , S 3 , называются балансовыми переменными.
3. Нахождение начального базиса и значения функции F, которое соответствует найденному начальному базису.
Что такое базис?
Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один
и не входит в оставшиеся уравнения системы (при условии, что в правой части уравнения стоит неотрицательное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис.
Переменные, которые не являются базисными, называются свободными.
В чем заключается идея симплекс метода?
Каждому базису соответствует единственное значение функции. Одно из них является наибольшим значением функции F.
Мы будем переходить от одного базиса к другому.
Следующий базис будем выбирать таким образом, чтобы получить значение функции F не меньше имеющегося.
Очевидно, количество возможных базисов для любой задачи число не очень большое.
Следовательно, рано или поздно, ответ будет получен.
Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка таблицы эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (см. таблицу ниже). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент (можно выбрать любой положительный).
Это необходимо для того, чтобы получить значение функции F не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение.
Это необходимо для того, чтобы после преобразования столбец свободных членов остался неотрицательным.
Выбрана строка.
Определен элемент, который будет базисным. Далее считаем.
В нашей системе есть базис?
| 2 | x 2 | + | S 1 | = | 4 | ||||||||||
| – | x 2 | – | S 2 | = | 1 | ||||||||||
| + | + | S 3 | = | 8 |
Базиса нет, т.е. мы не можем начать решение.
Придется его найти. Для этого решим вспомогательную задачу.
Добавим искусственную переменную в то уравнение, где нет базисной переменной.
| 2 | x 2 | + | S 1 | = | 4 | |||||||||||||
| – | x 2 | – | S 2 | + | R 1 | = | 1 | |||||||||||
| + | + | S 3 | = | 8 |
R 1 ≥ 0. Введенная переменная R 1 , называется искусственной переменной.
Введем в рассмотрение функцию W и будем искать ее наименьшее значение.
Алгоритм нахождения наименьшего значения функции W имеет только одно отличие от алгоритма, рассмотренного выше.
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | св. член | Θ |
| 1 | 2 | 1 | 0 | 0 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 0 | -1 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 1 | 0 | 0 | 1 | 0 | 8 | 8: 1 = 8 |
| -1 | 1 | 0 | 1 | 0 | 0 | W – 1 | |
| 0 | 3 | 1 | 1 | 0 | -1 | 3 | |
| 1 | -1 | 0 | -1 | 0 | 1 | 1 | |
| 0 | 2 | 0 | 1 | 1 | -1 | 7 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W – 0 |
Приравниваем свободные переменные нулю. Устно находим значения базисных переменных. (см. таблицу)
Функция W выражена через свободные переменные. Поэтому значение функции W, для данного базиса, можно найти мгновенно. (см. выделенную строку таблицы)
| x 2 = 0 S 2 = 0 R 1 = 0 x 1 = 1 S 1 = 3 S 3 = 7 |
=> W – 0 = 0 => W = 0 |
Среди коэффициентов выделенной строки нет отрицательных. Следовательно, найдено наименьшее значение функции W.
Получен базис без использования искусственной переменной. Что и требовалось.
Столбец, соответствующий искусственной переменной можно вычеркнуть.
В итоге, наша система выглядит следующим образом:
| 3 | x 2 | + | S 1 | + | = | 3 | ||||||||||
| x 1 | – | x 2 | – | S 2 | = | 1 | ||||||||||
| 2 | x 2 | + | + | S 3 | = | 7 |
Если вы уже разобрались с графическим методом решения задач линейного программирования, самое время переходить к симплекс-методу
. В отличие от первого, он практически не имеет ограничений на задачу (любое количество переменных, разные знаки и т.п.) и модифицируется в зависимости от типа задачи (например, М-метод или метод искусственного базиса).
При решении задачи симплекс методом вычисления обычно ведутся (для компактности и наглядности) в таблицах (табличный симплекс-метод), причем последняя таблица с оптимальным решением содержит важную дополнительную информацию: решение двойственной задачи, остатки ресурсов, сведения о дефицитных ресурсах и т.п., которая позволяет провести экономический анализ задачи линейного программирования (см. ниже пример 3).
Примеры решений задач симплекс-методом выложены бесплатно для вашего удобства — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении подобных заданий, перейдите в раздел: решение линейного программирования на заказ.
Решение задач симплекс-методом: примеры онлайн
Задача 1.
Компания производит полки для ванных комнат двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В — 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В — 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?
Составление математической модели и решение ЗЛП симплекс-методом (pdf, 33 Кб)
Задача 2.
Решить задачу линейного программирования симплекс-методом.
Решение симплекс-методом с искусственным базисом (pdf, 45 Кб)
Задача 3.
Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.
- Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
- Определить статус каждого вида сырья и его удельную ценность.
- Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
- Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
- Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.
Решение задачи линейного программирования с экономическим анализом (pdf, 163 Кб)
Задача 4.
Решить задачу линейного программирования симплексным методом:
Решение табличным симплекс-методом с поиском опорного плана (pdf, 44 Кб)
Задача 5.
Решить задачу линейного программирования симплекс-методом:
Решение табличным симплекс-методом (pdf, 47 Кб)
Задача 6.
Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:
Решение ручным симплекс-методом (pdf, 60 Кб)
Задача 7.
Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.
Решение модифицированным симплекс-методом (pdf, 67 Кб)
Задача 8.
Найти оптимальное решение двойственным симплекс-методом
Решение двойственным симплекс-методом (pdf, 43 Кб)
Примеры решений задач по линейному программированию
Методы решения задачи линейного программирования
Опорные решения задачи линейного программирования
Пусть дана задача линейного программирования в канонической форме записи
при условиях
Будем обозначать через множество решений системы (2) – (3). Предположим, что , где – ранг матрицы , – количество уравнений в системе (2).
Из системы векторов-столбцов матрицы выберем некоторую линейно независимую подсистему из векторов . Она существует, так как . Эта система образует базис в . Обозначим через , . Назовем множеством базисных значений
индекса , – базиснойподматрицей
матрицы . Координаты вектора будем называть базисными
, если , и небазисными
в противном случае.
Запишем систему (2) в виде . Разобьем слагаемые левой части на базисные и небазисные, то есть
Определим частное решение этой системы следующим образом. Положим в (4) все небазисные переменные равными нулю . Тогда система (4) примет вид
Назовем (5) базисной подсистемой
системы уравнений (2). Обозначим через вектор, составленный из базисных координат вектора . Тогда систему (2) можно переписать в векторно-матричном виде
Так как подматрица является базисной, она
невырождена. Поэтому система (6) имеет единственное решение . Полученное таким образом частное решение системы (2) назовем опорным решением
прямой задачи линейного программирования, соответствующим базису . (Иногда опорное решение также называют базисным
). Как видим, базису соответствует единственное опорное решение. Очевидно, что число опорных решений конечно.
Для данного базиса определим также и опорное решение двойственной задачи линейного программирования. Напомним, что задача двойственная к канонической имеет вид
при условиях
Запишем систему (8) в виде
Напомним, что множество решений системы (8) обозначается через .
Определим вектор двойственных переменных из условия выполнения базисных ограничений в системе (9) как равенств. Получим следующую систему линейных уравнений:
Обозначим через вектор, составленный из ба-
зисных координат вектора . Тогда систему (10) можно переписать в векторно-матричном виде
Система (11) также имеет единственное решение .
Назовем его опорным
(базисным
) решением
двойственной задачи линейного программирования, соответствующим базису . Это опорное решение также определяется однозначно.
Итак, любому базису соответствуют два вектора – два опорных решения и прямой и двойственной задач линейного программирования, соответственно.
Определим далее следующие разновидности базисов и опорных решений. Если все координаты опорного решения неотрицательны, то базис, которому соответствует это опорное решение, называется допустимым
опорным планом
прямой задачи линейного программирования, а соответствующее тому же базису опорное решение называется псевдопланом
двойственной задачи. Фактически для допустимости базиса достаточно неотрицательности базисных координат . Заметим, что опорный план является допустимым вектором прямой задачи линейного программирования ().
Если опорное решение удовлетворяет всем ограничениям (9) двойственной задачи, то базис, которому соответствует это опорное решение, называется двойственно допустимым
. В этом случае вектор называется опорным планом
двойственной задачи линейного программирования, а соответствующее тому же базису опорное реше-
ние называется псевдопланом
прямой задачи.
Для двойственной допустимости базиса достаточно выполнения только небазисных неравенств . Заметим, что опорный план является допустимым вектором двойственной задачи линейного программирования ().
Разности левых и правых частей неравенств (9) обозначим через , . Тогда двойственную допустимость базиса можно устанавливать, проверяя неотрицательность всех . Заметим, что, как следует непосредственно из определения, все базисные невязки равны нулю ().
Пример решения прямой и двойственной задачи симплекс методом
Поэтому достаточно убедиться в выполнении неравенств для всех .
Теорема 1.
Пусть
и
– опорные решения задачи линейного программирования, соответствующие некоторому базису
, тогда имеет место равенство
.
Доказательство
.
Из определений опорных решений легко получить равенства
откуда и следует справедливость теоремы.
Теорема 2.
(Критерий оптимальности опор-ных решений)
Если базис
одновременно допустим и двойственно допустим, то соответствующие ему опорные решения
и
являются решениями, соответственно, прямой и двойственной задач линейного программирования.
Доказательство.
Справедливость этого утверждения следует из теории двойственности в линейном программировании и теоремы 1.
Теорема 3.
Допустимое решение задачи (1) – (3) является опорным планом задачи тогда и только тогда, когда оно является вершиной выпуклого многогранного множества .
Доказательство.
Пусть – опорный план задачи (1) – (3). Докажем, что – вершина множества .
По определению опорный план –
допустимое опорное решение, соответствующее некоторому базису , то есть –
решениесистемы линейных уравнений относительно переменных
Легко увидеть, что эта система имеет единственное решение. Значит, несущая плоскость грани, содержащей точку ,
имеет размерность 0. Следовательно, – вершина множества .
Обратно. Пусть – вершина множества . Докажем, что – опорный план задачи (1) – (3). Так как – вершина, то она является гранью множества , размерность которой равна нулю. Следовательно, у вектора найдется не менее нулевых компонент, множество номеров которых обозначим .
Таким образом, –
единственное решение системы
где .
Поэтому осталось доказать, что система векторов линейно независима. Предположим противное. Тогда существуют числа не все равные нулю, такие что . Поэтому
Это означает, что система (12) имеет решение, отличное от , что противоречит единственности ее решения. Таким образом, – базис, а вектор – соответствующий ему опорный план задачи (1) – (3). Что и требовалось.
Заметим, что допустимое решение задачи (7), (8) (двойственной задаче (1) – (3)) также является опорным планом тогда и только тогда, когда оно является вершиной допустимого множества .
Дата публикования: 2015-01-10; Прочитано: 695 | Нарушение авторского права страницы
Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.005 с)…
Для определенности считаем, что решается задача на отыскание минимума.
1. Задачу линейного программирования привести к каноническому виду.
После введения добавочных переменных систему уравнений и линейную функцию записываем в виде, который называется расширенной системой:
Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М
– метод, который будет рассмотрен ниже.
2. Определить базисные и свободные переменные.
3. Исходную расширенную систему заносим в первую симплекс – таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной
. В ней указываются коэффициенты функции цели . В левом столбце таблицы записываем основные переменные (базис), в последующих – коэффициенты при свободных переменных. В предпоследнем столбце – свободные члены расширенной системы . Последний столбец подготовлен для оценочных отношений, необходимых для определения базисной переменной на основании соотношения (6.29).
4. Определить возможность решения задачи по значениям согласно теоремам 6.7,…, 6.9.
5. Выбрать разрешающий (опорный) элемент .
Решение производственной задачи табличным симплекс-методом
Если критерий оптимальности не выполнен (не выполнены условия теоремы 6.7 или 6.8), то наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий (опорный) столбец
.
Составляем оценочные отношения каждой строки по следующим правилам:
1 0) , если все и имеют разные знаки;
2 0) , если все и ;
3 0) , если ;
4 0) 0, если и ;
5 0) , если и имеют одинаковые знаки.
Определим . Если конечного минимума нет, то задача не имеет конечного оптимума (). Если минимум конечен, то выбираем строку q
, на которой он достигается (любую, если их несколько), и называем ее разрешающей (опорной) строкой. На пересечении разрешающих строки и столбца находится разрешающий (опорный) элемент .
6 0) Переход к следующей таблице по правилам:
а) в левом столбце записываем новый базис: вместо основной переменной – переменную , т.е. поменяем местами переменные и ;
б) на место опорного элемента поставить 1;
в) на остальных местах опорной строки в новой таблице оставить элементы исходной таблицы;
г) на остальные места в опорном столбце поставить соответствующие элементы исходной таблицы, умноженные на –1;
д) на оставшиеся свободные места элементов , , в новой таблице записать числа , , , которые находятся следующим образом:
Для упрощения вычислений по этим формулам их можно сформулировать в виде «правила прямоугольника»
(рис. 6.8): элементы на диагоналях прямоугольника с вершинами (или , , , , или , , , ) перемножаются (произведение, не содержащее опорного элемента , берется со знаком минус) и полученные произведения складываются;
е) все полученные элементы новой таблицы разделить на опорный элемент .
7 0) По значению элемента определить, найдено ли оптимальное значение целевой функции. В случае отрицательного ответа продолжить решение (возврат к пункту 6).
Рис. 6.8. Правило прямоугольника для определения чисел:
а − , б − , в − .
Рассмотрен алгоритм преобразования симплекс – таблиц для невырожденных допустимых базисных решений, т.е. выполнялась ситуация, описанная теоремой 6.9. Если исходная задача линейного программирования является вырожденной, то в ходе ее решения симплекс – методом могут появиться и вырожденные базисные решения. При этом возможны холостые шаги симплекс – метода, т.е. итерации, на которых f
(x)
не изменяется. Возможно так же и зацикливание, т.е. бесконечная последовательность холостых шагов. Для его предотвращения разработаны специальные алгоритмы – антициклины. Однако в подавляющем большинстве случаев холостые шаги сменяются шагами с убыванием целевой функции и процесс решения завершается в результате конечного числа итераций.
Пример 6.8.
Решить задачу, приведенную в примере 6.7, симплекс методом.
⇐ Предыдущая45678910111213Следующая ⇒
Дата публикования: 2015-01-23; Прочитано: 174 | Нарушение авторского права страницы
Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.002 с)…
Главная >> Пример №3. Симплекс метод. Нахождение наибольшего значения функции (искусственный базис)
Симплекс метод
| — | x 1 | + | x 2 | ≥ | 1 | |
| x 1 | + | 3 | x 2 | ≤ | 15 | |
| — | 2 | x 1 | + | x 2 | ≤ | 4 |
| Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один и не входит в оставшиеся уравнения (при условии, что в правой части уравнения стоит положительное число).
Если в каждом уравнении присутствует базисная переменная, тогда говорят, что в системе присутствует базис. Идея симплекс метода заключается в том, чтобы переходить от одного базиса к другому, получая значение функции, как минимум, не меньше имеющегося (каждому базису соответствует единственное значение функции). Как осуществляется переход от одного базиса к другому? |
| x 1 = 0 x 2 = 0 S 1 = 0 S 2 = 15 S 3 = 4 R 1 = 1 |
=> W = 1 |
| x 1 | x 2 | S 1 | S 2 | S 3 | R 1 | св. член | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | 1: 1 = 1 |
| 1 | 3 | 0 | 1 | 0 | 0 | 15 | 15: 3 = 5 |
| -2 | 1 | 0 | 0 | 1 | 0 | 4 | 4: 1 = 4 |
| 1 | -1 | 1 | 0 | 0 | 0 | W — 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | 1 | |
| 4 | 0 | 3 | 1 | 0 | -3 | 12 | |
| -1 | 0 | 1 | 0 | 1 | -1 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 1 | W — 0 |
| x 1 | x 2 | S 1 | S 2 | S 3 | св. член | Θ |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 4 | 0 | 3 | 1 | 0 | 12 | 12: 4 = 3 |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F — 1 | |
| -1 | 1 | -1 | 0 | 0 | 1 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| -1 | 0 | 1 | 0 | 1 | 3 | |
| 4 | 0 | 1 | 0 | 0 | F — 1 | |
| 0 | 1 | -1/4 | 1/4 | 0 | 4 | |
| 1 | 0 | 3/4 | 1/4 | 0 | 3 | |
| 0 | 0 | 7/4 | 1/4 | 1 | 6 | |
| 0 | 0 | -2 | -1 | 0 | F — 13 |
| S 1 = 0 S 2 = 0 x 1 = 3 x 2 = 4 S 3 = 6 |
=> F — 13 = 0 => F = 13 |
Среди коэффициентов выделенной строки нет положительных. Следовательно, найдено наибольшее значение функции F.
Ответ:
x 1 = 3 x 2 = 4
F max = 13
Перейти к решению своей задачи
© 2010-2018, по всем вопросам пишите по адресу [email protected]
Условие задачи
Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс.
Симплексный метод решения ЗЛП
руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.
К прямой задаче планирования товарооборота, решаемой симплекс методом
, составить двойственную задачу
линейного программирования.
Установить сопряженные пары переменных
прямой и двойственной задачи.
Согласно сопряженным парам переменных из решения прямой задачи получить решение двойственной задачи
, в которой производится оценка ресурсов
, затраченных на продажу товаров.
Решение задачи симплекс методом
Пусть x 1 , x 2 , x 3 — количество реализованных товаров, в тыс. руб., 1, 2, 3 — ей групп, соответственно. Тогда математическая модель задачи имеет вид:
F = 4·x 1 + 5·x 2 + 4·x 3 ->max
Решаем симплекс методом.
Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.
В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.
Данные заносим в симплекс таблицу
Симплекс таблица № 1
Целевая функция:
0 · 240 + 0 · 200 + 0 · 160 = 0
Вычисляем оценки по формуле:
Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 – 4 = – 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 – 5 = – 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 – 4 = – 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 – 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 – 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 – 0 = 0
Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:
Вводим переменную x 2 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .
= 26.667
Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса
3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2
Вычисляем:
Получаем новую таблицу:
Симплекс таблица № 2
Целевая функция:
0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3
Вычисляем оценки по формуле:
Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 – 4 = – 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 – 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 – 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 – 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 – 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 – 0 = 5/6
Поскольку есть отрицательная оценка Δ 1 = – 2/3, то план не оптимален.
Вводим переменную x 1 в базис.
Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .
Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса
3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3
Вычисляем:
Получаем новую таблицу:
Симплекс таблица № 3
Целевая функция:
0 · 160 + 0 · 40 + 4 · 40 = 160
Вычисляем оценки по формуле:
Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 – 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 – 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 – 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 – 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 – 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 – 0 = 1
Поскольку отрицательных оценок нет, то план оптимален.
Решение задачи:
Ответ
x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160
То есть необходимо реализовать товар первого вида в объеме 40 тыс.
руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.
Решение двойственной задачи
Двойственная задача имеет вид:
Z = 240·y 1 + 200·y 2 + 160·y 3 ->min
Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.
Сопряженные пары переменных прямой и двойственной задач имеют вид:
Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:
Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;
Ответ
y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;
Симплексный метод – это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной точки (базисного решения) к другой. При этом значение целевой функции улучшается.
Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан симплекс-метод.
Симплекс – это выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).
Например, линия бюджетных ограничений делит блага на доступные и недоступные.
Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число итераций (шагов), кроме случаев «зацикливания».
Алгоритм симплексного метода состоит из ряда этапов.
Первый этап. Строится исходная оптимизационная модель. Далее исходная матрица условий преобразуется в приведенную каноническую форму, которая среди всех других канонических форм выделяется тем, что:
а) правые части условий (свободные члены bi) являются величинами неотрицательными;
б) сами условия являются равенствами;
в) матрица условий содержит полную единичную подматрицу.
Если свободные члены отрицательные, то обе части неравенства умножаются на — 1, а знак неравенства меняется на противоположный. Для преобразования неравенств в равенства вводятся дополнительные переменные, которые, обычно, обозначают объем недоиспользованных ресурсов. В этом их экономический смысл.
Наконец, если после добавления дополнительных переменных, матрица условий не содержит полную единичную подматрицу, то вводятся искусственные переменные, которые не имеют никакого экономического смысла. Они вводятся исключительно для того, чтобы получить единичную подматрицу и начать процесс решения задачи при помощи симплексного метода.
В оптимальном решении задачи все искусственные переменные (ИП) должны быть равными нулю. Для этого вводят искусственные переменные в целевую функцию задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение искусственной переменной будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.
Второй этап. Строится исходная симплекс-таблица и отыскивается некоторое начальное базисное решение. Множество переменных, образующих единичную подматрицу, принимается за начальное базисное решение. Значения этих переменных равны свободным членам. Все остальные внебазисные переменные равны нулю.
Третий этап. Проверка базисного решения на оптимальность осуществляется при помощи специальных оценок коэффициентов целевой функции. Если все оценки коэффициентов целевой функции отрицательны или равны нулю, то имеющееся базисное решение – оптимальное. Если хотя бы одна оценка коэффициента целевой функции больше нуля, то имеющееся базисное решение не является оптимальным и должно быть улучшено.
Четвертый этап. Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличивает целевую функцию. При решении задач на максимум прибыли в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по максимальному положительному значению оценки коэффициента целевой функции.
Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом.
Для отыскания генеральной строки все свободные члены (ресурсы) делятся на соответствующие элементы генерального столбца (норма расхода ресурса на единицу изделия). Из полученных результатов выбирается наименьший. Соответствующая ему строка на данной итерации называется генеральной. Она соответствует ресурсу, который лимитирует производство на данной итерации.
Элемент симплексной таблицы, находящийся на пересечении генеральных столбца и строки, называется генеральным элементом.
Затем все элементы генеральной строки (включая свободный член), делятся на генеральный элемент. В результате этой операции генеральный элемент становится равным единице. Далее необходимо, чтобы все другие элементы генерального столбца стали бы равны нулю, т.е. генеральный столбец должен стать единичным. Все строки (кроме генеральной) преобразуются следующим образом. Полученные элементы новой строки умножаются на соответствующий элемент генерального столбца и полученное произведение вычитается из элементов старой строки.
Значения новых базисных переменных получим в соответствующих ячейках столбца свободных членов.
Пятый этап. Полученное базисное решение проверяется на оптимальность (см. третий этап). Если оно оптимально, то вычисления прекращаются. В противном случае необходимо найти новое базисное решение (четвертый этап) и т.
Симплекс метод
Пример решения оптимизационных задач линейного программирования симплексным методом
Пусть необходимо найти оптимальный план производства двух видов продукции (х1 и х2).
Исходные данные:
Построим оптимизационную модель
– ограничение по ресурсу А;
– ограничение по ресурсу В.
Приведем задачу к приведенной канонической форме. Для этого достаточно ввести дополнительные переменные Х3 и Х4. В результате неравенства преобразуются в строгие равенства.
Построим исходную симплексную таблицу и найдем начальное базисное решение. Им будут дополнительные переменные, т. к. им соответствует единичная подматрица.
1-я итерация. Находим генеральный столбец и генеральную строку:
Генеральный элемент равняется 5.
2-я итерация. Найденное базисное решение не является оптимальным, т.к. cтрока оценок (Fj-Cj) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:
max (0,0.3,-1.4,0) = 0.2
Найденное решение оптимально, так как все специальные оценки целевой функции Fj – Cj равны нулю или отрицательны. F(x)=29 x1=2; x2=5.
Универсальный метод решения задач ЛП называется симплекс-методом. Применение этого метода и его наиболее часто встречающейся модификации – двухфазного симплекс-метода.
При графическом методе решения задач ЛП мы фактически из множества вершин, принадлежащих границе множества решений системы неравенств, выбрали такую вершину, в которой значение целевой функции достигало максимума (минимума). В случае двух переменных этот метод совершенно нагляден и позволяет быстро находить решение задачи.
Если в задаче три и более переменных, а в реальных экономических задачах как раз такая ситуация, трудно представить наглядно область решений системы ограничений. Такие задачи решаются с помощью симплекс-метода
или методом последовательных улучшений. Идея метода проста и заключается в следующем.
По определенному правилу находится первоначальный опорный план (некоторая вершина области ограничений). Проверяется, является ли план оптимальным. Если да, то задача решена. Если нет, то переходим к другому улучшенному плану – к другой вершине. значение целевой функции на этом плане (в этой вершине) заведомо лучше, чем в предыдущей. Алгоритм перехода осуществляется с помощью некоторого вычислительного шага, который удобно записывать в виде таблиц, называемых симплекс-таблицами
. Так как вершин конечное число, то за конечное число шагов мы приходим к оптимальному решению.
Рассмотрим симплексный метод на конкретном примере задачи о составлении плана.
Еще раз заметим, что симплекс-метод применим для решения канонических задач ЛП, приведенных к специальному виду, т. е. имеющих базис, положительные правые части и целевую функцию, выраженную через небазисные переменные. Если задача не приведена к специальному виду, то нужны дополнительные шаги, о которых мы поговорим позже.
Рассмотрим задачу о плане производства, предварительно построив модель и приведя ее к специальному виду.
Задача.
Для изготовления изделий А
и В
склад может отпустить сырья не более 80 единиц. Причем на изготовление изделия А
расходуется две единицы, а изделия В
– одна единица сырья. Требуется спланировать производство так, чтобы была обеспечена наибольшая прибыль, если изделий А
требуется изготовить не более 50 шт., а изделий В
– не более 40 шт. Причем, прибыль от реализации одного изделия А
– 5 руб., а от В
– 3 руб.
Построим математическую модель, обозначив за х
1 количество изделий А в плане, за х
2 – количество изделий В
. тогда система ограничений будет выглядеть следующим образом:
x 1 ≤50
x 2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max
Приведем задачу к каноническому виду , введя дополнительные переменные:
x 1 +x 3 =50
x 2 +x 4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max
-F = -5x 1 – 3x 2 → min.
Эта задача имеет специальный вид (с базисом, правые части неотрицательны). Ее можно решить симплекс-методом.
I
этап.
Запись задачи в симплекс-таблицу. Между системой ограничений задачи (3.10) и симплекс-таблицей взаимно-однозначное соответствие. Строчек в таблице столько, сколько равенств в системе ограничений, а столбцов – столько, сколько свободных переменных. Базисные переменные заполняют первый столбец, свободные – верхнюю строку таблицы. Нижняя строка называется индексной, в ней записываются коэффициенты при переменных в целевой функции. В правом нижнем углу первоначально записывается 0, если в функции нет свободного члена; если есть, то записываем его с противоположным знаком. На этом месте (в правом нижнем углу) будет значение целевой функции, которое при переходе от одной таблицы к другой должно увеличиваться по модулю. Итак, нашей системе ограничений соответствует таблица 3.4, и можно переходить ко II этапу решения.
Таблица 3.4
II
этап
. Проверка опорного плана на оптимальность.
Данной таблице 3.4 соответствует следующий опорный план:
(х
1 , х
2 , х
3 , х
4 , х
5) = (0, 0, 50, 40, 80).
Свободные переменные х
1 , х
2 равны 0; х
1 = 0, х
2 = 0. А базисные переменные х
3 , х
4 , х
5 принимают значения х
3 = 50, х
4 = 40, х
5 = 80 – из столбца свободных членов. Значение целевой функции:
–F
= – 5х
1 – 3х
2 = -5 · 0 – 3 · 0 = 0.
Наша задача – проверить, является ли данный опорный план оптимальным. для этого необходимо просмотреть индексную строку – строку целевой функции F
.
Возможны различные ситуации.
1. В индексной F
-строке нет отрицательных элементов. Значит, план оптимален, можно выписать решение задачи. Целевая функция достигла своего оптимального значения, равного числу, стоящему в правом нижнем углу, взятому с противоположным знаком. Переходим к IV этапу.
2. В индексной строке есть хотя бы один отрицательный элемент, в столбце которого нет положительных. Тогда делаем вывод о том, что целевая функция F
→∞ неограниченно убывает.
3. В индексной строке есть отрицательный элемент, в столбце которого есть хотя бы один положительный. Тогда переходим к следующему III
этапу. пересчитываем таблицу, улучшая опорный план.
III
этап
. Улучшение опорного плана.
Из отрицательных элементов индексной F
-строки выберем наибольший по модулю, назовем соответствующий ему столбец разрешающим и пометим “”.
Чтобы выбрать разрешающую строку, необходимо вычислить отношения элементов столбца свободных членов только
к положительным
элементам разрешающего столбца. Выбрать из полученных отношений минимальное. Соответствующий элемент, на котором достигается минимум, называется разрешающим. Будем выделять его квадратом.
В нашем примере, элемент 2 – разрешающий. Строка, соответствующая этому элементу, тоже называется разрешающей (табл. 3.5).
Таблица 3.5
Выбрав разрешающий элемент, делаем перечет таблицы по правилам:
1. В новой таблице таких же размеров, что и ранее, переменные разрешающей строки и столбца меняются местами, что соответствует переходу к новому базису. В нашем примере: х
1 входит в базис, вместо х
5 , которая выходит из базиса и теперь свободная (табл. 3.6).
Таблица 3.6
2. На месте разрешающего элемента 2 записываем обратное ему число ½.
3. Элементы разрешающей строки делим на разрешающий элемент.
4. Элементы разрешающего столбца делим на разрешающий элемент и записываем с противоположным знаком.
5. Чтобы заполнить оставшиеся элементы таблицы 3.6, осуществляем пересчет по правилу прямоугольника. Пусть мы хотим посчитать элемент, стоящий на месте 50.
Соединяем этот элемент мысленно с разрешающим, находим произведение, вычитаем произведение элементов, находящихся на другой диагонали получившегося прямоугольника. Разность делим на разрешающий элемент.
Итак, . Записываем 10 на место, где было 50. Аналогично:
,
, ,
.
Таблица 3.7
Имеем новую таблицу 3.7, базисными переменными теперь являются переменные {x 3 ,x 4 ,x 1 }. Значение целевой функции стало равно -200, т.е. уменьшилось. Чтобы проверить данное базисное решение на оптимальность надо перейти опять ко II этапу. Процесс, очевидно, конечен, критерием остановки являются пункт 1 и 2 II этапа.
Доведем решение задачи до конца. Для этого проверим индексную строку и, увидев в ней отрицательный элемент -½, назовем соответствующий ему столбец разрешающим и, согласно III этапу, пересчитаем таблицу. Составив отношения и выбрав среди них минимальное = 40, определили разрешающий элемент 1. теперь пересчет осуществляем согласно правилам 2-5.
Таблица 3.8
После пересчета таблицы убеждаемся, что в индексной строке нет отрицательных элементов, следовательно, задача решена, базисный план оптимален.
IV
этап
. Выписывание оптимального решения.
Если симплекс-метод остановился согласно пункту 1 II этапа, то решение задачи выписывается следующим образом. Базисные переменные принимают значения столбца свободных членов соответственно. В нашем примере х
3 = 30, х
2 = 40, х
1 = 20. Свободные переменные равны 0, х
5 = 0, х
4 = 0. Целевая функция принимает значение последнего элемента столбца свободных членов с противоположным знаком: –F
= -220 → F
= 220, в нашем примере функция исследовалась на min, и первоначально F
→ max, поэтому фактически знак поменялся дважды. Итак, х
* = (20, 40, 30, 0, 0), F
* = 220. Ответ к задаче:
Необходимо в план выпуска включить 20 изделий типа А
, 40 изделий типа В, при этом прибыль будет максимальной и будет равна 220 руб.
В конце этого параграфа приведем блок-схему алгоритма симплекс-метода, которая в точности повторяет этапы, но, возможно, для некоторых читателей будет более удобна в пользовании, т. к. стрелочки указывают четкую направленность действий.
Ссылки над прямоугольниками в блок-схеме показывают, к какому этапу или подпункту относится соответствующая группа преобразований. правило нахождения первоначального опорного плана будет сформулировано в пункте 3.7.
Пример
. Решить следующую задачу ЛП в канонической форме симплекс-методом.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → min
x 1 +x 4 =20
x 2 +x 5 =50
x 3 +x 6 =30
x 4 +x 5 +x 6 =60
x i ≥ 0, i = 1,…,6
Говорят, что задача ЛП имеет каноническую форму, если все ограничения (кроме условий неотрицательности переменных) имеют вид равенств, а все свободные члены неотрицательны. Так что мы имеем задачу в канонической форме.
Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность.
Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число “шагов” мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).
Таким образом, идея симплекс-метода основывается на трех свойствах задачи ЛП.
Решение.
Чтобы найти начальное допустимое базисное решение, т.е. чтобы определить базисные переменные, систему (5.6) нужно привести к “диагональному” виду. Применяя метод Гаусса (метод последовательного исключения неизвестных), получаем из (5.6):
x 2 +x 1 +x 3 =40
x 4 +x 1 =20
x 5 -x 1 -x 3 =10
x 6 +x 3 =30
Следовательно, базисными являются переменные
x 2 , x 4 , x 5 , x 6 ,
им придаем значения, равные
свободным членам соответствующих строк:
x 2 =40, x 4 =20, x 5 =10, x 6 =30,
. Переменные
x 1
и
x 3
являются небазисными:
x 1 =0, x 3 =0
.
Построим начальное допустимое базисное решение
x 0 = (0,40,0,20,10,30) (5.9)
Для проверки на оптимальность найденного решения
x 0
нужно из целевой функции исключить базисные переменные (с помощью системы (5.8)) и построить специальную симплекс таблицу.
После исключения переменных целевую функцию удобно записать в виде:
f(x) = -7x 1 – 14x 3 +880 (5.10)
Теперь при помощи (5.8) –(5.10) составляем начальную симплекс-таблицу:
В нулевую строчку записаны коэффициенты с обратным знаком соответствующих переменных при целевой функции. Критерий оптимальности (для задачи на поиск минимума): допустимое базисное решение(
x 0
) оптимально, если в нулевой строчке нет ни одного строго положительного числа (не считая значения целевой функции (880)). Это правило распространяется и на следующие итерации (таблицы). Элементы нулевой строки будем называть оценками столбцов.
Так что начальное допустимое базисное решение (5.9) неоптимально:
7>0, 14>0
.
В нулевом столбике записаны значения базисных переменных. Они обязательно должны быть неотрицательными (см. уравнение (5.7)).
От первой по четвертую строки написаны коэффициенты переменных из системы (5.8).
Так как
x 0
неоптимально, то надо перейти к другой вершине многогранника допустимых решений (построить новое д.б.р.). Для этого нужно найти ведущий элемент и провести определенное преобразование (симплексное преобразование).
Сначала находим ведущий элемент таблицы, который стоит в пересечении ведущего столбика (столбец с наибольшей положительной оценкой) и ведущей строки (строки, соответствующей минимальному соотношению элементов нулевого столбика к соответствующим элементам (строго положительным) ведущего столбика).
В таблице 1 ведущий столбик – третий столбик, и ведущая строка – четвертая строка
(min{40/1,30/1}=30/1)
обозначены стрелками, а ведущий элемент – кружочком. Ведущий элемент показывает, что базисную переменную
x 6
нужно заменить на небазисную
x 3
. Тогда новыми базисными переменными будут
x 2 , x 3 , x 4 ,
x 5 ,
, а небазисными –
x 1 , x 6 ,
. Это и означает переход к новой вершине многогранника допустимых решений. Чтобы найти значения координат нового допустимого базисного решения
x 00
нужно строить новую симплекс-таблицу и провести в ней элементарные преобразования:
а)
все элементы ведущей строки поделить на ведущий элемент, превратив этим самым ведущий элемент в 1 (для простоты выкладок);
б)
с помощью ведущего элемента (равного 1) все элементы ведущего столбика превратить в нули (аналогично методу исключения неизвестных);
В результате в нулевом столбце получены значения новых базисных переменных
x 2 , x 3 , x 4 , x 5 ,
(см. таблицу 2) – базисные компоненты новой вершины
x 00
(небазисные компоненты
x 1 =0, x 6 =0,
).
Как показывает таблица 2, новое базисное решение
x 00 =(0,10,30,20,40,0)
неоптимально (в нулевой строке есть неотрицательная оценка 7). Поэтому с ведущим элементом 1 (см. таблицу 2) строим новую симплекс-таблицу, т.е. строим новое допустимое базисное решение
Таблице 3 соответствует допустимое базисное решение
x 000 =(10,0,30,10,50,0)
и оно оптимально, т.к. в нулевой строчке нет положительных оценок. Поэтому
f(x 000)=390
есть минимальное значение целевой функции.
Ответ:
x 000 =(10, 0, 30, 10, 50, 0)
– точка минимума,
f(x 000)=390
.
Условно стандартная задача линейного программирования
Необходимо выполнить в указанном порядке следующие задания.
- Найти оптимальный план прямой задачи:
а) графическим методом ;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса). - Построить двойственную задачу .
- Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
- Найти оптимальный план двойственной задачи по первой теореме двойственности , используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п. 1б). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
- Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п. 1а).
- Найти оптимальное целочисленное решение:
а) графическим методом ;
б) Методом Гомори .
Сравнить значения функций целочисленного и нецелочисленного решений
Вопросы для самоконтроля
- Как строится симплекс-таблица?
- Как отражается смена базиса в таблице?
- Сформулируйте критерий остановки симплекс-метода.
- Как организовать пересчет таблицы?
- С какой строки удобно начинать пересчет таблицы?
