Найти решение задачи линейного программирования методом исключения переменных

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

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

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

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

Переменные x₁, …, x_m, входящие с единичными коэффициентами только в одно уравнение системы, с нулевыми – в остальные, называются базисными или зависимыми. В канонической системе каждому уравнению соответствует ровно одна базисная переменная. Переход осуществляется с помощью метода Гаусса–Жордана. Основная идея этого метода состоит в сведении системы m уравнений с n неизвестными к каноническому виду при помощи элементарных операций над строками.
Остальные n-m переменных (x_m+1,…, x_n) называются небазисными или независимыми переменными.

Базисное решение называется допустимым базисным решением, если значения входящих в него базисных переменных x_j≥0, что эквивалентно условию неотрицательности b_j≥0.
Допустимое базисное решение является угловой точкой допустимого множества S задачи линейного программирования и называется иногда опорным планом.
Если среди неотрицательных чисел b_j есть равные нулю, то допустимое базисное решение называется вырожденным (вырожденной угловой точкой) и соответствующая задача линейного программирования называется вырожденной.

Пример №1 . Свести задачу линейного программирования к стандартной ЗЛП.
F(X) = x₁ + 2x₂ — 2x₃ → min при ограничениях:
4x₁ + 3x₂ — x₃≤10
— 2x₂ + 5x₃≥3
x₁ + 2x₃=9
Для приведения ЗЛП к канонической форме необходимо:
1. Поменять знак у целевой функции. Сведем задачу F(X) → min к задаче F(X) → max. Для этого умножаем F(X) на (-1). В первом неравенстве смысла (≤) вводим базисную переменную x₄; во втором неравенстве смысла (≥) вводим базисную переменную x₅ со знаком минус.
4x₁ + 3x₂-1x₃ + 1x₄ + 0x₅ = 10
0x₁-2x₂ + 5x₃ + 0x₄-1x₅ = 3
1x₁ + 0x₂ + 2x₃ + 0x₄ + 0x₅ = 9
F(X) = — x₁ — 2x₂ + 2x₃
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

4	3	-1	1	0	10
0	-2	5	0	-1	3
1	0	2	0	0	9

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₄.
2. В качестве базовой переменной выбираем x₂.
Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x₂, получена в результате деления всех элементов строки x₂ на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₂ записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

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. В качестве базовой переменной выбираем x₃.
Разрешающий элемент РЭ=2. Строка, соответствующая переменной x₃, получена в результате деления всех элементов строки x₃ на разрешающий элемент РЭ=2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x₃ записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы:

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 /₄x₁ + x₄ — 1 1 /₂x₅ = -14 3 /₄
1 1 /₄x₁ + x₂ + 1 /₂x₅ = 9 3 /₄
1 /₂x₁ + x₃ = 4 1 /₂
Выразим базисные переменные через остальные:
x₄ = — 3 /₄x₁ + 1 1 /₂x₅-14 3 /₄
x₂ = — 1 1 /₄x₁ — 1 /₂x₅+9 3 /₄
x₃ = — 1 /₂x₁+4 1 /₂
Подставим их в целевую функцию:
F(X) = — x₁ — 2(- 1 1 /₄x₁ — 1 /₂x₅+9 3 /₄) + 2(- 1 /₂x₁+4 1 /₂)
или
F(X) = 1 /₂x₁ + x₅-10 1 /₂ → max
Система неравенств:
— 3 /₄x₁ + 1 1 /₂x₅-14 3 /₄ ≥ 0
— 1 1 /₄x₁ — 1 /₂x₅+9 3 /₄ ≥ 0
— 1 /₂x₁+4 1 /₂ ≥ 0
Приводим систему неравенств к следующему виду:
3 /₄x₁ — 1 1 /₂x₅ ≤ -14 3 /₄
1 1 /₄x₁ + 1 /₂x₅ ≤ 9 3 /₄
1 /₂x₁ ≤ 4 1 /₂
F(X) = 1 /₂x₁ + x₅-10 1 /₂ → max
Упростим систему.
3 /₄x₁ — 1 1 /₂x₂ ≤ -14 3 /₄
1 1 /₄x₁ + 1 /₂x₂ ≤ 9 3 /₄
1 /₂x₁ ≤ 4 1 /₂
F(X) = 1 /₂x₁ + x₂-10 1 /₂ → max

Источник

6.1.2. Метод исключения переменных Пусть дана задача линейного программирования в канонической форме

f(x) = ,

а_ij x_j = b_{i ,} i  :m, (6.8)

x_j ≥ 0, j = 1:n,

где число переменных на два больше числа ограничений − равенств, т.е. n —m= 2, причем ранг матрицыА =m. Тогда две переменные в указанной системе уравнений, скажемх₁их₂, являются свободными, т.е. через них можно выразить все остальные переменные:

, (6.9)

где − некоторые числа. Подставляя эти выражения в целевую функцию, получаем

где γ₁, γ₂, δ − некоторые числа.

Рассмотрим задачу линейного программирования с двумя переменными:

Используя геометрические построения, находим ее решение (). Подставляя эти числа в (6.9), (6.10), получаем решение и значение исходной задачи (6.8).

Пример6.2.Используя графический метод, найти решение

