2. Лекции Практические и лабораторные занятия
Лекция 4. Графический метод решения задач линейного программирования
жүктеу/скачать 0,77 Mb.
|
Лекция 4. Графический метод решения задач линейного программированияСодержание лекционного занятия: ЗЛП имеет единственное решение ЗЛП имеет альтернативный оптимум ЗЛП имеет минимум и не имеет максимума ЗЛП не имеет решения Графический метод решения задачи линейного программирования имеет весьма ограниченную область применения. Как правило этим методом решаются задачи, содержащие не более двух переменных. Пример Найти решение X*=(x*1,x*2), которое удовлетворяет системе неравенств: (1) условиям неотрицательности переменных: x10, x20, (2) и которое доставляет оптимальное значение целевой функции: f = c1 x1+с2х2 —»max(min). (3) Необходимо отметить, что, несмотря на ограниченность применения, данный метод очень полезен для иллюстрации общих идей методов, используемых для решения задач линейного программирования. Применение геометрического метода предполагает использование нескольких этапов. На первом из них в системе координат Х1 ОХ2 строится область допустимых решений задачи (ОДЗ). Для этого каждое из неравенств системы (1) заменяем равенством и строим соответствующие этим равенствам граничные прямые: a i1x1+ai2 x2=bi (i=l.. .m). Каждая из этих прямых делит плоскость XiOX2 на две полуплоскости (рис. 1). Для точки (.) А, принадлежащей одной из этих полуплоскостей, выполняется неравенство:a i1x1+ai2 x2bi (i=l.. .m). Для любой (.)В, принадлежащей другой полуплоскости, — противоположное неравенство: a i1x1+ai2 x2bi (i=l.. .m). А для любой из точек, лежащих на граничной прямой, выполняется уравнение: a i1x1+ai2 x2=bi (i=l.. .m). решения, удовлетворяющие рассматриваемому неравенству, достаточно испытать одну какую-либо точку, например точку с координатами (0,0). Если при подстановке ее координат в левую часть неравенства оно удовлетворяется, значит, искомая полуплоскость содержит данную точку и штриховка, выделяющая искомую полуплоскость, обращена в сторону к испытуемой точке. Если же неравенство не удовлетворяется, штриховка, выделяющая искомую полуплоскость, обращена в противоположную от данной точки сторону. жүктеу/скачать 0,77 Mb. Достарыңызбен бөлісу:
|