Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Решение. Найти допустимую область задачи линейного программирования, определяемую ограничениями (5)




Пример

Найти допустимую область задачи линейного программирования, определяемую ограничениями

(5)

 

1. Рассмотрим прямую 12 = 1. При х1=0 х2 = 1, а при х2 = 0 х1=-1. Таким образом, эта прямая проходит через точки (0,1) и (-1,0). Беря х1= х2 =0 получим, что -0+0<1 и поэтому интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4а.

2. Рассмотрим прямую х1-2х2 = 1. При х1=0 х2 = -1/2, а при х2 = 0 х1=1. Таким образом, эта прямая проходит через точки (0, -1/2) и (1,0). так как 0-2·0 < 1 (4.б).

3. Наконец, рассмотрим прямую х1+ х2 =3. Она проходит через точки (0,3) и (3,0) и так как 0+0<3, то интересующая нас полуплоскость лежит ниже прямой, изображенной на рис. 4.в).

Сводя все вместе и добавляя условия х1 ≥0, х2 ≥0 получим рисунок 5, где выделена область, в которой выполняются одновременно все ограничения (5). Обратите внимание на то, что получившаяся область имеет вид выпуклого многоугольника.

Вернемся теперь к общему случаю, когда одновременно выполняются неравенства:

(6)

Имеют место некоторые случаи, которые тут могут получится.

1. Основной случай - получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 6).

2. Неосновной случай -получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 7. Подобная ситуация, например, получится, если в рассмотренном выше примере убрать ограничение х1+ х2≤ 3. Оставшаяся часть будет неограниченным выпуклым многоугольником.

3. Наконец, возможен случай, когда неравенства (6) противоречат друг другу, и допустимая область вообще пуста.

Вернёмся теперь к исходной задаче линейного программирования. В ней, кроме системы неравенств, есть еще целевая функция
с1 х12 х2 max.

Рассмотрим прямую с1 х12 х2=L. При увеличении L прямая будет двигаться параллельно самой себе в том направлении, которое дается вектором (с1 2), так как это - вектор нормали к нашей прямой и одновременно вектор градиента функции f (х1, х2)=с1 х12 х2.

А теперь сведем всё вместе. Итак, надо решить задачу:

х1 ≥0, х2 ≥0

Ограничения задачи вырезают на плоскости некоторый многоугольник. Пусть при некотором L прямая с1 х12 х2=L пересекает допустимую область. Это пересечение дает какие-то значения переменных (x1 ,x2), которые являются планами.

Увеличивая L, мы начнем двигать нашу прямую и её пересечение с допустимой областью будет изменяться (рис. 9). В конце концов эта прямая выйдет награницу допустимой области - как правило, это будет одна из вершин многоугольника. Дальнейшее увеличение L приведёт к тому, что пересечение прямой с1 х12 х2=L с допустимой областью будет пустым.

Поэтому то положение прямой с1 х12 х2=L, при котором она вышла на граничную точку допустимой области, и даст решение задачи, а соответствующее значение L и будет оптимальным значением целевой функции.




Поделиться с друзьями:


Дата добавления: 2014-01-20; Просмотров: 1067; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.012 сек.