Решение задач линейного программирования
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X) . Также имеется возможность составить двойственную задачу.
- Переход к КЗЛП. Любая ЗЛП вида ax ≤ b , ax ≥ b , ax = b ( F(X) → extr ) сводится к виду ax = b , F(X) → max ;
- Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b , F(X) → max ;
- Решение симплексным методом;
- Шаг №1
- Шаг №2
- Видеоинструкция
- Оформление Word
Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .
Переход от задачи минимизации целевой функции к задаче максимизации
Задача минимизации целевой функции F(X) легко может быть сведена к задаче максимизации функции F*(X) при тех же ограничениях путем введения функции: F*(X) = -F(X) . Обе задачи имеют одно и то же решение X*, и при этом min(F(X)) = -max(F*(X)) .
Проиллюстрируем этот факт графически:
| F(x) → min | F(x) → max |
Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).
Ведущий (разрешающий) элемент – коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка – строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец – столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).
Переменные x1, …, xm, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (xm+1,…, xn) называются небазисными или независимыми переменными.
Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных xj≥0, что эквивалентно условию неотрицательности bj≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел bj есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.
Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x1 + 2x2 — 2x3 → min при ограничениях:
4x1 + 3x2 — x3≤10
— 2x2 + 5x3≥3
x1 + 2x3=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x4; во втором неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус.
4x1 + 3x2-1x3 + 1x4 + 0x5 = 10
0x1-2x2 + 5x3 + 0x4-1x5 = 3
1x1 + 0x2 + 2x3 + 0x4 + 0x5 = 9
F(X) = — x1 — 2x2 + 2x3
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 4 | 3 | -1 | 1 | 0 | 10 |
| 0 | -2 | 5 | 0 | -1 | 3 |
| 1 | 0 | 2 | 0 | 0 | 9 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x4.
2. В качестве базовой переменной выбираем x2.
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x2, получена в результате деления всех элементов строки x2 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(0 • 3):-2 | 3-(-2 • 3):-2 | -1-(5 • 3):-2 | 1-(0 • 3):-2 | 0-(-1 • 3):-2 | 10-(3 • 3):-2 |
| 0 : -2 | -2 : -2 | 5 : -2 | 0 : -2 | -1 : -2 | 3 : -2 |
| 1-(0 • 0):-2 | 0-(-2 • 0):-2 | 2-(5 • 0):-2 | 0-(0 • 0):-2 | 0-(-1 • 0):-2 | 9-(3 • 0):-2 |
Получаем новую матрицу:
| 4 | 0 | 6 1 /2 | 1 | -1 1 /2 | 14 1 /2 |
| 0 | 1 | -2 1 /2 | 0 | 1 /2 | -1 1 /2 |
| 1 | 0 | 2 | 0 | 0 | 9 |
3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
| 4-(1 • 6 1 /2):2 | 0-(0 • 6 1 /2):2 | 6 1 /2-(2 • 6 1 /2):2 | 1-(0 • 6 1 /2):2 | -1 1 /2-(0 • 6 1 /2):2 | 14 1 /2-(9 • 6 1 /2):2 |
| 0-(1 • -2 1 /2):2 | 1-(0 • -2 1 /2):2 | -2 1 /2-(2 • -2 1 /2):2 | 0-(0 • -2 1 /2):2 | 1 /2-(0 • -2 1 /2):2 | -1 1 /2-(9 • -2 1 /2):2 |
| 1 : 2 | 0 : 2 | 2 : 2 | 0 : 2 | 0 : 2 | 9 : 2 |
Получаем новую матрицу:
| 3 /4 | 0 | 0 | 1 | -1 1 /2 | -14 3 /4 |
| 1 1 /4 | 1 | 0 | 0 | 1 /2 | 9 3 /4 |
| 1 /2 | 0 | 1 | 0 | 0 | 4 1 /2 |
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3 /4x1 + x4 — 1 1 /2x5 = -14 3 /4
1 1 /4x1 + x2 + 1 /2x5 = 9 3 /4
1 /2x1 + x3 = 4 1 /2
Выразим базисные переменные через остальные:
x4 = — 3 /4x1 + 1 1 /2x5-14 3 /4
x2 = — 1 1 /4x1 — 1 /2x5+9 3 /4
x3 = — 1 /2x1+4 1 /2
Подставим их в целевую функцию:
F(X) = — x1 — 2(- 1 1 /4x1 — 1 /2x5+9 3 /4) + 2(- 1 /2x1+4 1 /2)
или
F(X) = 1 /2x1 + x5-10 1 /2 → max
Система неравенств:
— 3 /4x1 + 1 1 /2x5-14 3 /4 ≥ 0
— 1 1 /4x1 — 1 /2x5+9 3 /4 ≥ 0
— 1 /2x1+4 1 /2 ≥ 0
Приводим систему неравенств к следующему виду:
3 /4x1 — 1 1 /2x5 ≤ -14 3 /4
1 1 /4x1 + 1 /2x5 ≤ 9 3 /4
1 /2x1 ≤ 4 1 /2
F(X) = 1 /2x1 + x5-10 1 /2 → max
Упростим систему.
3 /4x1 — 1 1 /2x2 ≤ -14 3 /4
1 1 /4x1 + 1 /2x2 ≤ 9 3 /4
1 /2x1 ≤ 4 1 /2
F(X) = 1 /2x1 + x2-10 1 /2 → max
Двойственный симплексный метод
Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых 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 кг корма каждого вида.
Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.