Линейное геометрическое программирование
14.1 Цель работы
Познакомиться с методами линейного программирования и получить навыки решения простейших задач путем их геометрической интерпретации с использованием вычислительной системы Mathcad.
14.2 Задание
Найти минимум целевой функции при заданных ограничениях.
| № | Целевая функция | 1 ограничение | 2 ограничение | 3 ограничение |
| 2х+3у | х+у5 | х+2у4 | 2х+у5 | |
| 6х+3у | 2х+у2 | 3х4у12 | х=2 | |
| х+2у | х+у6 | ху3 | х+у4 | |
| 2х+4у | х+у5 | х+2у4 | 2х+у5 | |
| 7х+3у | 2х+у2 | 3х4у12 | у=3 | |
| 3х+3у | х+у5 | х+2у4 | 2х+у5 | |
| 4х+3у | х+у6 | х+2у4 | 2х+у5 | |
| 5х+у | х+у7 | х+2у4 | у=10 | |
| 6х+2у | х+у8 | х+2у4 | х=5 | |
| 5х+3у | х+у7 | х+2у4 | 2х+у5 |
Для всех заданий х>0, у>0.
14.3 Теоретические сведения
Линейное программирование – математический способ решения задач оптимизации, для которых целевая функция и заданные ограничения являются линейными.
Основной задачей линейного программирования является нахождение чисел x1,x2,….,xn для которых целевая функция :
(14.1)
достигает наибольшего (наименьшего) значения при ограничениях
(14.2)
где сj,aij,bi - заданные числа.
Найденные числа x1,x2,….,xn , являющиеся решением задачи, называются оптимальным планом.
Особенностью основной задачи является то, что функциональные ограничения задаются в форме равенств. Если ограничения задаются в форме равенств и неравенств , и на некоторые ( или на все ) переменные не накладываются условие неотрицательности , то будем говорить о том , что задача представлена в общей форме. Любая задача линейного программирования может быть приведена к основной задаче.
Преобразовать неравенство в равенство можно, введя дополнительную переменную , а от условия отрицательности переменных можно заменой переменных перейти к условию неотрицательности. Область допустимых решений задачи линейного программирования представляет собой многогранник в пространстве n-переменных. В теории линейного программирования доказано, что оптимальное решение соответствует одной из вершин этого многогранника.
Решение задачи сводится к определению одной из вершин , в которой значение целевой функции меньше(больше), до тех пор, пока не будет достигнуто оптимальное значение целевой функции. Данной работе ограничимся двумя переменными, что допускает геометрическую интерпретацию решения задачи на плоскости.
Методы решения задач с большим числом переменных в данной работе не рассматриваются.
14.4 Пример выполнения задания
Рассмотрим производственную задачу. Пусть некоторая фирма изготавливает два вида красок. Цена одной тонны краски №1 равна 2 тыс. руб., а краски №2 3 тыс. руб. Нужно определить оптимальный суточный объем производства в тоннах для обеих красок. В качестве целевой функции выберем суммарный суточный доход фирмы :
Этот доход необходимо максимизировать.
Есть ограничения :
1) суточный спрос на краску №1 никогда не превышает спрос на краску №2 более, чем на 1 тонну х1-х21,
2) суточный спрос на краску №2 никогда не превышает 2 тонны.
Для производства красок используются два вида исходных продуктов: А и В. Расход исходных продуктов для производства обоих видов красок и их возможные суточные запасы представлены в таблице 14.1.
Таблица 14.1
| Исходный продукт | Расход исходного продукта на 1 тонну краски | Максимальный суточный запас, т | |
| Краска №1 | Краска №2 | ||
| А | |||
| В |
Согласно таблице 14.1 можно записать ограничения на расход материалов:
для исходного продукта А : 2х1+х26,
для исходного продукта В : х1+2х28.
К записанным ограничениям нужно добавить естественное условие неотрицительности : х10, х20 .
Математическую формулировку задачи оптимизации запишем в виде:
Z=2x1+3x2 max (14.3)
x1x21 (14.4)
2x1+x26 (14.5)
x1 2 (14.6)
x1+2x28 (14.7)
x10, x20 (14.8)
Будем решать задачу в общем виде без преобразования неравенств в равенства. В связи с тем , что в задаче только две независимых переменных , она может решаться графическим методом.
Построим при помощи Mathcad многогранник ABCDEF (рис.14.1) , внутри которого находится область допустимых решений.
Оптимальное решение находится в одной из вершин этого многогранника. Нанесем на график линии уровня 1 и 2 , соответствующие различным значениям целевой функции. Увеличение значения целевой функции при движении в направлении перпендикуляра от линии 1 до линии 2.
Рис.14.1
Геометрическое решение задачи (14.3) : 1 линии уровня z=6, 2 линии уровня z=9, 3 ограничение (14.7) по ресурсу В, 4 ограничение (14.4), 5 ограничение (14.5) по ресурсу А , 6 ограничение (14.6).
Таким образом, максимальное значение целевой функции будет соответствовать точка С.
Найдем с помощью Mathcad координаты точки С:
|
|
|
|
|
|
|
Таким образом ,точка С имеет координаты х1=1,333 и х2=3,333 .
Определим целевую функцию Z(x1,x2):=2x1+3x2
Найдем оптимальное значение целевой функции
Z(1.33,3.33)=12.67 т.руб./сутки
Проанализируем влияние начальных условий на оптимальное решение.
Первая задача определить влияние изменения запасов.
Здесь можно рассмотреть два случая. На сколько можно увеличить запас дефицитного ресурса, улучшая оптимальное значение целевой функции, и на сколько можно снизить запас недефицитного ресурса при сохранении оптимального значения целевой функции.
В нашей задаче дефицитными ресурсами являются ограничения (14.5) и (14.7), определяющие оптимальную точку С.
Увеличением ресурса А с 6 до 7 т/сутки можно сдвинуть прямую DC так, чтобы оптимальной стала (·) К. Определим ее координаты :
|
|
|
|
|
|
|
|
|
|
Точка К имеет координаты х1=2 , х2=3.
Найдем новое оптимальное значение целевой функции в (·) К
Z(2,3)=13 т.руб./сутки
Полученное оптимальное значение лучше предыдущего.
Увеличением ресурса (14.7) , связанного с суточным запасом продукта В, с 8 до 12 т/сутки сдвигает прямую DC так, чтобы оптимальной стала (·) L. Ее координаты : х1=0, х2=6.
Z(0,6)=18 т.руб./сутки
Увеличением суточного запаса продукта В можно добиться существенного увеличения оптимального значения целевой функции.
Недефицитный ресурс (14.6) фиксирует максимальный уровень спроса на краску №1 . Без изменения оптимального значения целевой функции он может быть уменьшен до 1,33 т/сутки .
Другой недефицитный ресурс (14.4) при сдвиге прямой 4 вправо до точки С примет вид х2х12 , т.е.спрос на краску №2 может превышать спрос на краску №1 не более ,чем на 2 т/сутки.
Результаты анализа представлены в таблице
Таблица 14.2
| Ресурс | Тип | Максимальное изменение ресурса, т/сутки | Максимальное изменение дохода т.руб./сутки |
| (14.5) | дефицитный | 0,33 | |
| (14.7) | дефицитный | 5,33 | |
| (14.6) | недефицитный | 0,66 | |
| (14.4) | недефицитный |
Вторая задача анализа – определение чувствительности или изменения дохода на единицу изменения ресурса. В таблице 14.3 представлены результаты определения чувствительности по каждому из ресурсов.
Таблица 14.3
| Ресурс | Тип | Чувствительность, т.руб./т |
| (14.5) | дефицитный | 0,33 |
| (14.7) | дефицитный | 1,33 |
| (14.6) | недефицитный | |
| (14.4) | недефицитный |
Из таблицы видно 14.3 очевидно , что в первую очередь следует увеличивать ресурс (14.7) , т.е. запасы исходного продукта В.
Третья задача анализа – определение пределов изменения коэффициентов целевой функции . Эта задача разделяется на две части.
Первая – определить диапазон изменения коэффициентов, при котором не происходит изменения оптимального значения целевой функции . В данном случае можно допустить поворот целевой функции вокруг точки С в пределах, определяемых тангенсами углов наклона ресурсов (14.5) и (14.7), т.е. от -5 до -2. При этом коэффициент при х2, равный 3 в исходной целевой функции , может изменяться от 2 до 4.
Вторая часть задачи – определить, на сколько следует изменить коэффициенты целевой функции, чтобы дефицитный ресурс сделать недефицитный или наоборот.
В данном случае при коэффициенте целевой функции при х2 в пределах от -2 до -4 ресурс (14.5) становится недефицитным, т.к. не проходит через оптимальную точку В.
14.5 Порядок выполнения работы
1.Получить у преподавателя вариант задания.
2.Построить график с областью допустимых значений переменных.
3.Построить на графике линии уровня целевой функции и определить оптимальное решение, рассчитать координаты оптимальной точки.
4.Вычислить значение функции в оптимальной точке.
5.Если задача имеет бесконечное множество решений, экстремум достигается на отрезке, вычислить оптимальное значение целевой функции
и описать множество решений.
6.Проанализировать влияние изменения ограничений на оптимальное значение целевой функции.
7.Проанализировать чувствительность целевой функции по каждому из ограничений.
8.Проанализировать пределы изменения коэффициентов целевой функции, при которых на происходит изменения оптимального решения.
9.Выбрать один из дефицитных ресурсов, и определить при каких коэффициентов целевой функции он становится недефицитным .
10.Выводы.
14.6 Контрольные вопросы
1.Сформулируйте основную задачу линейного программирования.
2.Каким образом заменить ограничения в форме неравенств ограничениями-равенствами ?
3.В чем суть геометрического метода определения области допустимых решений задачи линейного программирования ?
4.В каких точках находится оптимальное решение ?
5.В чем различие недефицитных и дефицитных ресурсов ?
6.Как сделать дефицитный ресурс недефицитным ?
7.Как определить наиболее ценный из дефицитных ресурсов ?
8.Как можно изменить значения коэффициентов целевой функции без изменения ее оптимального значения ?
9.В каком случае может быть получено бесконечное множество оптимальных решений ?
10. Когда задача линейного программирования не будет иметь решений ?
14.7 Литература
1.А.И. Плис, Н.А.Славина, Mathcad 2000,Математический практикум для экономистов и инженеров.- М.: Финансы и статистика,2000 г.
2.Mathcad. Руководство пользователя Mathcad Plus 6.0. Финансовые, инженерные и научные расчеты в среде Windows-95. – М.,Филинъ,1997 г.