≤ = ≥ |
≤ = ≥ |
≤ = ≥ |
×
Предупреждение
Очистить все ячейки?
Закрыть Очистить
Инструкция ввода данных. Числа вводятся в виде целых чисел (примеры: 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. Тогда исходная задача не имеет опорного плана. Следовательно она неразрешима.
Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.
Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.
Все вышесказанное относится и к случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство
можно представить в виде системы двух неравенств (см. рис.2.1)
ЦФ при фиксированном значении определяет на плоскости прямую линию. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня .
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора.
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки. Оптимальной считается точка, через которую проходит линия уровня, соответствующая наибольшему (наименьшему) значению функции. Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.
Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.
Методика решения задач ЛП графическим методом.
I. В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые.
II. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.
Если неравенство истинное,
то надо заштриховать полуплоскость, содержащую данную точку;
иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.
Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси, т.е. в I-м квадранте.
Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.
III. Определить ОДР как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделить ее. При отсутствии ОДР задача не имеет решений.
IV. Если ОДР - не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L - произвольное число, например, кратное и, т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.
V. Построить вектор, который начинается в точке (0;0) и заканчивается в точке. Если целевая прямая и вектор построены верно, то они будут перпендикулярны .
VI. При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора, при поиске минимума ЦФ - против направления вектора. Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).
VII. Определить координаты точки max (min) ЦФ и вычислить значение ЦФ. Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится.
Цель работы
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 ден.ед.
Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными. Рассмотрим задачу ЛП в стандартной форме:
max f(x 1 , x 2 , ..., x n) = ,
, i = 1, 2, …, m,
x j 0, j = 1, 2, …, n.
Положим n=2 и будем рассматривать задачу на плоскости. Пусть система неравенств совместна (имеет хотя бы одно решение).
Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой а i 1 х 1 + а i 2 х 2 = b i , i = 1, 2,…, m. Условия неотрицательности определяют полуплоскости с граничными прямыми х 1 = 0, х 2 = 0 соответственно. Система совместна, поэтому полуплоскости, как выпуклые множества, пересекаясь, образуют общую часть, которая является выпуклым множеством и представляет собой совокупность точек, где координаты каждой точки являются решением данной системы. Совокупность этих точек называют многоугольником решений. Он может быть точкой, отрезком, лучом, ограниченным и неограниченным многоугольником.
Таким образом, геометрически ЗЛП представляет собой отыскание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений.
Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает некоторую область на плоскости. Определим, какую часть плоскости описывает неравенство 2х 1 + Зх 2 12.
Во-первых, построим прямую 2х 1 + Зх 2 = 12. Она проходит через точки (6; 0) и (0; 4). Для того чтобы определить, какая полуплоскость удовлетворяет неравенству, необходимо выбрать любую точку на графике, не принадлежащую прямой, и подставить ее координаты в неравенство. Если неравенство будет выполняться, то данная точка является допустимым решением, и полуплоскость, содержащая точку, удовлетворяет неравенству. Для подстановки в неравенство удобно использовать точку начала координат. Подставим х 1 = х 2 = 0 в неравенство 2х 1 + Зх 2 12. Получим 2х0 + 3х0 12. Данное утверждение является верным, следовательно, неравенству 2х 1 + Зх 2 12 соответствует нижняя полуплоскость, содержащая точку (0; 0). Это отражено на графике, изображенном на рис. 1.1.
Аналогично графически можно изобразить все ограничения задачи ЛП.
Решением каждого неравенства системы ограничений ЗЛП является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее. Пересечение полуплоскостей, каждая из которых определяется соответствующим неравенством системы, называется областью допустимых решений, или областью определения. Необходимо помнить, что область допустимых решений удовлетворяет условиям неотрицательности (х j 0, j = 1, 2, …, n). Координаты любой точки, принадлежащей области определения, являются допустимым решением задачи.
Для нахождения экстремального значения целевой функции при графическом решении задач ЛП используют вектор-градиент, координаты которого являются частными производными целевой функции, т.е.
Этот вектор показывает направление наискорейшего изменения целевой функции. Прямая с 1 х 1 + с 2 х 2 = f(х 0) , перпендикулярная вектору-градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение. Приравняем целевую функцию постоянной величине «а» . Меняя значение «а», получим семейство параллельных прямых, каждая из которых является линией уровня целевой функции.
Важное свойство линии уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону - только убывает.
С геометрической точки зрения в задаче линейного программирования ищется такая угловая точка или набор точек из допустимого множества решений, на котором достигается самая верхняя (нижняя) линия уровня, расположенная дальше (ближе) остальных в направлении наискорейшего роста.
Графический метод решения ЗЛП состоит из следующих этапов.
1. Строится многоугольная область допустимых решений (ОДР) ЗЛП.
2. Строится вектор-градиент целевой функции (ЦФ) в какой-нибудь точке х 0 , принадлежащей ОДР:
3. Линия уровня с 1 х 1 + с 2 х 2 = а (а - постоянная величина) - прямая, перпендикулярная вектору-градиенту , - передвигается в направлении этого вектора в случае максимизации f(x 1 , х 2) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума f(x 1 , х 2).
4. Для нахождения координат точки максимума достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение f(x 1 , х 2), найденное в получаемой точке, является максимальным.
При минимизации (максимизации) функции f(x 1 , х 2) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая, соответствующая линии уровня, при своем движении не покидает ОДР, то минимум (максимум) функции f(x 1 , х 2) не существует.
Если линия уровня параллельна какому-либо функциональному ограничению задачи, то оптимальное значение ЦФ будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП. Возможные ситуации графического решения задач ЛП представлены в табл. 1.3.
Таблица 1.3
| № | Вид ОДР | Вид оптимального решения | Примечания |
| Многоугольная замкнутая | Единственное решение | ||
| Единственное решение | |||
| Многоугольная | ЦФ не ограничена снизу | ||
| ЦФ не ограничена сверху | |||
| Многоугольная незамкнутая | Единственное решение | ||
| Бесконечное множество решений | |||
| Отрезок | Единственное решение |
Рассмотрим графическое решение задач линейного программирования на следующем примере.
Пример 1.1. Планирование выпуска продукции пошивочного предприятия (задача о костюмах).
Намечается выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1м шерсти, 2м лавсана и 1 чел./день трудозатрат. На мужской костюм – 3,5м шерсти, 0,5м лавсана и 1 чел./день трудозатрат. Всего имеется 350м шерсти, 240м лавсана и 150 чел./дней трудозатрат. Требуется определить, сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, а от мужского – 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.
Введем следующие обозначения: х 1 - число женских костюмов; х 2 – число мужских костюмов. Прибыль от реализации женских костюмов составляет 10х 1 , а от реализации мужских - 20х 2 , т.е. необходимо максимизировать целевую функцию:
10х 1 + 20х 2
Ограничения задачи имеют вид:
х 1 + х 2 150,
2 х 1 + 0,5х 2 240,
х 1 + 3,5х 2 350,
х 2 60,
х 1 0.
Первое ограничение по труду х 1 + х 2 150. Прямая х 1 + х 2 = 150 проходит через точки (150; 0) и (0; 150) (рис. 1.2).
Второе ограничение по лавсану 2 х 1 + 0,5х 2 240. Прямая 2 х 1 + 0,5х 2 = 240 проходит через точки (120; 0) и (0; 480). Третье ограничение по шерсти х 1 + 3,5х 2 350. Добавим четвертое ограничение по количеству мужских костюмов х 2 60. Решением этого неравенства является полуплоскость, лежащая выше прямой х 2 = 60. На рис. 1.3 заштрихована область допустимых решений. Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.
Чтобы построить такой вектор, нужно соединить точку (10;20) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации – в противоположном направлении. Для удобства можно строить вектор, пропорциональный вектору . Так, на рис. 1.4 изображен вектор-градиент (30;60).
Для определения направления движения к оптимуму построим вектор-градиент , координаты которого являются частными производными целевой функции, т.е.
В нашем случае движение линии уровня будем осуществлять до ее выхода из области допустимых решений. В крайней, угловой, точке достигается максимум целевой функции. Для нахождения координат этой точки достаточно решить два уравнения прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума:
х 1 + 3,5х 2 = 350,
х 1 + х 2 = 150.
Отсюда легко записать решение исходной ЗЛП: max f(x) = 2300 и достигается при х 1 = 70 и х 2 = 80 (см. рис. 1.4).
1.3.ТЕХНОЛОГИЯ РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ С ПОМОЩЬЮ НАДСТРОЙКИ ПОИСК РЕШЕНИЯ В СРЕДЕ EXCEL
1.3.1. Общие сведения о работе с табличным процессором Excel
Рассмотрим некоторые аспекты работы с табличным процессором Excel, которые позволят упростить расчеты, необходимые для решения оптимизационных задач. Табличный процессор - это программный продукт, предназначенный для автоматизации обработки данных табличной формы.
Элементы экрана Excel. После запуска Excel на экране появляется таблица, вид которой показан на рис 1.5.
Это изображение называют рабочим листом. Оно представляет собой сетку строк и столбцов, пересечения которых образуют прямоугольники, называемые ячейками. Рабочие листы предназначены для ввода данных, выполнения расчетов, организации информационной базы и т.п. Окно Excel отображает основные программные элементы: строку заголовка, строку меню, строку состояния, кнопки управления окнами.
Работа с формулами. В программах электронных таблиц формулы служат для выполнения множества разнообразных расчетов. С помощью Excel можно быстро создать формулу. Формула состоит из трех основных частей:
1) знака равенства;
2) совокупности значений или ссылок на ячейках, с которыми выполняются расчеты;
3) операторов.
4) Если знак равенства отсутствует, то Excel интерпретирует данные не как формулу, а как ввод данных в ячейку. Формулы можно вводить непосредственно в ячейку или в строку формул – как текст, так и число. При этом нужно выполнить следующие действия:
· выделить ячейку, которая должна содержать формулу и ввести знак (=);
· ввести оператор или знак действия;
· выделить другую ячейку, включаемую в формулу;
· нажать на клавишу Enter.
В строке формул появится введенная формула, в ячейке – результат расчета.
Использование в формулах функций. Чтобы облегчить ввод формул, можно воспользоваться функциями Excel. Функции - это встроенные в Excel формулы. Excel содержит множество формул. Они сгруппированы по различным типам: логические, математические, инженерные, статистические и др.
Для активизации той или иной формулы следует нажать кнопки Вставка, Функции. В появившемся окне Мастер функций слева содержится перечень типов функций. После выбора типа справа будет помещен список самих функций. Выбор функции осуществляется щелчком клавиши мыши на соответствующем названии.
Различные функции выполняют разные типы вычислений по определенным правилам. Когда функция является единичным объектом в ячейке рабочего листа, она начинается со знака (=), далее следует название функции, а затем - аргументы функции, заключенные в скобки.
Поиск решения - это надстройка Excel, которая позволяет решать оптимизационные задачи. Если в меню Сервис отсутствует команда Поиск решения, значит, необходимо загрузить эту надстройку. Выберите команду Сервис => Надстройки и активизируйте надстройку Поиск решения. Если же этой надстройки нет в диалоговом окне Надстройки, то вам необходимо обратиться к панели управления Windows, щелкнуть на пиктограмме Установка и удаление программ и с помощью программы установки Excel (или Office) установить надстройку Поиск решения.
После выбора команд Сервис => Поиск решения появится диалоговое окно Поиск решения.
В диалоговом окне Поиск решения есть три основных параметра;
Установить целевую ячейку.
Изменяя ячейки.
Ограничения.
Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или установить конкретное значение.
Второй важный параметр средства Поиск решения - это параметр Изменяя ячейки. Здесь указываются ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К этим ячейкам предъявляется два основных требования: они не должны содержать формул и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависит от изменяемых ячеек.
Третий параметр, который нужно вводить на вкладке Поиск решения, - это ограничения.
Для решения задачи необходимо:
1) указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки);
2) ввести исходные данные;
3) ввести зависимость для целевой функции;
4) ввести зависимости для ограничении,
5) запустить команду Поиск решений;
6) назначить ячейку для целевой функции (установить целевую ячейку);
7) ввести ограничения;
8) ввести параметры для решения ЗЛП.
Рассмотрим технологию решения, используя условия примера 1.1 (задача о костюмах).
Экономико-математическая модель задачи
Пусть х 1 - число женских костюмов; х 2 - число мужских костюмов,
10 х х 1 + 20 х х 2 max
Ограничения задачи имеют вид:
х 1 + х 2 150 - ограничение по труду;
2 x х 1 + 0,5 х х 2 240 - ограничение по лавсану;
х 1 + 3,5 х х 2 350 - ограничение по шерсти;
х 2 60 - ограничение по мужским костюмам;
х 1 0 - ограничение по женским костюмам.
1. Указать адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки).
Обозначьте через x 1 , х 2 количество костюмов каждого типа. В нашей задаче оптимальные значения вектора = (х 1 , х 2) будут помещены в ячейках А2:В2, оптимальное значение целевой функции - в ячейке СЗ.
2. Ввести исходные данные.
Введите исходные данные задачи, как показано на рис. 1.6.
3. Ввести зависимость для целевой функции.
· Поместить курсор в ячейку «СЗ», произойдет выделение ячейки.
· Поместить курсор на кнопку Мастер функций, расположенную на панели инструментов.
· Ввести Enter. На экране появляется диалоговое окно Мастер функций шаг 1 из 2.
· В окне Функции выбрать строку СУММПРОИЗВ (рис. 1.7). На экране
· появляется диалоговое окно СУММПРОИЗВ (рис. 1.8).
· В строку Массив 1 ввести А2:В2 .
· В строку Массив 2 ввести АЗ:ВЗ.
Массив 1 будет использоваться при вводе зависимостей для ограничений, поэтому на этот массив надо сделать абсолютную ссылку. На рис. 1.9 показано, что в ячейку СЗ введена функция.
5. Ввести зависимости для ограничений (рис 1.10).
· Поместить курсор в ячейку СЗ.
· На панели инструментов кнопка Копировать в буфер.
· Поместить курсор в ячейку С4.
· Поместить курсор в ячейку С5.
· На панели инструментов кнопка Вставить из буфера.
· Поместить курсор в ячейку Сб.
· На панели инструментов кнопка Вставить из буфера.
· Поместить курсор в ячейку С7.
· На панели инструментов нажать кнопку Вставить из буфера. (Содержимое ячеек С4-С7 необходимо проверить. Они обязательно должны содержать информацию, как это показано для примера на рис. 1.11; в качестве примера представлено содержимое ячейки С5.)
· В строке Меню указатель мышки поместить на Сервис. В развернутом меню выбрать команду Поиск решения. Появляется диалоговое окно Поиск решения (рис. 1.12).
5. Запустить команду Поиск решения.
6. Назначить ячейку для целевой функции (установить целевую ячейку), указать адреса изменяемых ячеек.
· Поместить курсор в строку Установить целевую ячейку.
· Ввести адрес ячейки $С$3.
· Ввести тип целевой функции в зависимости от условия вашей задачи. Для этого отметьте, чему равна целевая функция - Максимальному значению или Минимальному значению.
· Поместить курсор в строку Изменяя ячейки.
· Ввести адреса искомых переменных А$2:В$2 (рис. 1.13).
7. Ввести ограничения.
· Поместить указатель мыши на кнопку Добавить. Появляется диалоговое окно Добавление ограничения.
· Ввести знак ограничения.
· В строке Ограничение ввести адрес $D$4 (рис. 1.14).
· Поместить указатель мыши на кнопку Добавить. На экране вновь появится диалоговое окно Добавление ограничения.
· Ввести остальные ограничения задачи по вышеописанному алгоритму.
· После введения последнего ограничения нажать на кнопку ОК. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.15).
8. Ввести параметры для решения задачи линейного программирования.
· В диалоговом окне поместить указатель мышки на кнопку Параметры. На экране появится диалоговое окно Параметры поиска решения (рис. 1.16).
· Установить флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения.
· Поместить указатель мыши на кнопку ОК. На экране появится диалоговое окно Поиск решения.
· Поместить указатель Мыши на кнопку Выполнить.
Через непродолжительное время появятся диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками АЗ:ВЗ для значений х i и ячейка СЗ с максимальным значением целевой функции (рис. 1.17).
Если указать тип отчета Устойчивость, то можно получить дополнительную информацию об оптимальном решении (рис. 1.18).
В результате решения задачи был получен ответ: необходимо сшить 70 шт. женских костюмов и 80 шт. мужских костюмов, чтобы получить максимальную прибыль 2300 у.е.
1.4. ДВОЙСТВЕННОСТЬ В ЗАДАЧАХ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. АНАЛИЗ ПОЛУЧЕННЫХ ОПТИМАЛЬНЫХ РЕШЕНИЙ
В 1975 г. наш соотечественник Л.В. Канторович был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов (см. Приложение 1).
С каждой задачей линейного программирования тесно связана другая линейная задача, называемая двойственной; первоначальная задача называется исходной, или прямой. Связь исходной и двойственной задач заключается, в частности, в том, что решение одной из них может быть получено непосредственно из решения другой.
Переменные двойственной задачи y i называются объективно обусловленными оценками, или двойственными оценками, или «ценами» ресурсов, или теневыми ценами.
Каждая из задач двойственной пары фактически является самостоятельной задачей линейного программирования и может быть решена независимо от другой.
Двойственная задача по отношению к исходной составляется согласно следующим правилам:
1) целевая функция исходной задачи формулируется на максимум, а целевая функция двойственной задачи - на минимум, при этом в задаче на максимум все неравенства в функциональных ограничениях имеют вид (), в задаче на минимум - вид ( );
2) матрица А, составленная из коэффициентов при неизвестных в системе ограничений исходной задачи, и аналогичная матрица А Т в двойственной задаче получаются друг из друга транспонированием;
3) число переменных в двойственной задаче равно числу функциональных ограничений исходной задачи, а число ограничений в системе двойственной задачи - числу переменных в исходной;
4) коэффициентами при неизвестных в целевой функции двойственной задачи являются свободные члены в системе ограничений исходной задачи, а правыми частями в ограничениях двойственной задачи - коэффициенты при неизвестных в целевой функции исходной; j 0.
Две приведенные задачи образуют пару симметричных двойственных задач. Основные утверждения о взаимно двойственных задачах содержатся в двух следующих теоремах.
Первая теорема двойственности. Для взаимно двойственных задач имеет место один из взаимоисключающих случаев.
1. В прямой и двойственной задачах имеются оптимальные решения,
при этом значения целевых функций на оптимальных решениях
совпадают
2. В прямой задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допустимое множество.
3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множество оказывается пустым.
4. Обе из рассматриваемых задач имеют пустые допустимые множества.
Вторая теорема двойственности (теорема о дополняющей нежесткости). Пусть = (x 1 ,х 2 ,..., х п) - допустимое решение прямой задачи, a = (у 1 ,у 2 ,…,у т) - допустимое решение двойственной задачи. Для того чтобы они были оптимальными решениями соответственно прямой и двойственной задач, необходимо и достаточно, чтобы выполнялись следующие соотношения:
Условия (1.4) и (1.5) позволяют, зная оптимальное решение одной из взаимно двойственных задач, найти оптимальное решение другой задачи.
Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.
Теорема об оценках. Значения переменных y i в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b i системы ограничений (неравенств) прямой задачи на величину
Решая ЗЛП симплекс-методом, мы одновременно решаем двойственную ЗЛП. Переменные двойственной задачи y i называют объективно обусловленными оценками.
Рассмотрим экономическую интерпретацию двойственной задачи на примере задачи о коврах.
Пример 1.2. Используя постановку задачи о коврах, выполнить следующие задания.
1. Сформулировать экономико-математическую модель задачи о коврах на максимум общей стоимости продукции, используя данные табл. 1.1.
2. Используя Поиск решения, найти такой план выпуска продукции, при котором общая стоимость продукции будет максимальной.
3. Сформулировать экономико-математическую модель двойственной задачи к задаче о коврах.
4. Найти оптимальный план двойственной задачи, используя теоремы двойственности, пояснить равенство нулю Х 1 и Х 4 .
5. Используя протоколы Поиска решения, выполнить анализ полученного оптимального решения исходной задачи.
6. Определить, как изменится общая стоимость и план выпуска продукции при увеличении запаса ресурса труб на 12 ед.
1. Сформулируем экономико-математическую модель задачи.
Обозначим через Х 1 , Х 2 , Х 3 , Х 4 число ковров каждого типа. Целевая функция имеет вид
F(X) = ЗХ 1 + 4Х 2 + ЗХ 3 + Х 4 max,
а ограничения по ресурсам
7Х 1 + 2Х 2 + 2Х 3 + 6Х 4 80,
5Х 1 + 8Х 2 + 4 Х 3 + ЗХ 4 480,
2Х 1 + 4 Х 2 + Х 3 + 8X 4 130,
Х 1 , X 2 , X 3 , Х 4 0.
2. Поиск оптимального плана выпуска.
Решение задачи выполним с помощью надстройки Excel Поиск решения. Технология решения задачи была подробно рассмотрена в задаче о костюмах. В нашей задаче оптимальные значения вектора Х=(Х 1 , X 2 , X 3 , Х 4) будут помещены в ячейках ВЗ:ЕЗ, оптимальное значение целевой функции - в ячейке F4 .
Введем исходные данные. Сначала опишем целевую функцию с помощью функции - СУММПРОИЗВ (рис. 1.19). А потом введем данные для левых частей ограничений. В Поиске решения введем направление целевой функции, адреса искомых переменных, добавим ограничения. На экране появится диалоговое окно Поиск решения с введенными условиями (рис. 1.20).
После ввода параметров для решения ЗЛП следует нажать кнопку Выполнить. На экране появится сообщение, что решение найдено (рис. 1.21).
Полученное решение означает, что максимальный доход 150 тыс. руб. фабрика может получить при выпуске 30 ковров второго вида и 10 ковров третьего вида. При этом ресурсы «труд» и «оборудование» будут использованы полностью, а из 480 кг пряжи (ресурс «сырье») будет использовано 280 кг.
Создание отчета по результатам поиска решения. Excel позволяет представить результаты поиска решения в форме отчета (табл. 1.4). Существует три типа таких отчетов:
· Результаты (Answer). В отчет включаются исходные и конечные значения целевой и изменяемых ячеек, дополнительные сведения об ограничениях.
· Устойчивость (Sensitivity). Отчет, содержащий сведения о чувствительности решения к малым изменениям в изменяемых ячейках или в формулах ограничений.
· Пределы (Limits). Помимо исходных и конечных значений изменяемых и целевой ячеек, в отчет включаются верхние и нижние границы значений, которые могут принимать влияющие ячейки при соблюдении ограничений.