Динамическое программирование
Задачи динамического программирования: задача распределения инвестиций, задача замены оборудования, задача Джонсона
xf1(x)f2(x)f3(x)
16.345
25.267
34.34.67.8
4563
5*76.38.2
Решить онлайн
Примеры решений Метод Гомори Графический метод Теория игр Симплекс-метод M-задача Теоремы двойственности Одноканальные СМО Задача коммивояжера Транспортная задача

Решение задач линейного программирования

Назначение сервиса. Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП. При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции F*(X) = -F(X). Также имеется возможность составить двойственную задачу.

Решение происходит в три этапа:

  1. Переход к КЗЛП. Любая ЗЛП вида ax ≤ b, ax ≥ b, ax = b (F(X) → extr) сводится к виду ax = b, F(X) → max;
  2. Переход к СЗЛП. КЗЛП вида ax = b сводится к виду ax ≤ b, F(X) → max;
  3. Решение симплексным методом;
Инструкция. Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле 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
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

43-11010
0-250-13
102009

Приведем систему к единичной матрице методом жордановских преобразований.
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 61/2 1 -11/2 141/2
0 1 -21/2 0 1/2 -11/2
1 0 2 0 0 9

3. В качестве базовой переменной выбираем x3.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x3, получена в результате деления всех элементов строки x3 на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:
4-(1 • 61/2):2 0-(0 • 61/2):2 61/2-(2 • 61/2):2 1-(0 • 61/2):2 -11/2-(0 • 61/2):2 141/2-(9 • 61/2):2
0-(1 • -21/2):2 1-(0 • -21/2):2 -21/2-(2 • -21/2):2 0-(0 • -21/2):2 1/2-(0 • -21/2):2 -11/2-(9 • -21/2):2
1 : 2 0 : 2 2 : 2 0 : 2 0 : 2 9 : 2

Получаем новую матрицу:
3/4 0 0 1 -11/2 -143/4
11/4 1 0 0 1/2 93/4
1/2 0 1 0 0 41/2

Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (4,2,3).
Соответствующие уравнения имеют вид:
3/4x1 + x4 - 11/2x5 = -143/4
11/4x1 + x2 + 1/2x5 = 93/4
1/2x1 + x3 = 41/2
Выразим базисные переменные через остальные:
x4 = - 3/4x1 + 11/2x5-143/4
x2 = - 11/4x1 - 1/2x5+93/4
x3 = - 1/2x1+41/2
Подставим их в целевую функцию:
F(X) = - x1 - 2(- 11/4x1 - 1/2x5+93/4) + 2(- 1/2x1+41/2)
или
F(X) = 1/2x1 + x5-101/2 → max
Система неравенств:
- 3/4x1 + 11/2x5-143/4 ≥ 0
- 11/4x1 - 1/2x5+93/4 ≥ 0
- 1/2x1+41/2 ≥ 0
Приводим систему неравенств к следующему виду:
3/4x1 - 11/2x5 ≤ -143/4
11/4x1 + 1/2x5 ≤ 93/4
1/2x1 ≤ 41/2
F(X) = 1/2x1 + x5-101/2 → max
Упростим систему.
3/4x1 - 11/2x2 ≤ -143/4
11/4x1 + 1/2x2 ≤ 93/4
1/2x1 ≤ 41/2
F(X) = 1/2x1 + x2-101/2 → max

Пример №2. Найдите сначала графическим методом, а затем симплекс-методом решение задачи
F(X) = x1 + x2 - x3 + x5+15 → max (min) при ограничениях:
-3x1 + x2 + x3=3
4x1 + 2x2 - x4=12
2x1 - x2 + x5=2
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0, x4 ≥ 0, x5 ≥ 0

Учебно-методический
  • курсы переподготовки и повышения квалификации;
  • вебинары;
  • сертификаты на публикацию методического пособия
Подробнее
Болит горло
Как быстро вылечить ангину, гланды, тонзиллит
Природные средства, проверенные временем и врачами
Подробнее
ЕГЭ по математике
Yandex.Просвещение представляет бесплатные видеокурсы по ЕГЭ с возможностью прохождения тестов
Подробнее