Графический способ онлайн. Решение задач линейного программирования симплекс-методом
Краткая теория
Линейное программирование - раздел математического программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные. По типу решаемых задач его методы разделяются на универсальные и специальные. С помощью универсальных методов могут решаться любые задачи линейного программирования (ЗЛП). Специальные методы учитывают особенности модели задачи, ее целевой функции и системы ограничений. Особенностью является то, что экстремума целевая функция достигает на границе области допустимых решений.
Графический метод решения задач линейного программирования дает возможность наглядно представить их структуру, выявить особенности и открывает пути исследования более сложных свойств. Задачу линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическое решение, вообще говоря, невозможно. Случай двух переменных не имеет особого практического значения, однако его рассмотрение проясняет свойства ограничений ЗЛП, приводит к идее ее решения, делает геометрически наглядными способы решения и пути их практической реализации.
Если ограничения и целевая функция содержит более двух переменных, тогда необходимо (или методом последовательного улучшения решения) - он универсален и им можно решить любую ЗЛП. Для некоторых прикладных задач линейного программирования, таких как , разработаны специальные методы решения.
Пример решения задачи
Условие задачи
Предприятие выпускает два вида продукции: Изделие 1 и Изделие 2. На изготовление единицы Изделия 1 требуется затратить кг сырья первого типа, кг сырья второго типа, кг сырья третьего типа. На изготовление единицы Изделия 2 требуется затратить кг первого типа, сырья второго типа, сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве кг, кг, кг соответственно. Рыночная цена единицы Изделия 1 составляет тыс руб., а единицы Изделия 2 - тыс. руб.
Требуется:
- Построить математическую модель задачи.
- Составить план производства изделий, обеспечивающий максимальную выручку от их реализации при помощи графического метода решения задачи линейного программирования.
Решение задачи
Построение модели
Через и обозначим количество выпускаемых изделий 1-го и 2-го типа.
Тогда ограничения на ресурсы:
Кроме того, по смыслу задачи
Целевая функция экономико-математической модели, выражающая получаемую от реализации выручку:
Получаем следующую экономико-математическую модель:
Построение области допустимых решений
Решим полученную задачу линейного программирования графическим способом:
Для построения области допустимых решений строим в системе координат соответствующие данным ограничениям-неравенствам граничные прямые:
Найдем точки, через которые проходят прямые:
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.
Для определения полуплоскости возьмём любую точку, например , не принадлежащую прямой (1), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 1-го неравенства соответствует левая полуплоскость
Возьмём любую точку, например , не принадлежащую прямой (2), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Возьмём любую точку, например , не принадлежащую прямой (3), подставим координаты (0;0) в соответствующее неравенство. Т.к. неравенство верно:
Области решений соответствующего 2-го неравенства соответствует левая полуплоскость
Областью допустимых решений является фигура .
Нахождение решения задачи ЛП
Строим вектор , координаты которого пропорциональны коэффициентам целевой функции. Здесь - коэффициент пропорциональности.
Перпендикулярно к построенному вектору проводим линию уровня .
Перемещаем линию уровня в направлении вектора так, чтобы она касалась области допустимых решений в крайней точке. Решением на максимум является точка , координаты которой находим как точку пересечения прямых (2) и (1).
Ответ
Таким образом необходимо выпускать 56 изделий 1-го вида и 64 изделия 2-го вида. При этом выручка от реализации изделий будет максимальна и составит 5104 ден.ед.
Метод графического решения, если задача с двумя переменными имеет линейные ограничения, а целевая функция - квадратичная, подробно рассмотрен .
На цену сильно влияет срочность решения (от суток до нескольких часов). Онлайн-помощь на экзамене/зачете осуществляется по предварительной записи.
Заявку можно оставить прямо в чате, предварительно скинув условие задач и сообщив необходимые вам сроки решения. Время ответа - несколько минут.
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).
Назначение сервиса . С помощью данного сервиса можно в онлайн режиме решить задачу линейного программирования геометрическим методом, а также получить решение двойственной задачи (оценить оптимальность использования ресурсов). Дополнительно создается шаблон решения в 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 . Составить математическую модель задачи линейного программирования и найти решение геометрическим способом.
- Составить систему математических зависимостей (неравенств) и целевую функцию.
- Изобразить геометрическую интерпретацию задачи.
- Найти оптимальное решение.
- Провести аналитическую проверку.
- Определить существенные и несущественные ресурсы и их избытки.
- Определить значение целевой функции.
- Вычислить объективно обусловленные оценки.
- Составить соотношение устойчивости.
≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 487, 5, -7623 и т.д.), десятичных чисел (напр. 67., 102.54 и т.д.) или дробей. Дробь нужно набирать в виде a/b, где a и b (b>0) целые или десятичные числа. Примеры 45/5, 6.6/76.4, -7/6.7 и т.д.
Симплекс метод
Примеры решения ЗЛП симплекс методом
Пример 1. Решить следующую задачу линейного программирования:
 |
