Методы решения систем линейных неравенств

| Категория реферата: Рефераты по математике
| Теги реферата: рынок реферат, отчет по производственной практике
| Добавил(а) на сайт: Nazarov.

В связи с ограниченными возможностями наглядного графического представления данный метод применяется только для систем линейных неравенств с двумя неизвестными и систем, которые могут быть приведены к данному виду.

Для того чтобы наглядно продемонстрировать графический метод, решим следующую задачу:

[pic]

[pic]

1. На первом этапе надо построить область допустимых решений. Для данного примера удобнее всего выбрать X2 за абсциссу, а X1 за ординату и записать неравенства в следующем виде:

[pic]

Так как [pic] и [pic] графики и область допустимых решении находятся в первой четверти.

Для того чтобы найти граничные точки решаем уравнения (1)=(2), (1)=(3) и
(2)=(3).

[pic]

Как видно из иллюстрации многогранник ABCDE образует область допустимых решений.
Если область допустимых решений не является замкнутой, то либо max(f)=+ ?, либо min(f)= -?.

2. Теперь можно перейти к непосредственному нахождению максимума функции f.

Поочерёдно подставляя координаты вершин многогранника в функцию f и сравнивать значения, находим что

f(C)=f(4;1)=19 – максимум функции.

Такой подход вполне выгоден при малом количестве вершин. Но данная процедура может затянуться если вершин довольно много.

В таком случае удобнее рассмотреть линию уровня вида f=a. При монотонном увеличении числа a от -? до +? прямые f=a смещаются по вектору нормали[1].
Если при таком перемещении линии уровня существует некоторая точка X – первая общая точка области допустимых решений (многогранник ABCDE) и линии уровня, то f(X)- минимум f на множестве ABCDE. Если X- последняя точка пересечения линии уровня и множества ABCDE то f(X)- максимум на множестве допустимых решений. Если при а>-? прямая f=a пересекает множество допустимых решений, то min(f)= -?. Если это происходит при а>+?, то max(f)=+ ?.
[pic]
В нашем примере прямая f=a пересевает область ABCDE в точке С(4;1).
Поскольку это последняя точка пересечения, max(f)=f(C)=f(4;1)=19.

Симплекс-метод

Реальные задачи линейного программирования содержат очень большое число ограничений и неизвестных и выполняются на ЭВМ. Симплекс-метод – наиболее общий алгоритм, использующийся для решения таких задач. Суть метода заключается в том, что после некоторого числа специальных симплекс- преобразований ЗЛП, приведенная к специальному виду, разрешается. Для того, чтобы продемонстрировать симплекс-метод в действии решим, с попутными комментариями следующую задачу:

[pic]

1. Для того, чтобы приступить к решению ЗЛП симплекс методом, надо привести ЗЛП к специальному виду и заполнить симплекс таблицу.

Система (4) – естественные ограничения и в таблицу не вписываются.
Уравнения (1), (2), (3) образуют область допустимых решений. Выражение (5)
– целевая функция. Свободные члены в системе ограничений и области допустимых решений должны быть неотрицательны.

В данном примере X3, X4, X5 – базисные неизвестные. Их надо выразить через свободные неизвестные и произвести их замену в целевой функции.

[pic]

Теперь можно приступить к заполнению симплекс-таблицы:

|Б. |X1 |X2 |X3 |X4 |X5 |C |
|X3 |0 |-1 |1 |1 |0 |1 |
|X4 |0 |1 |-1 |0 |1 |1 |
|X5 |1 |1 |1 |0 |0 |2 |
|f |0 |-6 |7 |0 |0 |3 |

В первом столбце данной таблицы обозначены базисные неизвестные, в последнем – значения свободных неизвестных, в остальных – коэффициенты при неизвестных.