![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Для того чтобы отчетливее представить себе особенности решения задач линейного программирования и различные случаи, которые могут при этом встретиться, удобно воспользоваться геометрической интерпретацией.
Начнем рассмотрение геометрического отображения с одного уравнения с двумя переменными:
2х1+х2=2.
Очевидно, что данному уравнению соответствует множество решений. Отобразим их на графике, построив в системе прямоугольных координат прямую, соответствующую заданному уравнению.
Для нахождения точек пересечения прямой с осями координат можно, поочередно, прировнять каждую из переменных к нулю и вычислить значение второй, а затем проделать эту процедуру в обратном порядке. Для рассматриваемого уравнения имеем: х1=1; х2=2. Эти координаты определяют на графике положение искомой прямой (рис 2.1).
![]() | |||
| |||
х2
х1
0 1 2 3
Рис.2.1
|
3
1
х1
0 1 2 3
Рис. 2.2
х2
|
3
1
х1
0 1 2 3
Рис. 2.3
(а)
(б)
(в)
(г)
х1≥0; х2≥0
|
7
6
а
5 в
3 Е D г
С
2
1 б х1
А В
1 2 3 4 5 6 7 8 9
Рис. 2.4
Пусть:
|
При решении задач линейного программирования оптимальное решение удается получить не всегда. Рассмотрим возможные ситуации, приводящие к такому результату, на примерах.
1. Представить графически систему ограничений:
|
3
1
х1
0 1 2 3
Рис. 2.5
На рисунке 2.5 видно, что нет таких значений х1 и х2, которые бы удовлетворяли заданной системе ограничений. Следовательно, в данной системе отсутствует ОДР. Системы ограничений, подобные рассматриваемой, называют несовместимыми.
2. Построить систему:
х1 + х2 ≥ 1
х1 ≥ 0, х2 ≥ 0
х2
3
2
1
х1
1 2 3
Рис. 2.6
Рассматриваемая система приведена на рис. 2.6, из которого видно, что ОДР не ограничена сверху. В таком случае при максимизации целевой функции решение получено быть не может, так как линия целевой функции может бесконечно перемещаться в сторону увеличения Z. Соответственно, при минимизации целевой функции ОДР должна быть ограничена снизу.
Решение общих задач линейного программирования при m-n=2 является частным практически крайне ограниченным случаем. Пользоваться геометрической интерпретацией для отыскания решения даже при n-m=3, т.е. в трехмерном пространстве, затруднительно. При n-m=k>3 геометрическая интерпретация теряет наглядность. Однако соответствующая терминология может оказаться удобной: можно говорить об области допустимых решений, как о некотором «сверхмногограннике» в пространстве k измерений, ограниченном m «гиперплоскостями»; об оптимальном решении – как об одной из «вершин» этого многогранника, о каждой «вершине» - как об «опорной точке» и т.д.
Несмотря на то, что построение для m-n=2 относится к частному случаю, из него вытекают определенные выводы, относящиеся вообще к свойствам решения основной задачи линейного программирования.
1. Оптимальное решение, если оно существует, не может лежать внутри области допустимых решений, а только на ее границе.
2. Оптимальное решение всегда достигается в одной из вершин многоугольника допустимых решений (если оно достигается на целой стороне, то оно же достигается и в каждой из вершин, через которые проходит эта сторона). Решение, лежащее в одной из вершин ОДР, называется опорным решением, а сама вершина – опорной точкой.
3. Для того, чтобы найти оптимальное решение, в принципе достаточно перебрать все вершины ОДР (опорные точки) и выбрать из них ту, где функция Z достигает максимума.
4. Задача может не иметь решения даже в случае, когда существует ОДР.
Дата публикования: 2015-01-23; Прочитано: 631 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!