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

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

Инструкция . Выберите количество переменных и количество строк (количество ограничений). Полученное решение сохраняется в файле Word .

Переход от задачи минимизации целевой функции к задаче максимизации

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

F(x) → min

F(x) → max

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

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

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

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

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

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

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

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

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 / 4 x 1 + x 4 - 1 1 / 2 x 5 = -14 3 / 4
1 1 / 4 x 1 + x 2 + 1 / 2 x 5 = 9 3 / 4
1 / 2 x 1 + x 3 = 4 1 / 2
Выразим базисные переменные через остальные:
x 4 = - 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4
x 2 = - 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4
x 3 = - 1 / 2 x 1 +4 1 / 2
Подставим их в целевую функцию:
F(X) = - x 1 - 2(- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4) + 2(- 1 / 2 x 1 +4 1 / 2)
или

Система неравенств:
- 3 / 4 x 1 + 1 1 / 2 x 5 -14 3 / 4 ≥ 0
- 1 1 / 4 x 1 - 1 / 2 x 5 +9 3 / 4 ≥ 0
- 1 / 2 x 1 +4 1 / 2 ≥ 0
Приводим систему неравенств к следующему виду:
3 / 4 x 1 - 1 1 / 2 x 5 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 5 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 5 -10 1 / 2 → max
Упростим систему.
3 / 4 x 1 - 1 1 / 2 x 2 ≤ -14 3 / 4
1 1 / 4 x 1 + 1 / 2 x 2 ≤ 9 3 / 4
1 / 2 x 1 ≤ 4 1 / 2
F(X) = 1 / 2 x 1 + x 2 -10 1 / 2 → max

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

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

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

Инструкция . Выберите количество строк (количество ограничений). Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. и пример №2). Если ограничение двойное, например, 1 ≤ x 1 ≤ 4 , то оно разбивается на два: x 1 ≥ 1 , x 1 ≤ 4 (т.е. количество строк увеличивается на 1).
Построить область допустимого решения (ОДР) можно также с помощью этого сервиса .

Вместе с этим калькулятором также используют следующие:
Симплексный метод решения ЗЛП

Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Вычисление пределов

Решение задачи линейного программирования графическим методом включает следующие этапы :

На плоскости X 1 0X 2 строят прямые.
Определяются полуплоскости.
Определяют многоугольник решений;
Строят вектор N(c 1 ,c 2), который указывает направление целевой функции;
Передвигают прямую целевую функцию c 1 x 2 + c 2 x 2 = 0 в направлении вектора N до крайней точки многоугольника решений.
Вычисляют координаты точки и значение целевой функции в этой точке.

При этом могут возникать следующие ситуации:

Пример . Компания изготавливает два вида продукции - П1 и П2. Для производства продукции используются два вида сырья - С1 и С2. Оптовые цены единицы продукции равна: 5 д.е. для П1 и 4 д.е. для П2. Расход сырья на единицу продукции вида П1 и вида П2 дан в таблице.
Таблица - Расход сырья на производство продукции

Установлены ограничения на спрос продукции: ежедневный объем производства продукции П2 не должен превышать ежедневный объем производства продукции П1 не более чем на 1 тонну; максимальный ежедневный объем производства П2 не должен превышать 2 т.
Требуется определить:
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?

Сформулировать математическую модель задачи линейного программирования.
Решить задачу линейного программирования графическим способом (для двух переменных).

Решение.
Сформулируем математическую модель задачи линейного программирования.
x 1 - производство продукции П1, ед.
x 2 - производство продукции П2, ед.
x 1 , x 2 ≥ 0

Ограничения по ресурсам
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Ограничения по спросу
x 1 +1 ≥ x 2
x 2 ≤ 2

Целевая функция
5x 1 + 4x 2 → max

