Симплексный метод решения ЗЛП
Симплекс-метод — это итеративный процесс направленного решения системы уравнений по шагам, который начинается с опорного решения и в поисках лучшего варианта движется по угловым точкам области допустимого решения, улучшающих значение целевой функции до тех пор, пока целевая функция не достигнет оптимального значения.
- в виде симплексной таблицы (метод жордановых преобразований); базовой форме записи;
- модифицированным симплекс-методом; в столбцовой форме; в строчечной форме.
- Шаг №1
- Шаг №2
- Видеоинструкция
- Оформление Word
- Также решают
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word и Excel . При этом ограничения типа xi≥0 не учитывайте. Если в задании для некоторых xi отсутствуют ограничения, то ЗЛП необходимо привести к КЗЛП, или воспользоваться этим сервисом. При решении автоматически определяется использование М-метода (симплекс-метод с искусственным базисом) и двухэтапного симплекс-метода.
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Задачи динамического программирования
Распределить 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 |
- Составление первого опорного плана. Переход к канонической форме задачи линейного программирования путем введения неотрицательных дополнительных балансовых переменных.
- Проверка плана на оптимальность. Если найдется хотя бы один коэффициент индексной строки меньше нуля, то план не оптимальный, и его необходимо улучшить.
- Определение ведущих столбца и строки. Из отрицательных коэффициентов индексной строки выбирается наибольший по абсолютной величине. Затем элементы столбца свободных членов симплексной таблицы делит на элементы того же знака ведущего столбца.
- Построение нового опорного плана. Переход к новому плану осуществляется в результате пересчета симплексной таблицы методом Жордана—Гаусса.
Аналитическое введение в симплекс-метод
Симплексный метод является универсальным методом линейного программирования. Итак, если мы решаем ЗЛП в канонической форме, то система ограничений — это обычная система линейных уравнений. При решении задач ЛП получаются системы линейных уравнений, имеющие, как правило, бесконечно много решений. Например, пусть дана система
Здесь число уравнений равно 2, а неизвестных — 3, уравнений меньше. Выразим x1 и x2 через x3 :
Это общее решение системы. если переменной x3 придавать произвольные числовые значения, то будем находить частные решения системы. Например, x3=1 → x1=1 → x2=6. Имеем (1, 6, 1) — частное решение. Пусть x3=2 → x1=-3, x2= 1, (-3, 1, 2) — другое частное решение. Таких частных решений бесконечно много. Переменные x1 и x2 называются базисными, а переменная x3 — не базисная, свободная. Совокупность переменных x1 и x2 образует базис: Б (x1, x2). Если x3 = 0, то полученное частное решение (5, 11, 0) называется базисным решением, соответствующим базису Б (x1, x2). Базисным называется решение, соответствующее нулевым значениям свободных переменных.
В качестве базисных можно было взять и другие переменные: (x1, x3) или (x2, x3).
Как переходить от одного базиса Б(x1, x2) к другому базису Б(x1, x3)?
Для этого надо переменную x3 перевести в базисные, а x2 — в небазисные т. е. в уравнениях надо x3 выразить через x2 и подставить в 1-е: Базисное решение, соответствующее базису Б (x1, x3), таково: (-19/5; 0; 11/5). Если теперь от базиса Б (x1, x3) нам захочется перейти к базису Б (x2, x3), то
Базисное решение, соответствующее базису Б (x2, x3): (0;19/4; 7/8).
Из трех найденных базисных решений решение, соответствующее базису Б (x1, x3) — отрицательное x1 < 0, нас в ЗЛП интересуют только неотрицательные решения. Если задача ЛП имеет решение, то оно достигается на множестве базисных неотрицательных решений системы ограничений канонической формы. Поэтому идея симплекс-метода и состоит в последовательном переходе от одного базиса к другому, лучшему с точки зрения значения целевой функции. Пример . Решить задачу ЛП. Функцию F= x2 — x1 → min необходимо минимизировать при заданной системе ограничений:
-2x1 + x2 + x3 = 2
x1 + x2 + x5 = 5
x1 — 2x2 + x4 = 12
xi ≥ 0, i = 1, 5 Эти ограничения могут рассматриваться как произошедшие из неравенств, а переменные x3, x5, x4 — как дополнительные.
Запишем ограничения, выбрав базис из переменных Б< x3, , x4, x5>: Этому базису соответствует базисное неотрицательное решение
x1 = 0, x2 = 0, x3 = 2, x4 = 2, x5 = 5 или (0, 0, 2, 2, 5).
Теперь нужно выразить F через небазисные переменные, в нашем случае это уже сделано: F= x2 — x1.
Проверим, достигла ли функция F своего минимального значения. Для этого базисного решения F= 0 — 0 = 0 — значение функции равно 0. Но его можно уменьшить, если x1 будет возрастать, т. к. коэффициент в функции при x1 отрицателен. Однако при увеличении x1 значения переменных x4, x5 уменьшаются (смотрите второе и третье равенство системы ограничений). Переменная x1 не может быть увеличена больше чем до 2, иначе x4 станет отрицательной (ввиду равенства 2), и не больше, чем до 5, иначе x5 — отрицателен. Итак, из анализа равенств следует, что переменную x1 можно увеличить до 2, при этом значение функции уменьшится.
Перейдем к новому базису Б2, введя переменную x1 в базис вместо x4.
Б2x1, x3, x5>.
Выразим эти базисные переменные через небазисные. Для этого сначала выразим x1 из второго уравнения и подставим в остальные, в том числе и в функцию. Имеем:
F = -2 — x2 + x4.
Базисное решение, соответствующее базису Б2x1, x3, x5>, имеет вид (2, 0, 6, 0, 3), и функция принимает значение F= -2 в этом базисе.
Значение функции можно и дальше уменьшать, увеличивая x2. Однако, глядя на систему, x2 можно увеличивать лишь до 1, т. к. иначе из последнего равенства x5 = 3 — 3x2 + x4 следует, что при x2 > 1 x5 станет отрицательной. А у нас все переменные в ЗЛП предполагаются неотрицательными. Остальные уравнения системы не дают ограничений на x2. Поэтому увеличим x2 до 1, введя его в базис вместо x5: Б3x1, x2, x3>.
Выразим x2 через x5 и подставим во все уравнения:
Базисное решение, соответствующее базису Б3х1, х2, х3>, выписывается (4, 1, 9, 0, 0), и функция принимает значение F= -3. Заметим, что значение F уменьшилось, т. е. улучшилось по сравнению с предыдущим базисом.
Посмотрев на вид целевой функции , заметим, что улучшить, т. е. уменьшить значение F нельзя и только при x4 = 0, x5 = 0 значение F= -3. как только x4, x5 станут положительными, значение F только увеличится, т. к. коэффициенты при x4, x5 положительны. Значит, функция F достигла своего оптимального значения F* = -3. Итак, наименьшее значение F, равное -3, достигается при x1* = 4, x2* = 1, x3* = 9, x4* = 0, x5* = 0. На этом примере очень наглядно продемонстрирована идея метода: постепенно переходя от базиса к базису, при этом всегда обращая внимание на значения целевой функции, которые должны улучшиться, мы приходим к такому базису, в котором значение целевой функции улучшить нельзя, оно оптимально. Заметим, что базисов конечное число, поэтому количество шагов, совершаемых нами до того нужного базиса, конечно.
Двойственный симплексный метод
Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых bi могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».
Инструкция для решения задач двойственным симплекс-методом. Выберите количество переменных и количество строк (количество ограничений), нажмите Далее . Полученное решение сохраняется в файле Word . При этом ограничения типа xi≥0 не учитывайте.
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Задачи динамического программирования
Распределить 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 |
- Составление псевдоплана. Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
- Проверка плана на оптимальность. Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом.
- Выбор ведущих строки и столбца. Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
- Расчет нового опорного плана. Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса. Далее переход к этапу 2.
Алгоритм двойственного симплекс-метода
Пример решения Р-методом
Условие задачи. Предприятию необходимо выпустить по плану продукции А1– 500 единиц, А2– 300 единиц, А3– 450 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P – метода.
| Матрица затрат времени на производство видов продукции g – го вида A=(aig) | ||||
| Машины | Виды продукции | Ресурс времени машин | ||
| А1 | А2 | А3 | ||
| 1 | 2 | 3 | 3 | 1500 |
| 2 | 5 | 4 | 1 | 1000 |
| План выпуска продукции | 500 | 300 | 450 | |
Составим математическую модель задачи.
2x11+ 3x12+3x13≤ 1500
5x21+ 4x22+x23≤ 1000
x11+ x21≥ 500
x12+ x22≥ 300
x13+ x23≥ 450
Целевая функция:
2x11+ 3x12+3x13+ 5x21+ 4x22+x23→ min
Запишем в виде, решаемом Р-методом.
2x11+ 3x12+3x13≤ 1500
5x21+ 4x22+x23≤ 1000
-x11 -x21≤ -500
-x12-x22≤ -300
-x13-x23≤ -450
Определим минимальное значение целевой функции F(X) = 2x1+3x2+3x3+5x4+4x5+x6при следующих условиях-ограничений.
2x1+3x2+3x3≤1500
5x4+4x5+x6≤1000
-x1-x4≤-500
-x2-x5≤-300
-x3-x6≤-450
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x1+ 3x2+ 3x3+ 0x4+ 0x5+ 0x6+ 1x7+ 0x8+ 0x9+ 0x10+ 0x11= 1500
0x1+ 0x2+ 0x3+ 5x4+ 4x5+ 1x6+ 0x7+ 1x8+ 0x9+ 0x10+ 0x11= 1000
-1x1+ 0x2+ 0x3-1x4+ 0x5+ 0x6+ 0x7+ 0x8+ 1x9+ 0x10+ 0x11= -500
0x1-1x2+ 0x3+ 0x4-1x5+ 0x6+ 0x7+ 0x8+ 0x9+ 1x10+ 0x11= -300
0x1+ 0x2-1x3+ 0x4+ 0x5-1x6+ 0x7+ 0x8+ 0x9+ 0x10+ 1x11= -450
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:
| 2 | 3 | 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 5 | 4 | 1 | 0 | 1 | 0 | 0 | 0 |
| -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 |
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x7, x8, x9, x10, x11,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0,1500,1000,-500,-300,-450)
| План | Базис | В | x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 |
| 0 | x7 | 1500 | 2 | 3 | 3 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| x8 | 1000 | 0 | 0 | 0 | 5 | 4 | 1 | 0 | 1 | 0 | 0 | 0 | |
| x9 | -500 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| x10 | -300 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | 0 | |
| x11 | -450 | 0 | 0 | -1 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 1 | |
| Индексная строка | F(X0) | 0 | -2 | -3 | -3 | -5 | -4 | -1 | 0 | 0 | 0 | 0 | 0 |
| θ | 2 | 5 |
Посмотреть все итерации Оптимальный план можно записать так: x5 = 133.33, x8 = 16.67, x1 = 500, x2 = 166.67, x6 = 450
F(X) = 2*500 + 3*166.67 + 4*133.33 + 1*450 = 2483.33 Пример №1 . Предприятию необходимо выпустить по плану продукции, не менее, чем: А 1 — 500 единиц, А2 – 300 единиц, А 3 – 450 единиц. Каждый вид изделия может производиться на двух машинах. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Ресурс времени каждой машины приведен справа от таблицы. Записать модель исследуемой операции в форме, допускающей использование Р-метода. Решить задачу Р-методом. Пример №2 . Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в 2 ед. вещества В и в 3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.
Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.