2. Лекции Практические и лабораторные занятия


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



бет12/46
Дата06.01.2022
өлшемі0,77 Mb.
#11583
1   ...   8   9   10   11   12   13   14   15   ...   46
Байланысты:
УМКД метод матер МО и Исл опер

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


Содержание лекционного занятия:

  • ЗЛП имеет единственное решение

  • ЗЛП имеет альтернативный оптимум

  • ЗЛП имеет минимум и не имеет макси­мума

  • ЗЛП не имеет решения


Графический метод решения задачи линейного про­граммирования имеет весьма ограниченную область при­менения. Как правило этим методом решаются задачи, со­держащие не более двух переменных.

Пример

Найти решение X*=(x*1,x*2), которое удовлетворяет системе неравенств:




(1)


условиям неотрицательности переменных:
x10, x20, (2)

и которое доставляет оптимальное значение целевой функции:

f = c1 x12х2 —»max(min). (3)

Необходимо отметить, что, несмотря на ограниченность применения, данный метод очень полезен для иллюстрации общих идей методов, используемых для решения задач ли­нейного программирования.

Применение геометрического метода предполагает ис­пользование нескольких этапов.

На первом из них в системе координат Х1 ОХ2 строится область допустимых решений задачи (ОДЗ). Для этого каждое из неравенств системы (1) заменяем равенст­вом и строим соответствующие этим равенствам гранич­ные прямые:

a i1x1+ai2 x2=bi (i=l.. .m).

Каждая из этих прямых делит плоскость XiOX2 на две полуплоскости (рис. 1). Для точки (.) А, принадлежащей одной из этих полуплоскостей, выполняется неравенство:a i1x1+ai2 x2bi (i=l.. .m).

Для любой (.)В, принадлежащей другой полуплоскости, — противоположное неравенство: a i1x1+ai2 x2bi (i=l.. .m).

А для любой из точек, лежащих на граничной прямой, выполняется уравнение: a i1x1+ai2 x2=bi (i=l.. .m).

решения, удовлетворяющие рассматриваемому нера­венству, достаточно испытать одну какую-либо точку, на­пример точку с координатами (0,0). Если при подстановке ее координат в левую часть неравенства оно удовлетворя­ется, значит, искомая полуплоскость содержит данную точ­ку и штриховка, выделяющая искомую полуплоскость, об­ращена в сторону к испытуемой точке.

Если же неравенство не удовлетворяется, штриховка, выделяющая искомую полуплоскость, обращена в проти­воположную от данной точки сторону.






Достарыңызбен бөлісу:
1   ...   8   9   10   11   12   13   14   15   ...   46




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет