КАТЕГОРИИ:
Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)
II. Решение задачи линейного программирования геометрическим методом
|
|
|
|
Общей задачей линейного программирования называется задача нахождения минимума (максимума) линейной функции
Z = c1 x1 + c2 x2 +...+ cn xn ® min (max) (1)
при ограничениях:
a11 x1 + a12 x2 +...+ a1n xn £ (=, ³) b1
a21 x1 + a22 x2 +...+ a2n xn £ (=, ³) b2 (2)
..................................
am1 x1 + am2 x2 +...+ amn xn £ (=, ³) bm,
xj ³ 0, j = 1,..., n (3)
где cj, aij, bi - заданные числа, xj - неизвестные, i = 1,…,m, j = 1,…,n и в любом из ограничений вида (2) может встречаться любой из знаков £, = или ³.
Если число неизвестных n = 2, то задача (1) – (3) примет вид
Z = c1 x + c2 y ® min (max) (4)
a11 x + a12 y £ (=, ³) b1
a21 x + a22 y £ (=, ³) b2 (5)
......................
am1 x + am2 y £ (=, ³) bm,
x ³ 0, y ³ 0. (6)
и ее можно решить геометрическим методом, так как каждая пара неизвестных (х, y) может быть представлена точкой на координатной плоскости хОy.
При решении задачи (4) – (6) сначала строят так называемую допустимую область, т.е. множество точек (х, y) плоскости, координаты которых удовлетворяют всем ограничениям (5) и лежат в первой четверти координатной плоскости (ограничение (6)). Поскольку все ограничения (5) – линейные, то допустимая область будет представлять собой выпуклый многоугольник (конечный или бесконечный) или пустое множество.
Затем среди точек допустимой области находят оптимальную, т.е. такую точку М0 координаты которой (х0 , y0) доставляют минимум (максимум) целевой функции Z. Для этого по виду целевой функции (4) строят линию уровня функции Z, соответствующую Z=0, т.е. прямую L0: c1 x + c2 y = 0 и находят градиент функции Z – вектор 
, который показывает направление наибыстрейшего возрастания функции Z. Вектор антиградиента (-с1, -с2) будет показывать направление наибыстрейшего убывания целевой функции Z. Вектор градиента перпендикулярен линии уровня L0.
Перемещая линию уровня L0 параллельно самой себе в направлении градиента (с1, с2), находим последнюю точку допустимой области, которую она пересекает при таком движении. Очевидно, что это будет точка максимума. Перемещая линию уровня в противоположном направлении (-с1, -с2), находим точку минимума. Поясним этот метод на конкретном примере.
Геометрическим методом найти максимум и минимум функции Z для
x, y ³ 0 при заданных ограничениях.
Z = x – 3y
-x + y £ 4
5x + 4y £ 34
x + 8y ³ 14
Решение. Построим допустимую область. Для этого в системе координат х0y строим прямую - x + y= 4 - границу первого ограничения. Затем определяем, в какой полуплоскости находятся точки (х, y), для которых -x + y < 4. Для этого выбираем любую точку, например (0, 0), и проверяем, удовлетворяет ли она этому неравенству. Поскольку -0 + 0 = 0 < 4, то точки, для которых - x+y£ 4 лежат в той же полуплоскости, что и точка О(0, 0), т.е. справа (ниже) от границы -x + y = 4.
y
8,5 -x + y = 4
L2
C
L0
4 B L1
E
1,75 A D
0 1 6,8 14 y
x + 8y =14
-3 
5x + 4y = 34
Аналогично строятся остальные полуплоскости, соответствующие ограничениям 5 х + 4 у £ 34 и х + 8 у ³ 14 (ниже прямой 5 х + 4 у = 34 и выше прямой х + 8 у = 14). Множество точек, удовлетворяющих всем трем неравенствам, образуют треугольник ECD. Учитывая ограничение х ³ 0 и у ³ 0, получаем допустимую область – четырехугольник ABCD.
Проведем линию уровня L 0, соответствующую значению Z =0, т.е. прямую х – 3 у = 0 (для точек, лежащих на этой прямой, значение Z =0). Она будет проходить через точку О(0, 0) перпендикулярно вектору 
. Перемещая линию уровня в направлении градиента , т.е. в направлении возрастания Z, находим последнюю точку допустимой области, которую линия уровня пересекает при этом движении (линия L1). Это будет точка максимума. В нашем случае – это точка D (6, 1), координаты которой можно найти, решив систему линейных уравнений 5 х + 4 у = 34 и х + 8 у = 14. Аналогично, двигая линию уровня в противоположном направлении до линии L2, находим точку минимума – точку С (2, 6). Таким образом, Zmax= Z (6,1)= 6 - 3×1=3, Zmin=Z (2,6)=2-3×6=-16.
Задача решена полностью.
КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задание 2. Геометрическим методом найти максимум и минимум функции Z для x, y ³ 0 при заданных ограничениях:
Варианты:
1. Z = 2x + y 2. Z = 3x + y
3x - 4y £ 4 y £ 1
-x + 6y £ 8 x - 2y £ 3
x + y ³ 1 2x + y ³ 1
3. Z = 2x - y 4. Z = x + y
2x + y £ 3 y ³ 2
x + y ³ 6 x + y £ 7
x - 3y £ 3 -x + 2y £ 2
5. Z = 4x + y 6. Z = 3x - y
x - 2y ³ 0 2x + 3y £ 13
4x - y £ 14 x ³ 2
3x + y ³ 7 5x - 3y £ 22
7. Z = 2x + y 8. Z = x + 5y
x ³ 2 3x - y ³ 3
4x - y £ 8 x - y £ 4
x - y ³ -1 x + y ³ 6
9. Z = 5x + y 10. Z = 3x
x - 4y ³ -3 x + y £ 7
4x - 3y £ 14 2x - y £ 11
3x + y ³ 4 4x + y ³ 19
|
|
|
|
|
Дата добавления: 2017-02-01; Просмотров: 68; Нарушение авторских прав?; Мы поможем в написании вашей работы!