Тогда получаем следующую ЗЛП:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → max

Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП .
→ max при ограничениях:
x 1 + x 2 + x 3 =12
2x 1 - x 2 + x 4 =8
- 2x 1 + 2x 2 + x 5 =10
F(X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Переход к СЗЛП .

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.

x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10

x 3 = - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10

или

Система неравенств:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0

x 1 + x 2 ≤ 12
2x 1 - x 2 ≤ 8
- 2x 1 + 2x 2 ≤ 10

Особенности решения задач линейного программирования графическим методом

Пример №1 . Записать задачу в стандартной форме и решить ее графическим методом.

f=x 1 +13x 2 -x 3 +2x 4 +3x 5
-x 2 +x 3 -x 5 =-3
x 1 -4x 2 +3x 3 -x 4 +2x 5 =3
4x 2 -x 3 +x 4 -x 5 =6

Из первого уравнения выражаем x 5:
x 5 = -x 2 +x 3 +3

f=x 1 +13x 2 -x 3 +2x 4 +3(-x 2 +x 3 +3)
x 1 -4x 2 +3x 3 -x 4 +2(-x 2 +x 3 +3)=3
4x 2 -x 3 +x 4 -(-x 2 +x 3 +3)=6
или
f=x 1 +10x 2 +2x 3 +2x 4 +9
x 1 -6x 2 +5x 3 -x 4 =-3
5x 2 -2x 3 +x 4 =9

Из второго уравнения выражаем x 4:
x 4 =9-5x 2 +2x 3
и подставим во все выражения:
f=x 1 +6x 3 +27
x 1 -x 2 +3x 3 =6

Переменную x 2 принимаем в качестве дополнительной переменной и делаем замену на знак «≥»:
f=x 1 + 6x 3 + 27
x 1 + 3x 3 ≥6

Пример №2

x 1 + x 2 + x 3 =12
2x 1 - x 2 + x 4 =8
- 2x 1 + 2x 2 + x 5 =10
F(X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Переход к СЗЛП .
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x 3 .
2. В качестве базовой переменной можно выбрать x 4 .
3. В качестве базовой переменной можно выбрать x 5 .
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x 1 + 2x 2 + x 5 = 10
Выразим базисные переменные через остальные:
x 3 = - x 1 - x 2 +12
x 4 = - 2x 1 + x 2 +8
x 5 = 2x 1 - 2x 2 +10
Подставим их в целевую функцию:
F(X) = 3x 1 - 2x 2 + 5(- x 1 - x 2 +12) - 4(2x 1 - 2x 2 +10)
или
F(X) = - 10x 1 + x 2 +20 → max
Система неравенств:
- x 1 - x 2 +12 ≥ 0
- 2x 1 + x 2 +8 ≥ 0
2x 1 - 2x 2 +10 ≥ 0
Приводим систему неравенств к следующему виду:
x 1 + x 2 ≤ 12
2x 1 - x 2 ≤ 8
- 2x 1 + 2x 2 ≤ 10
F(X) = - 10x 1 + x 2 +20 → max

Пример №3 . Составить математическую модель задачи линейного программирования и найти решение геометрическим способом.

Составить систему математических зависимостей (неравенств) и целевую функцию.
Изобразить геометрическую интерпретацию задачи.
Найти оптимальное решение.
Провести аналитическую проверку.
Определить существенные и несущественные ресурсы и их избытки.
Определить значение целевой функции.
Вычислить объективно обусловленные оценки.
Составить соотношение устойчивости.

Николай Кузнецов управляет небольшим механическим заводом. В будущем месяце он планирует изготавливать два продукта (А и В), по которым удельная маржинальная прибыль оценивается в 2500 и 3500 руб., соответственно.

Изготовление обоих продуктов требует затрат на машинную обработку, сырье и труд На изготовление каждой единицы продукта А отводится 3 часа машинной обработки, 16 единиц сырья и 6 единиц труда. Соответствующие требования к единице продукта В составляют 10, 4 и 6. Николай прогнозирует, что в следующем месяце он может предоставить 330 часов машинной обработки, 400 единиц сырья и 240 единиц труда. Технология производственного процесса такова, что не менее 12 единиц продукта В необходимо изготавливать в каждый конкретный месяц.

Наименование ресурса	A	B	Объем ресурсов
Часы маш.обработки	3	10	330
Единиц сырья	16	4	400
Единиц труда	6	6	240

Николай хочет построить модель с тем, чтобы определить количество единиц продуктов А и В, которые он доложен производить в следующем месяце для максимизации маржинальной прибыли.

Решение задачи

Этап 1. Определение переменных

Существует целевая переменная (обозначим её Z), которую необходимо оптимизировать, то есть максимизировать или минимизировать (например, прибыль, выручка или расходы). Николай стремится максимизировать маржинальную прибыль, следовательно, целевая переменная:

Z - это суммарная маржинальная прибыль (в рублях), полученная в следующем месяце в результате производства продуктов А и В.

Существует ряд неизвестных искомых переменных (обозначим их х 1 , х 2 , х 3 и пр.), чьи значения необходимо определить для получения оптимальной величины целевой функции, которая, в нашем случае является суммарной маржинальной прибылью. Эта маржинальная прибыль зависит от количества произведенных продуктов А и В. Значения этих величин необходимо рассчитать, и поэтому они представляют собой искомые переменные в модели. Итак, обозначим:

х 1 - количество единиц продукта А, произведенных в следующем месяце.

х 2 - количество единиц продукта В, произведенных в следующем месяце.

Очень важно четко определить все переменные величины; особое внимание уделите единицам измерения и периоду времени, к которому относятся переменные.

Этап. 2. Построение целевой функции

Целевая функция - это линейное уравнение, которое должно быть или максимизировано или минимизировано. Оно содержит целевую переменную, выраженную с помощью искомых переменных, то есть Z выраженную через х 1 , х 2 , … в виде линейного уравнения.

В нашем примере каждый изготовленный продукт А приносит 2500 руб. маржинальной прибыли, а при изготовлении х 1 единиц продукта А, маржинальная прибыль составит 2500х 1 . Аналогично маржинальная прибыль от изготовления х 2 единиц продукта В составит 3500х 2 . Таким образом, суммарная маржинальная прибыль, полученная в следующем месяце за счет производства х 1 единиц продукта А и х 2 единиц продукта В, то есть, целевая переменная Z составит: Z = 2500х 1 +3500х 2 .

Николай стремится максимизировать этот показатель. Таким образом, целевая функция в нашей модели:

Этап. 3. Определение ограничений

Ограничения – это система линейных уравнений и/или неравенств, которые ограничивают величины искомых переменных. Они математически отражают доступность ресурсов, технологические факторы, условия маркетинга и иные требования. Ограничения могут быть трех видов: «меньше или равно», «больше или равно», «строго равно».

В нашем примере для производства продуктов А и В необходимо время машинной обработки, сырье и труд, и доступность этих ресурсов ограничена. Объемы производства этих двух продуктов (то есть значения х 1 и х 2) будут, таким образом, ограничены тем, что количество ресурсов, необходимых в производственном процессе, не может превышать имеющееся в наличии. Рассмотрим ситуацию со временем машинной обработки. Изготовление каждой единицы продукта А требует трех часов машинной обработки, и если изготовлено х 1 , единиц, то будет потрачено Зх 1 , часов этого ресурса.

Изготовление каждой единицы продукта В требует 10 часов и, следовательно, если произведено х 2 продуктов, то потребуется 10х 2 часов. Таким образом, общий объем машинного времени, необходимого для производства х 1 единиц продукта А и х 2 единиц продукта В, составляет 3х 1 +10х 2 . Это общее значение машинного времени не может превышать 330 часов. Математически это записывается следующим образом:

3х 1 +10х 2 ≤330

Аналогичные соображения применяются к сырью и труду, что позволяет записать еще два ограничения:

16х 1 +4х 2 ≤400

6х 1 +6х 2 ≤240

Наконец следует отметить, что существует условие, согласно которому должно быть изготовлено не менее 12 единиц продукта В:

Этап. 4. Запись условий неотрицательности

Искомые переменные не могут быть отрицательными числами, что необходимо записать в виде неравенств х 1 ≥0 и х 2 ≥0. В нашем примере второе условия является избыточным, так как выше было определено, что х 2 не может быть меньше 12.

\[\left\{ {\begin{array}{}
{3{x_1} + 10{x_2} \le 330}\\
{16{x_1} + 4{x_2} \le 400}\\
{6{x_1} + 6{x_2} \le 240}\\
{{x_1} \ge 0}\\
{{x_2} \ge 12}
\end{array}} \right.\]

Решение симплекс-методом

Симплексный метод является универсальным методом решения задачи линейного грограммирования, так как позволяет решить практически любую задачу, представленную в каноническом виде.

Идея симплексного метода заключатся в том, что, начиная с некоторого опорного решения, осуществляется последовательно направленное перемещение по опорным решениям системы к оптимальному опорному решению. Так как число опорных решений конечно, то через конечное число шагов оптимальное решение будет найдено.

Алгорим симплексного метода можно описать следующим образом:

Привести задачу к каноническому виду
Найти неотрицательное базисное решение системы ограничений
Рссчитать оценки свободных переменных по формуле:

\[{\Delta}_j = \sum\limits_{i = 1}^r {{c_i}{h_{ij}} – {c_j}} ,\;j = \overline {1,n} ,\]

где h ij – коэффициенты при свободной переменной x j ,

c i – коэффициенты при базисных переменных в целевой функции,

c j – коэффициенты при свободной переменной в целевой функции,

Проверить найденное опорное решение на оптмальность:

а) если все оценки ${\Delta}_j \ge 0$ , то найденное решение оптимально и задача решена;

б) если хотя бы одна оценка ${\Delta}_j < 0$ , а при соответствующей переменной x j нет ни одного положительного коэффициента, то задача не имеет оптимального решения из-за ограниченности целевой функции

в) если хотя бы одна оценка ${\Delta}_j < 0$ , а при соответствующей переменной x j есть хотя бы один положительный коэффициент, то решение не оптимально и его можно улучшить переходом к новому базису. Если отрицательных оценок несколько,то в базис ввести переменную с наибольшей по абсолютной величине отрицательной оценкой.

