Решение происходит в три этапа:
- Переход к КЗЛП. Любая ЗЛП вида 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
Цех изготавливает изделия А и Б. Расход сырья, его запас и прибыль от реализации каждого изделия указаны в таблице.
| Вид сырья | Расход на изделие | Запас | А | Б | 48 | 12 | 600 | 24 | 21 | 840 | 15 | 27 | 1350 | Прибыль | 12 | 18 |
Найти план производства изделий, обеспечивающий предприятию максимальную прибыль от их реализации. Решить задачу графическим методом.
Решение задачи
Экономико-математическая модель задачи
Через и обозначим количество выпускаемой продукции вида А и Б соответственно.
Тогда ограничения на ресурсы:
Кроме того, по смыслу задачи
Целевая функция, выражающая получаемую прибыль от реализации изделий:
Получаем следующую экономико-математическую модель:
Построение чертежа
Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые:
Найдем точки, через которые проходят прямые:
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.
Для определения полуплоскости возьмём любую точку, например точку не принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 1-го неравенства соответствует левая полуплоскость
Возьмём любую точку, например точку не принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 2-го неравенства соответствует левая полуплоскость
Для определения полуплоскости возьмём любую точку, например точку не принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 3-го неравенства соответствует нижняя полуплоскость
Областью допустимых решений является фигура .
Строим вектор , координаты которого пропорциональны коэффициентам целевой функции.
Перпендикулярно к построенному вектору проводим линию уровня .
Нахождение оптимального плана
Перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в крайней точке. Решением на максимум является точка D, координаты которой находим как точку пересечения прямой (2) и оси .
Таким образом, необходимо выпускать 40 ед. изделия Б. Изделие а выпускать невыгодно. При этом прибыль будет максимальной и составит 720 д.е.
Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:
Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой а п х, + + a j2 х 2 = b n i = 1, т. Условия неотрицательности определяют полуплоскости с граничными прямыми х { = 0, х 2 = 0 соответственно. Если система совместна, то полуплоскости, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек; координаты каждой из этих точек являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.
Геометрически ЗЛП представляет собой отыскание такой угловой точки многоугольника решений, координаты которой доставляют максимальное (минимальное) значение линейной целевой функции, причем допустимыми решениями являются все точки многоугольника решений.
Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости.
Определим, какую часть плоскости описывает неравенство 2х { + Зх 2 12.
Во-первых, построим прямую 2х, + Зх 2 =
12. Она проходит через точки (6; 0) и (0; 4). Во-вторых, определим, какая полуплоскость удовлетворяет неравенству. Для этого выбираем любую точку на графике, не принадлежащую прямой, и подставляем ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать начало координат. Подставим х { = х 2 =
0 в неравенство 2х, + Зх 2 12. Получим 2 0 + 3 0
Аналогично графически можно изобразить все ограничения задачи линейного программирования.
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений (ОДР) или областью определения.
Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (Xj > 0, j = 1, п). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении ЗЛП используют вектор-градиент, координаты которого являются частными производными целевой функции:
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая c [ x l + с 2 х 2 = f(x 0), перпендикулярная вектору-градиенту, является линией уровня целевой функции (рис. 2.2.2). В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине а. Меняя значение а, получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Рис. 2.2.2.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в д р у г у ю сторону - только убывает.
Графический метод решения ЗЛП состоит из четырех этапов:
- 1. Строится область допустимых решений (ОДР) ЗЛП.
- 2. Строится вектор-градиент целевой функции (ЦФ) с началом в точке х 0 (0; 0): V = (с, с 2).
- 3. Линия уровня CjXj + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту V, - передвигается в направлении вектора-градиента в случае максимизации целевой функции f(x v х 2) до тех пор, пока не покинет пределов ОДР. При минимизации /(*, х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Крайняя точка (или точки) ОДР при этом движении и является точкой максимума (минимума) f(x p jc 2).
Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимума (максимума) функции f(x р х 2) не существует.
Если линия уровня целевой функции параллельна функциональному ограничению задачи, на котором достигается оптимальное значение ЦФ, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.
4. Определяются координаты точки максимума (минимума). Для этого достаточно решить систему уравнений прямых, дающих в пересечении точку максимума (минимума). Значение f(x { , х 2), найденное в полученной точке, является максимальным (минимальным) значением целевой функции.
Возможные ситуации графического решения ЗЛП представлены в табл. 2.2.1.
Таблица 2.2.1
|
Вид ОДР |
Вид оптимального решения |
|
Ограниченная |
Единственное решение |
|
Бесконечное множество решений |
|
|
Неограниченная |
ЦФ не ограничена снизу |
|
ЦФ не ограничена сверху |
|
|
Единственное решение |
|
|
Бесконечное множество решений |
|
|
Единственное решение |
|
|
Бесконечное множество решений |
Пример 2.2.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).
Намечается выпуск двух видов костюмов - мужских и женских. На женский костюм требуется 1 м шерсти, 2 м лавсана и 1 человекодень трудозатрат; на мужской - 3,5 м шерсти, 0,5 м лавсана и 1 человекодень трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 человекодней трудозатрат.
Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 ден. ед., а от мужского - 20 ден. ед. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
Экономико-математическая модель задачи
Переменные : х, - число женских костюмов; х 2 - число мужских костюмов.
Целевая функция :
Ограничения :
Первое ограничение (по шерсти) имеет вид х { + 3,5х 2 х { + 3,5х 2 = 350 проходит через точки (350; 0) и (0; 100). Второе ограничение (по лавсану) имеет вид 2х { + 0,5х 2 2х х + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение (по труду) имеет вид х у +х 2 150. Прямая х { + х 2 = 150 проходит через точки (150; 0) и (0; 150). Четвертое ограничение (по количеству мужских костюмов) имеет вид х 2 > 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60.
В результате пересечения построенных четырех полуплоскостей получаем многоугольник, который и является областью допустимых решений нашей задачи. Любая точка этого многоугольника удовлетворяет всем четырем функциональным неравенствам, а для любой точки вне этого многоугольника хотя бы одно неравенство будет нарушено.
На рис. 2.2.3 затенена область допустимых решений (ОДР). Для определения направления движения к оптимуму построим вектор- градиент V, координаты которого являются частными производными целевой функции:
Чтобы построить такой вектор, нужно соединить точку (10; 20) с началом координат. Для удобства можно строить вектор, пропорциональный вектору V. Так, на рис. 2.2.3 изображен вектор (30; 60).
Затем построим линию уровня 10xj + 20х 2 = а. Приравняем целевую функцию постоянной величине а. Меняя значение а , получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции:
Далее будем передвигать линию уровня до ее выхода из ОДР. В нашем случае (при максимизации целевой функции) движение линии уровня будем осуществлять в направлении градиента. В крайней угловой точке достигается максимум целевой функции. Для нахождения координат этой точки решаем систему из двух уравнений прямых, дающих в пересечении точку максимума:
Получаем
При этих значениях
Ответ. Для получения максимальной прибыли (2300) необходимо сшить 70 женских (xj 1 = 70) и 80 мужских (х 2 = 80) костюмов.
Рис. 2.2.3. Точка (70; 80) - оптимальное решение задачи Пример 2.2.2. Найти максимум и минимум f(X ):
при ограничениях
Решение. При решении данного примера на максимум возникает ситуация, когда линия уровня Зх, + 3х 2 = а параллельна первому ограничению: х х +х 2 8. Целевая функция достигает максимального значения в двух точках: А (3; 5) и В (6; 2) - и принимает на отрезке АВ одно и то же значение, равное 24:
При решении данного примера на минимум целевой функции линию уровня 3xj + 3х 2 - а следует двигать в направлении, обратном направлению вектора-градиента. Целевая функция достигает минимального значения в точке D (0,5; 0):
Графическое решение примера приведено на рис. 2.2.4.
Рис. 2.2.4.
Ответ: max /(2Q = 24; min /(X) = 1,5. Пример 2.2.3. Найти максимум /(X):
при ограничениях
Решение. Задача не имеет решения, так как ЦФ не ограничена сверху на ОДР (рис. 2.2.5).
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).
Назначение сервиса . С помощью данного сервиса можно в онлайн режиме решить задачу линейного программирования геометрическим методом, а также получить решение двойственной задачи (оценить оптимальность использования ресурсов). Дополнительно создается шаблон решения в 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 дан в таблице.
Таблица - Расход сырья на производство продукции
Требуется определить:
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализации продукции был максимальным?
- Сформулировать математическую модель задачи линейного программирования.
- Решить задачу линейного программирования графическим способом (для двух переменных).
Сформулируем математическую модель задачи линейного программирования.
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 . Составить математическую модель задачи линейного программирования и найти решение геометрическим способом.
- Составить систему математических зависимостей (неравенств) и целевую функцию.
- Изобразить геометрическую интерпретацию задачи.
- Найти оптимальное решение.
- Провести аналитическую проверку.
- Определить существенные и несущественные ресурсы и их избытки.
- Определить значение целевой функции.
- Вычислить объективно обусловленные оценки.
- Составить соотношение устойчивости.
Задача. Решить графически задачу линейного программирования, определив экстремальное значение целевой функции:
при ограничениях
Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом).
Построим уравнение 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