Рис. 6.2. Допустимое множество задачи 6.2

Решение. Изобразим на плоскости (х₁, х₂) допустимое множество  данной задачи (многоугольник ABCDE, рис. 6.2) и одну из линий уровня —х₁ -2х₂ = — 3 целевой функции х. Направление убывания (x) указывает вектор l = (1,2). Совершая параллельный перенос линии уровня вдоль направления l, находим ее крайнее положение. В этом положении прямая —х₁ — 2х₂ = — 3 проходит через сторону CD полиэдра ABCDE. Таким образом, все точки отрезка CD являются точками минимума функции х на множестве X. Так как концы C и D этого отрезка имеют координаты (1,3) и (3,2) соответственно, то любая точка минимума функции х представима в виде

где . Минимальное значение целевой функции * =(х*) = –7.

Пример 6.3.Решить графическим методом задачу линейного программирования:

Рис. 6.3. Неограниченное многоугольное множество

Решение. Допустимое множество этой задачи представляет собой неограниченное многоугольное множество (рис. 6.3). Функцияf(x) убывает в направленииl= (1,2). При параллельном переносе линии уровнявдоль направленияlона всегда пересекает множествоХ, а целевая функцияf(x) неограниченно убывает. Поэтому рассмотренная задача не имеет решений.

Пример 6.4.Найти максимальное значение функции

при условиях:

Решение.В отличие от рассмотренных выше задач в исходной задаче ограничения заданы в виде уравнений. При этом число неизвестных равно пяти. Поэтому данную задачу следует свести к задаче, в которой число неизвестных было бы равно двум. В рассматриваемом случае это можно сделать путем перехода от исходной задачи, записанной в форме основной, к задаче, записанной в форме стандартной.

Из целевой функции исходной задачи исключаем переменные x₃, x₄, x₅ с помощью подстановки их значений из соответствующих уравнений системы ограничений. Получаем постановку задачи в стандартной форме:

f(x) = 2x₁ +3x₂,

Рис. 6.4. Многоугольник решений

Построим многоугольник решений полученной задачи (рис. 6.4). Как видно из рис. 6.4., максимальное значение целевая функция задачи принимает в точке С пересечения прямыхIиII.Вдоль каждой из граничных прямых значение одной из переменных, исключенной при переходе к соответствующему неравенству, равно нулю. Поэтому в каждой из вершин полученного многоугольника решений последней задачи по крайней мере две переменные исходной задачи принимают нулевые значения. Так, в точкеС имеемx₃ = 0 иx₄ = 0. Подставляя эти значения в первое и второе уравнения системы ограничений исходной задачи, получаем систему двух уравнений

решая которую, находим x₁* =3,x₂* = 4.

Подставляя найденные значения x₁иx₂в третье уравнение системы ограничений исходной задачи, определяем значение переменнойx₅ равное 14.

Следовательно, оптимальным планом рассматриваемой задачи является x* = (3; 4; 0; 0; 14). При этом плане значение целевой функции есть _max = 18.

Источник

Задача 6

Используя метод исключения переменных и геометрические построения, найти решение задачи Линейного Программирования: Решение

1. Из третьего ограничения можно выразить:

1. Подставим выражение для в первое ограничение:

1. Подставим выражение для во второе ограничение:

1. Таким образом, после применения метода исключения переменных от исходной задачи перейдем к задаче вида:

Данная задача может быть решена на плоскости графическим методом решения задач линейного программирования.

1. Необходимо на плоскости построить прямые, соответствующие заданным неравенствам.

Прямая, соответствующая неравенству , проходит через точкупараллельно оси Прямая, соответствующая неравенству проходит через точки и

1. Строим на плоскости прямые, соответствующие данным прямым.

1. Определяем ОДЗ (Область допустимых значений) данной системы неравенств. ОДЗ- это многогранник, ограниченный заданной системой неравенств, каждая точка которого удовлетворяет всем неравенствам ( условиям).

Таким образом, ОДЗ, удовлетворяющая всем условиям следующая:

1. Строим вектор целевой функции . Для этого необходимо построить линию уровня целевой функции, где, а затем определить в какую сторону целевая функция возрастает.

Линия уровня целевой функции проходит через точкии. Чтобы определить градиент возрастания целевой функции можно взять две точки выше и ниже линии уровня целевой функции , подставить данные значения в уравнение целевой функциии посмотреть, в какой точке значениебольше нуля. В нашем случае можно взять две точки: и: Таким образом, целевая функция возрастает вниз (см. рисунок), а вверх соответственно убывает.

1. Мысленно передвигая параллельно линию уровня целевой функции вверх, нужно определить крайнюю точку ОДЗ, которую пересекают линии уровня целевой функции.

Для данной ОДЗ целевая функция достигает минимума в точке С, а максимума в точкеA. Определим координаты точек Aи С. Координаты точки Aможно определить из графика:. Тогда, подставив координаты точки А в, получаем значение максимума целевой функции для заданной системы неравенств: Точка С образована пересечением двух прямых Решив данную систему уравнений, получаем координаты точки С . Подставив координаты точки С в, получаем значение максимума целевой функции для заданной системы неравенств: Ответ: ,

1. Источник