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

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

Назначение сервиса . Онлайн-калькулятор предназначен для решения задач линейного программирования симплексным методом путем перехода к КЗЛП и СЗЛП . При этом задача на минимум целевой функции сводятся к задаче на поиск максимума через преобразование целевой функции 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. Решение симплексным методом;
  • Шаг №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

Для оптимизации функции цели используем следующие понятия и методы.
Опорный план – план с определёнными через свободные базисными переменными.
Базисный план – опорный план с нулевыми базисными переменными.
Оптимальный план – базисный план, удовлетворяющий оптимальной функции цели (ФЦ).

Ведущий (разрешающий) элемент – коэффициент свободной неизвестной, которая становится базисной, а сам коэффициент преобразуется в единицу.
Направляющая строка – строка ведущего элемента, в которой расположена с единичным коэффициентом базисная неизвестная, исключаемая при преобразовании (строка с минимальным предельным коэффициентом, см. далее).
Направляющий столбец – столбец ведущего элемента, свободная неизвестная которого переводится в базисную (столбец с максимальной выгодой, см. далее).

Читайте также:  Устройства программирования микроконтроллеров avr

Переменные 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

Источник

Оцените статью