Студопедия

КАТЕГОРИИ:


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

Графический метод решения


Задача с двумя переменными

Графический метод решения задач линейного программирования

 

Пусть требуется найти максимальное значение функции

F(X) = с1 х1 + с2 х2 (2.1)

при ограничениях

(2.2)

Допустим, что система ограничений (2.2) совместна, т.е. имеет решение, а многоугольник ее решений (ОДР) ограничен. Каждое из неравенств (2.2) определяет полуплоскость с границей , i = 1, 2, ..., т или х1 = 0, х2 = 0. Представим этот многоугольник на плоскости Ох1х2 (рис. 2.1).

Рис.2.1

Линейная функция (2.1) при фиксированных значениях F(X) является уравнением прямой линии c1x1+ c2x2=const.

Изобразим прямую, соответствующую линейной функции, при F(X) = 0. Эта прямая пройдет через начало координат. Другим значениям F(X) будут соответствовать прямые, параллельные друг другу.

Прямая, уравнение которой получено из целевой функции задачи при равенстве ее постоянной величине, называется линией уровня.

Известно, что коэффициенты при переменных в линейном уравнении являются координатами нормального вектора к соответствующей прямой или плоскости. Следовательно, нормальный вектор линий уровня и имеет координаты с1 и с2, т.е. = (с1, с2).

Если перемещать линию уровня параллельно ее начальному положению в направлении вектора , то для данного случая (см. рис. 2.1) последней точкой, в которой линия уровня коснется ОДР, окажется точка С. Линия уровня, имеющая общие точки с ОДР и расположенная так, что ОДР целиком находится в одной из полуплоскостей, называется опорной прямой.

Алгоритм решения ЗЛП с двумя переменными графическим методом таков:

1. Строится область допустимых решений.

2. Строится вектор = (с1, с2) с точкой приложения в начале координат.

3. Перпендикулярно вектору проводится одна из линий уровня, например линия уровня, соответствующая уравнению с1х1 + с2х2 = 0.

4. Линия уровня перемещается до положения опорной прямой. На этой прямой и будет находиться максимум или минимум функции.

В зависимости от вида ОДР и целевой функции F(X) задача может иметь единственное решение (рис. 2.3, а), бесконечное множество решений (рис. 2.3, б) или не иметь ни одного оптимального решения (рис. 2.3, в).



 

 


a) б) в)

Рис. 2.3

Пример 1.Решить задачу линейного программирования графическим методом: F(X)=2x1+4x2→ max,

 

 
 

Решение. Изобразим на плоскости систему координат Ох1х2 и построим

Рис. 2.4
граничные прямые области допустимых решений (номера прямых соответствуют их порядковому номеру в системе). Область допустимых решений определяется многоугольником OABCD (рис. 2.4). Для линий уровня 2х1 + 4х2 = с (с = const) строим нормальный вектор = (2,4).
Перпендикулярно вектору построим одну из линий уровня (на рис. 2.4 она проходит через начало координат). Так как задача на максимум, то перемещаем линию уровня в направлении вектора до опорной прямой. В данном случае опорной прямой является прямая, проходящая через точку пересечения граничных прямых L1 и L2, т.е. через точку В = L1L2. Для определения координат точки В решаем систему уравнений

Получаем х1 = 3, х2 = 6. Это и будет оптимальное решение данной задачи, которому соответствует максимальное значение целевой функции

max F(X) = 2 · 3 + 4 · 6 = 30.

Пример 2.Найти минимум функции F(X)=2x1+x2→ min при ограничениях

Отличие этого примера от предыдущего состоит в том, что здесь ищется не максимум, а минимум функции F. Областью решений данной системы ограничений является треугольник АВС (рис.2.5). На рисунке изображены также исходная линия уровня и вектор q = (2; 1), показывающий направление движения этой линии для достижения максимума функции F. Так как требуется найти минимум этой функции, то будем передвигать исходную линию уровня в сторону, противоположную вектору q. Как видно из рис. 2.5, минимум функции F достигается в угловой точке А, координаты которой служат решением системы уравнений

Рис. 2.5
 
 

Отсюда А (6/7; 25/7) и Fmin = 37/7.

<== предыдущая лекция | следующая лекция ==>
Задачи для самостоятельного решения | Задач линейного программирования

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


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



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

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