Правая часть ограничений системы уравнений имеет вид:
Запишем текущий опорный план:
 |
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор x
при 
. min
(40:6, 28:2)=20/3 соответствует строке 1. Из базиса выходит вектор x
3 . Сделаем исключение Гаусса для столбца x
2 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на -1/3, 1/6, 1/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-3), следовательно в базис входит вектор x
1 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. min(44/3:11/3, 62/3:5/3)=4 соответствует строке 2. Из базиса выходит вектор x
4 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 2. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 3, 4 со строкой 2, умноженной на 1/11, -5/11, 9/11, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4 под переменными 
нет отрицательных элементов.
Решение можно записать так: 
.
Значение целевой функции в данной точке: F
(X
)=
.
Пример 2. Найти максимум функции
Р е ш е н и е.
Базисные векторы x 4 , x 3 , следовательно, все элементы в столбцах x 4 , x 3 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 1, умноженной на 4. Обнулим все элементы столбца x 3 , кроме ведущего элемента. Для этого сложим строку 3 со строкой 2, умноженной на 1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательный элемент (-11), следовательно в базис входит вектор x
2 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
. Все следовательно целевая функция неограничена сверху. Т.е. задача линейного программирования неразрешима.
Примеры решения ЗЛП методом искусственного базиса
Пример 1. Найти максимум функции
Р е ш е н и е. Так как количество базисных векторов должен быть 3, то добавляем искусственное переменное, а в целевую функцию добавляем это переменное, умноженное на −M, где M, очень большое число:
 |
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы следовательно, все элементы в столбцах ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-5), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор Сделаем исключение Гаусса для столбца учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строку 5 со строкой 3, умноженной на 1. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-3), следовательно в базис входит вектор Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 1. Из базиса выходит вектор x
2 . Сделаем исключение Гаусса для столбца x
1 , учитывая, что ведущий элемент соответствует строке 1. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 2, 3, 4 со строкой 1, умноженной на 3/2, -1/10, 3/2, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Данный опорный план не является оптимальным, так как в последней строке есть отрицательные элементы. Самый большой по модулю отрицательный элемент (-13/2), следовательно в базис входит вектор x
3 . Определяем, какой вектор выходит из базиса. Для этого вычисляем 
при 
соответствует строке 3. Из базиса выходит вектор x
5 . Сделаем исключение Гаусса для столбца x
3 , учитывая, что ведущий элемент соответствует строке 3. Обнулим все элементы этого столбца, кроме ведущего элемента. Для этого сложим строки строки 1, 2, 4 со строкой 3, умноженной на 5/3, 25/9, 65/9, соответственно. Далее делим строку с ведущим элементом на ведущий элемент.
Симплекс таблица примет следующий вид:
Текущий опорный план является оптимальным, так как в строках 4−5 под переменными нет отрицательных элементов.
Решение исходной задачи можно записать так:
Пример 2. Найти оптимальный план задачи линейного программирования:
Матрица коэффициентов системы уравнений имеет вид:
Базисные векторы x 4 , x 5 , x 6 , следовательно, все элементы в столбцах x 4 , x 5 , x 6 , ниже горизонтальной линии должны быть нулевыми.
Обнулим все элементы столбца x 4 , кроме ведущего элемента. Для этого сложим строку 4 со строкой 1, умноженной на -1. Обнулим все элементы столбца x 5 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 2, умноженной на -1. Обнулим все элементы столбца x 6 , кроме ведущего элемента. Для этого сложим строку 5 со строкой 3, умноженной на -1.
Симплекс таблица примет вид:
В строке 5 элементы, соответствующие переменным x 1 , x 2 , x 3 , x 4 , x 5 , x 6 неотрицательны, а число находящийся в пересечении данной строки и столбца x 0 отрицательнo. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
Наиболее простым и наглядным методом решения задачи линейного программирования (ЗЛП) является графический метод. Он основан на геометрической интерпретации задачи линейного программирования и применяется при решении ЗЛП с двумя неизвестными:
Будем рассматривать решение этой задачи на плоскости. Каждое неравенство системы функциональных ограничений геометрически определяет полуплоскость с граничной прямой а п х, + + 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).
Цель работы
1. Изучить понятие математической модели.
2. Рассмотреть примеры задач линейного программирования.
3. Усвоить графический метод решения задач линейного программирования.
4. Научиться приведению задач линейного программирования к стандартной форме.
Теоретическое введение
Понятие математической модели. Математическая модель в задачах линейного программирования (ЛП)
Линейное программирование – это раздел высшей математики, посвященный решению задач, связанных с нахождением экстремумов функций нескольких переменных при наличии ограничений на переменные. Методами линейного программирования решаются задачи о распределении ресурсов, планировании выпуска продукции, ценообразовании, транспортные задачи и т.п.
Любое описание некоторой задачи в виде формул, алгоритмов называется математической моделью этой задачи.
Построение математической модели задачи включает следующие этапы:
1) выбор переменных задачи;
2) составление системы ограничений;
3) выбор целевой функции.
Переменными задачи называются величины х 1 , х 2 , …х n , которые полностью характеризуют экономический процесс. Их обычно записывают в виде вектора A = (х 1 , х 2 , …х n).
Система ограничений включает в себя систему уравнений и неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических или физических условий.
Целевой функцией называют функцию переменных задачи, которая характеризует качество выполнения задачи, и экстремум которой требуется найти.
Общая задача математического программирования формулируется следующим образом:
найти экстремум целевой функции и соответствующие ему переменные при условии, что эти переменные удовлетворяют системе ограничений и условиям неотрицательности.
Функция (1.1) называется целевой функцией, а ограничения (1.2) – системой ограничений задачи.
Если по условию задачи требуется найти такие значения переменных, при которых целевая функция (1.1) будет иметь максимальное значение, то говорят, что целевая функция подлежит максимизации (или направлена на максимум). Если требуется, чтобы целевая функция принимала минимальное значение, то говорят, что она подлежит минимизации (направлена на минимум).
Обратите внимание на полученный результат. Целевая функция является линейной функцией переменных х 1 , х 2 , …х n ; сами ограничения на значения переменных х 1 , х 2 , …х n имеют вид линейных неравенств. Все это и определило название этого класса задач – задачи линейного программирования .
В большинстве задач (но не всегда) требуется, чтобы переменные принимали неотрицательные значения (ограничение на неотрицательность); в некоторых задачах требуется, чтобы переменные принимали целочисленные значения (ограничения на целочисленность).
Линейная математическая модель может быть построена для многих задач, решаемых на практике.
Любые значения переменных, удовлетворяющие ограничениям задачи (1.2), называются допустимыми решениями (независимо от того, какое значение при этом принимает целевая функция). Большинство задач имеет бесконечно много допустимых решений. Все множество допустимых решений представляет собой область допустимых решений (ОДР).
Допустимые значения переменных, при которых целевая функция принимает максимальное или минимальное значение (в зависимости от постановки задачи), т.е. достигает экстремума, представляют собой оптимальное решение.
Методика выполнения работы
Примеры задач ЛП
Пример 1.1. Предприятие химической промышленности выпускает соляную и серную кислоту. Выпуск одной тонны соляной кислоты – 25 денежных единиц (ден. ед.)., выпуск одной тонны серной кислоты – 40 ден. ед. Для выполнения государственного заказа необходимо выпустить не менее 200 т соляной и не менее 100 т серной кислоты. Кроме того, необходимо учитывать, что выпуск кислот связан с образованием опасных отходов. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов, при выпуске одной тонны серной кислоты – 1,2 т опасных отходов. Общее количество опасных отходов не должно превышать 600 т, так как превышение этого ограничения приведет к выплате предприятием крупного штрафа.
Требуется определить, сколько соляной и серной кислоты должно выпустить предприятие, чтобы получить максимальную прибыль.
Составим математическую модель задачи . Для этого введем переменные. Обозначим через x 1 количество выпускаемой соляной кислоты (в тоннах), через x 2 – количество серной кислоты.
Составим ограничения, связанные с необходимостью выполнения государственного заказа. Предприятию необходимо выпустить не менее 200 т соляной кислоты. Это ограничение можно записать следующим образом: x 1 200. Аналогично составим ограничение, устанавливающее, что предприятие должно выпустить не менее 100 т серной кислоты: x 2 100.
Составим ограничение на опасные отходы. При выпуске одной тонны соляной кислоты образуется 0,5 т опасных отходов; значит, общее количество опасных отходов при выпуске соляной кислоты составит 0,5x 1 т. При выпуске серной кислоты образуется 1,2x 2 т опасных отходов. Таким образом, общее количество опасных отходов составит 0,5x 1 +1,2x 2 т. Эта величина не должна превышать 600 т. Поэтому можно записать следующее ограничение: 0,5x 1 +1,2x 2 600 .
Кроме того, переменные по своему физическому смыслу не могут принимать отрицательных значений, так как они обозначают количество выпускаемых кислот. Поэтому необходимо учитывать ограничения неотрицательности: x 1 0; x 2 0.
В данной задаче требуется определить выпуск кислот, при котором прибыль будет максимальной. Прибыль от выпуска одной тонны соляной кислоты составляет 25 ден. ед.; значит прибыль от выпуска соляной кислоты составит 25x 1 ден. ед. Прибыль от выпуска серной кислоты составит 40x 2 ден. ед. Таким образом, общая прибыль от выпуска кислот составит 25x 1 +40x 2 ден. ед. Требуется найти такие значения переменных x 1 и x 2 , при которых эта величина будет максимальной. Таким образом, целевая функция для данной задачи будет иметь следующий вид:
Е=25x 1 +40x 2 → max.
Приведем полную математическую модель рассматриваемой задачи:
0,5x 1 +1,2x 2 600
Е=25x 1 +40x 2 → max.
В этой задаче имеется два ограничения «больше или равно» и одно ограничение «меньше или равно». Целевая функция подлежит максимизации.
Пример 1.2. Пусть в условиях задачи 1.1 из-за ужесточения требований к экологической безопасности требуется свести к минимуму количество опасных отходов. В то же время необходимо учитывать, что для того, чтобы производство кислот было экономически целесообразным, необходимо получить прибыль не менее 20 тыс. ден. ед.
Математическая модель такой задачи имеет следующий вид:
25x 1 +40x 2 20000
Е= 0,5x 1 +1,2x 2 → min.
Третье ограничение в этой модели устанавливает, что прибыль от выпуска кислот должна составлять не менее 20 тыс. ден.ед. Целевая функция представляет собой количество опасных отходов; эта величина подлежит минимизации.
Графический метод решения задач ЛП
Графический метод применяется для решения задач, в которых имеются только две переменные. Для таких задач имеется возможность графически изобразить область допустимых решений (ОДР).
Примечание . Графический метод может применяться также для решения задач с любым количеством переменных, если возможно выразить все переменные задачи через какие-либо две переменные.
Как отмечено выше, ОДР – это множество значений переменных, удовлетворяющих ограничениям (1.2). Таким образом, для задач с двумя переменными ОДР представляет собой множество точек (x 1 ; x 2), т.е. некоторую область на плоскости (обычно многоугольник). Для задач с тремя переменными ОДР представляет собой многогранник в пространстве, для задач с большим количеством переменных – некоторую область многомерного пространства. Можно доказать, что экстремум (минимум или максимум) целевой функции всегда достигается при значениях переменных, соответствующей одной из угловых точек ОДР. Другими словами, оптимальное решение всегда находится в угловой точке ОДР. Поэтому задачу линейного программирования с двумя переменными можно решить следующим образом: построить ОДР на плоскости в системе координат (x 1 ; x 2), определить все угловые точки ОДР, вычислить значения целевой функции в этих точках и выбрать оптимальное решение.
Решим графическим методом задачу из примера 1.1.
Решение показано на рис. 1.1.
Рис. 1.1 Решение примера 1.1 графическим методом
Ограничение x 1 200 задается вертикальной линией x 1 =200. Все точки (x 1 ; x 2), расположенные справа от этой линии, удовлетворяют ограничению x 1 200, расположенные слева – не удовлетворяют. Ограничение x 2 100 задается горизонтальной линией x 2 =100. Все точки, расположенные сверху от этой линии, удовлетворяют ограничению x 2 100, расположенные снизу – не удовлетворяют.
Для построения линии, задающей ограничение 0,5x 1 +1,2x 2 600, удобно записать его в виде равенства: 0,5x 1 +1,2x 2 =600 . Выразим одну из переменных через другую: x 2 =-0,41x 1 +500. это уравнение прямой. Построим эту прямую. Она разбивает координатную плоскость на две полуплоскости. В одной из этих полуплоскостей находятся точки, удовлетворяющие ограничению, в другой – не удовлетворяющие. Чтобы найти полуплоскость, удовлетворяющую ограничению 0,5x 1 +1,2x 2 600, подставим в него координаты любой точки, например, (0; 0). Для этой точки ограничение выполняется. Значит, она находится в полуплоскости, удовлетворяющей ограничению.
Пересечение всех полуплоскостей, удовлетворяющих ограничениям задачи, представляет собой ОДР. На рис. 1.1 она выделена серым цветом.
Оптимальное решение находится в одной из угловых точек ОДР (на рис. 1.1 они обозначены как А, В, С). Эти точки можно найти из построенного графика или путем решения соответствующих систем из двух уравнений. Найдем значения целевой функции в этих точках:
Е(А) = 25∙200 + 40∙100=9000;
Е(В) = 25∙200 + 40∙416,67 = 21666,8;
Е(С) = 25∙960 + 40∙100 = 28000.
Таким образом, оптимальное решение находится в точке С= (960; 100). Это означает, что предприятию следует выпустить 960 т соляной кислоты и 100 т серной кислоты. Прибыль при этом составит 28000 ден.ед. Можно также найти количество опасных отходов, которое будет получено при производстве кислот: 0,5 960 + 1,2∙100 = 600 т.
Решим графическим методом задачу из примера 1.2. Решение показано на рис. 1.2.
Рис. 1.2 Решение задачи 1.2 графическим методом
В данном случае ОДР имеет только две угловые точки (А и В). Найдем для них значение целевой функции:
Е(А)= 0,5 ∙200+1,2 ∙ 375 =550;
Е (В) = 0,5 ∙640+1,2∙100 =440.
Таким образом, оптимальное решение находится в точке В(640; 100). Это означает, что предприятию следует выпустить 640 т соляной и 100 т серной кислоты. При этом образуется 440 т опасных отходов. Можно также найти прибыль от производства кислот: 25 ∙ 640 + 40 ∙100 = 20 000 ден.ед.
Статьи по теме
