5.4. Геометрический метод решения задачи. Общий случай.

Общая задача линейного программирования в случае двух переменных имеет вид

. (4)

f max (5)

Решение задачи линейного программирования геометрическим методом в общем случае проводится точно так же, как и в предыдущем примере. Сначала строится множество М допустимых решений, а затем находится линия уровня

С наибольшим С, пересекающим множество М в точке (х⁰, у⁰). Эта точка (х⁰, у⁰) и будет решением задачи. Заметим, что если ищется наименьшее значение целевой функции f min, то определяется линия уровня f c с наименьшим значением D ( на рисунке она изображена пунктиром).

у
f=C0
	В
	М
f=D
1
Рис.3	1									х

Возможны следующие случаи.

1. Система ограничений (4) несовместна. Если система (4) не имеет ни одного решения, то и задача линейного программирования не имеет решений.

2. Неединственность решения. Такой случай возникает, если линия уровня проходит не через одну, а через две угловые точки множества М. В этом случае решением задачи линейного программирования будут все точки отрезка АВ.

f(х,у)=С

А

В

М

Рис.4

3. Неограниченность области М. В этом случае решение задачи линейного программирования может существовать, а может не существовать.

f(х,у)=С

М

Рис.5

На рис. 5 с ростом С линии уровня все время пересекают множество М, а поэтому наибольшего значения f не существует, а значит и задача линейного программирования не имеет решения.

f(х,у)=С

М

Рис.6

В

На рис. 6 линия уровня с наибольшим С⁰ проходит через точку В(х⁰, у⁰), при С>С⁰ линии уровня не пересекают М, поэтому В(х⁰, у⁰) является решением задачи линейного программирования.

Очевидным недостатком геометрического метода решения задачи линейного программирования является то, что в задаче могут присутствовать только две переменные. Поэтому дальше мы рассмотрим другой метод, позволяющий решать задачи любой размерности.