Решение задач линейного программирования
Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции 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
Решение задач линейного программирования
симплексным методом
Если вы уже разобрались с графическим методом решения задач линейного программирования, самое время переходить к симплекс-методу. В отличие от первого, он практически не имеет ограничений на задачу (любое количество переменных, разные знаки и т.п.) и модифицируется в зависимости от типа задачи (например, М-метод или метод искусственного базиса).
При решении задачи симплекс методом вычисления обычно ведутся (для компактности и наглядности) в таблицах (табличный симплекс-метод), причем последняя таблица с оптимальным решением содержит важную дополнительную информацию: решение двойственной задачи, остатки ресурсов, сведения о дефицитных ресурсах и т.п., которая позволяет провести экономический анализ задачи линейного программирования (см. ниже пример 3).
Примеры решений задач симплекс-методом выложены бесплатно для вашего удобства — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении подобных заданий, перейдите в раздел: решение линейного программирования на заказ.
Решение задач симплекс-методом: примеры онлайн
Задача 1. Компания производит полки для ванных комнат двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В — 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В — 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?
Задача 2. Решить задачу линейного программирования симплекс-методом.
Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.
- Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
- Определить статус каждого вида сырья и его удельную ценность.
- Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
- Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
- Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.
Задача 6. Решить задачу симплекс-методом, рассматривая в качестве начального опорного плана, план, приведенный в условии:
Задача 7. Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.