2015-05-13
633
Задание
Решить ниже представленную ЗЛП (1.11) графическим методом. В качестве средства построения графиков используйте MS Excel.
(1.11)
Для построения графического решения выразим переменную x2 через x1 во всех неравенствах, получим:
(1.12)
В декартовой системе координат X1X2 строим графики функций, полученных в результате преобразований ограничений (рис.1.13). Ограничения неотрицательности переменных определяются осями координат.
Согласно требованиям неотрицательности переменных следует рассматривать только первую четверть системы координат. Для прочих ограничений определяем, какая из полуплоскостей для каждого из полученных графиков, удовлетворяет соответствующему ограничению. Для этого подставляем произвольные точки, принадлежащие той или иной полуплоскости графика, в соответствующее ему ограничение. Если неравенство верно, то данная полуплоскость, которой принадлежит выбранная точка, является областью допустимых решений (ОДР) данного неравенства. В результате определения ОДР каждого неравенства получаем ОДР системы неравенств, которая представляет собой выпуклый многоугольник (рис.1.14).
|
|
|
Строим линии уровня для целевой функции – то есть кривые безразличия для функции от двух переменных на плоскости её аргументов. Для этого последовательно приравниваем целевую функцию 1 (значению свободного члена) и 0 (небольшому изменению функции), полученные уравнения строим в нашей системе координат X1X2, и определяем визуально направление роста функции (рис.1.15).
Параллельным переносом передвигаем полученные линии уровня в направлении роста целевой функции, вплоть до пересечения с последней вершиной многогранника ОДР. Вычисляем приблизительное значение координат x1 и x2 в этой точке, подставляем эти значения в нашу систему ограничений, проверяем, справедливы ли неравенства для нашего приблизительного решения. Если нет, то корректируем это решение так, чтобы неравенства выполнялись.
В нашем случае координаты полученного оптимального решения, x1 и x2, будут равны соответственно 0,25 и 3,75. При этом выполняются все ограничения, а Z=8,75.
Далее строим для Z=8,75 кривую безразличия в плоскости X1X2, она, естественно проходит через одну из вершин многогранника, таким образом, получено оптимальное решение задачи линейного программирования графическим методом (рис.1.16).
Рис.1.13. Построение графиков функций, полученных в результате преобразований ограничений
Рис.1.14. Определение ОДР системы неравенств
Рис.1.15. Построение линий уровня для заданной целевой функции
Рис.1.16.Оптимальное решение задачи линейного программирования, полученное графическим методом
|
|
|
5.Варианты для выполнения лабораторной работы №1 [1]
Задание
Решите ЗМП графическим методом, используя MS Excel для построения графиков по ниже представленным данным для соответствующего варианта.
Таблица 1.1
| Вариант | Ограничения | Целевая функция | |||
Таблица 1.2
| Целевая функция вида a1x1+a2x2+b→Цель | a1 | a2 | b | Цель |
| max | ||||
| max | ||||
| max | ||||
| max | ||||
| max | ||||
| -2 | max | |||
| -1 | max | |||
| -3 | max | |||
| -5 | max | |||
| -2 | max | |||
| -3 | -1 | min | ||
| -2 | -4 | min | ||
| -5 | -3 | min | ||
| -5 | -2 | min | ||
| -7 | -3 | min | ||
| -4 | min | |||
| -3 | min | |||
| -5 | min | |||
| -4 | min | |||
| -5 | min |
Таблица 1.3
| Ограничения вида a1x1+a2x2 знак b | a1 | a2 | знак | b |
| ³ | ||||
| ³ | ||||
| -0,5 | £ | |||
| £ | ||||
| ³ | ||||
| -5 | ³ | |||
| -6 | £ | |||
| £ | ||||
| -3 | ³ | -1 | ||
| -4 | ³ | -1 | ||
| -5 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| -2 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| -7 | £ | |||
| 0,7 | ³ | |||
| £ | ||||
| -1 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| -2 | -7 | £ | ||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ | ||||
| 0,1 | ³ | |||
| ³ | ||||
| -2 | £ | |||
| £ | ||||
| £ | ||||
| £ | ||||
| -0,5 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| -1 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ | ||||
| ³ | ||||
| ³ | ||||
| -2 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| -3 | £ | |||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ | ||||
| ³ | ||||
| ³ | ||||
| £ | ||||
| -9 | £ | |||
| ³ | ||||
| ³ | ||||
| £ | ||||
| £ |
На переменные x1 и x2 дополнительно накладываются ограничения неотрицательности.
6.Рекомендуемая литература
1. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. Учеб. пособие для студ. Втузов. – 2-е изд., стер. – М.: Высшая школа, 2001. – С. 60-70.
2. Гарнаев А.Ю. Использование MS Excel и VBA в экономике и финансах. – СПб.:БХВ – Санкт-Петербург, 2000. – С. 38-64.
|
|
|
3. Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике: Учебник. - М.: МГУ им. М.В.Ломоносова. Дело и Сервис, 1999. – С. 120-134.
4. Резниченко С.С., Ашихмин А.А. Математические методы и моделирование в горной промышленности. – М.: МГГУ, 1997. – С.20-61.