Приведем задачу к каноническому виду .

Полная модель линейного программирования для производственной задачи Николая может быть записана в виде:

\[\left\{ {\begin{array}{}
{3{x_1} + 10{x_2} + {x_3} = 330}\\
{16{x_1} + 4{x_2} + {x_4} = 400}\\
{6{x_1} + 6{x_2} + {x_5} = 240}\\
{-{x_2} +{x_6} = 12}\\
{{x_j} \ge 0\;j = \overline {1,n}}
\end{array}} \right.\]

Б.п.	x 1	x 2	x 3	x 4	x 5	x 6	b i
x 3	3	10	1	0	0	0	330
x 4	16	4	0	1	0	0	400
x 5	6	6	0	0	1	0	240
x 6	0	-1	0	0	0	1	12

\[\bar{x}_{\text{опор}}=(0;0;330;400;20;12)\]

Проверим данное решение на оптимальность, для этого найдем свободные переменные в симплексной таблице. Вычисления представлены в файле lp_simplex.xlsx .

Данное решение не оптимально, поскольку в нижней строчке есть отрицательные значения. Поскольку имеются положительные коэффициенты, решение можно улучшить, для этого введем в базис переменную x 2 . Так как в колонке x 2 имеется несколько положительных коэффициентов, то определяем отношение свободного члена b i к соответсвующим коэффициентам в данной колонке и выбираем наименьший результат.

Преобразуем таблицу и повторим расчет.

Полученное решение (10; 30) является оптимальным.

Решение с помощью Excel и LibreOffice

Решение в Excel осуществляется с помощью надстройки “Поиск решения”, также использующей симплекс-метод.

Анологично даную задач можно решить с помощью Решателя в LibreOffice. Следует отметить, что в LibreOffice нет ограничений на число переменных, в отличии от Excel.

Решение в R

Для решения задач линеного программирования в GNU R можно использовать следующие пакеты:

lpSolve
linprog

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

Решение с пакетом lpSolve

library(lpSolve) # Подключили библиотеку f.obj <- c(2500, 3500) # Описали целевую функцию names(f.obj) <-c("A","B") a.mat<-rbind(c(3,10), # матрица c(16,4), # коээфициентов c(6,6), # при ограничениях c(1,0), c(0,1)) a.dir<-c("<=","<=","<=",">=",">=") b.vec<-c(330,400,240,0,12) # вектор ограничений result<-lp ("max", f.obj, a.mat, a.dir, b.vec)

Результат

result ## Success: the objective function is 130000 result$solution ## 10 30

Таким образом, максимальное значение целевой функции равно 130000 и оно достигается при x 1 и x 2 равными, соответственно: 10 и 30.

Решение с пакетом linprog

Поскольку пакет linprog является дополнением к предыдущему пакету, то переменные уже все инициализированы.

Library(linprog) ## Warning: package "linprog" was built under R version 3.2.2 (result<-solveLP(f.obj, b.vec, a.mat, TRUE,const.dir=a.dir,lpSolve=T)) ## ## ## Results of Linear Programming / Linear Optimization ## (using lpSolve) ## ## Objective function (Maximum): 130000 ## ## Solution ## opt ## A 10 ## B 30 ## ## Constraints ## actual dir bvec free ## 1 330 <= 330 0 ## 2 280 <= 400 120 ## 3 240 <= 240 0 ## 4 10 >= 0 10 ## 5 30 >= 12 18

Результат получился тот же, дополнительно выведена информация по свободным ресурсам. Таким образом,GNU R предоставляет достаточно удобный механизм для решения задач линейного программирования.

Вконтакте

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

при ограничениях

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

Построим уравнение 3x 1 +x 2 = 9 по двум точкам .
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 9. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 3. Соединяем точку (0;9) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 . 0 + 1 . 0 - 9 ≤ 0, т.е. 3x 1 +x 2 - 9≥ 0 в полуплоскости выше прямой.
Построим уравнение x 1 +2x 2 = 8 по двум точкам .
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 4. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 8. Соединяем точку (0;4) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 . 0 + 2 . 0 - 8 ≤ 0, т.е. x 1 +2x 2 - 8≥ 0 в полуплоскости выше прямой.
Построим уравнение x 1 +x 2 = 8 по двум точкам .
Для нахождения первой точки приравниваем x 1 = 0. Находим x 2 = 8. Для нахождения второй точки приравниваем x 2 = 0. Находим x 1 = 8. Соединяем точку (0;8) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 . 0 + 1 . 0 - 8 ≤ 0, т.е. x 1 +x 2 - 8≤ 0 в полуплоскости ниже прямой.

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.

Проверить правильность построения графиков функций можно с помощью калькулятора

Рассмотрим целевую функцию задачи F = 4x 1 +6x 2 → min.
Построим прямую, отвечающую значению функции F = 0: F = 4x 1 +6x 2 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора - точка (0; 0), конец - точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = 4x 1 +6x 2 пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2) , то ее координаты удовлетворяют уравнениям этих прямых:
3x 1 +x 2 =9
x 1 +2x 2 =8

Решив систему уравнений, получим: x 1 = 2, x 2 = 3
Откуда найдем минимальное значение целевой функции:
F(X) = 4*2 + 6*3 = 26

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

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

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

Однако для выработки наглядных представлений о решениях задач линейного программирования графический метод представляет определённый интерес. Кроме того, он позволяет геометрически подтвердить справедливость теорем линейного программирования .

Теоретические основы графического метода

Итак, задача линейного программирования. Требуется найти неотрицательные значения переменных и , удовлетворяющих системе неравенств

при которых линейная форма принимает оптимальное значение.

Пример 3.

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

Продолжаем решать задачи графическим методом вместе

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

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

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