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

Пусть требуется найти и , удовлетворяющие системе неравенств

(5.5)

и условиям неотрицательности

, (5.6)

для которых функция

(5.7)

достигает максимума.

Решение.

Построим в системе прямоугольных координат область допустимых решений задачи (рис.11). Для этого, заменяя каждое из неравенств (5.5) равенством, строим соответствующую ему граничную прямую (i = 1, 2, … , r)   Рис. 11

Эта прямая делит плоскость на две полуплоскости. Для координат любой точки А одной полуплоскости выполняется неравенство , а для координат любой точки В другой полуплоскости - противоположное неравенство . Координаты любой точки граничной прямой удовлетворяют уравнению .

Для определения того, по какую сторону от граничной прямой располагается полуплоскость, соответствующая заданному неравенству, достаточно «испытать» одну какую-либо точку (проще всего точку О (0;0)). Если при подстановке её координат в левую часть неравенства оно удовлетворяется, то полуплоскость обращена в сторону к испытуемой точке, если же неравенство не удовлетворяется, то соответствующая полуплоскость обращена в противоположную сторону. Направление полуплоскости показывается на чертеже штриховкой. Неравенствам и соответствуют полуплоскости, расположенные справа от оси ординат и над осью абсцисс.

На рисунке строим граничные прямые и полуплоскости, соответствующие всем неравенствам.

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

При построении области допустимых решений в зависимости от конкретного вида системы ограничений (неравенств) на переменные может встретиться один из следующих четырех случаев:

 

Рис. 12. Область допустимых решений пустая, что соответствует несовместности системы неравенств; решения нет.

 

 

Рис. 13. Область допустимых решений изобра- жается одной точкой А, что соответствует единственному решению системы.

 

 

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

 

Рис. 15. Область допустимых решений неограни-ченная, в виде выпуклой многоугольной области. Допустимых решений бесконечное множество.

 

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

Вектор градиента , перпендикулярный к линиям уровня, показывает направление возрастания R.

Задача отыскания оптимального решения системы неравенств (5.5), для которого целевая функция R (5.7) достигает максимума, гео­метрически сводится к определе­нию в области допустимых реше­ний точки, через которую пройдет линия уровня, соответствую­щая наибольшему значении пара­метра R

.

 

Рис. 16

Если область допустимых решений есть выпуклый многоугольник, то экстремум функции Rдостигается, по крайней мере, в одной из вер­шин этого многоугольника.

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

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

 

Пример.

Пусть требуется найти значения и , удовлетворяющие системе неравенств

и условиям неотрицательности

, ,

для которых функция

достигает максимума.

Решение.

Заменим каждое из неравенств равенством и построим граничные прямые:

 

 

Рис. 17

 

Определим полуплоскости, соответствующие данным неравенствам, путём «испытания» точки (0;0). С учетом неотрицательности и получим область допустимых решений данной задачи в виде выпуклого многоугольника ОАВДЕ.

В области допустимых решений находим оптимальное решение, строя вектор градиента , показывающий направление возрастания R.

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

Ответ:

 

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

Таблица 9.

 

№ варианта Экстремум a b c Ограничения
Max 2,1 5,5 1,4 ; ; ; ;
Max 3,0 0,9 1,8 ; ; ; ;
Min 4,5 6,7 0,6 ; ; ; ;
3 Max 0.8 5,4 3,1 ; ; ; ;
Min 1,9 2,6 -1,2 ; ; ; ;
Min 4,1 5,2 9,3 ; ; ; ;
Min 5,4 1,5 5,7 ; ; ; ;
Max 3,8 2,9 1,3 ; ; ; ;
Max 1,4 5,8 4,2 ; ; ; ;
Min 4,6 1,1 6,5 ; ; ; ;

 

Список литературы

1. Бахвалов Н. С. Численные методы. - М.: Наука. 1975.

2. Калиткин Н. Н. Численные методы. - М.: Наука. 1978.

3. Демидович Б. П., Марон И. А. Основы вычислительной математики. – М.:Наука, 1970.

4. Березин И. С., Жидков Н. П. Методы вычислений. – Ч.1 : Наука, 1966; Ч.2 : М.: Физматгиз, 1962.

5. Мак-Кракен Д., Дорн У. Численные методы и программирование на ФОРТРАНе. - М.: Мир, 1969.

6. Турчак Л. И. Основы численных методов. – М.: Высш. шк., 1985.

7. Воробьёва Г. Н., Данилова А. Н. Практикум по численным методам.– М.: Высш. шк., 1979.

 

Содержание

1. Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Приближенное решение нелинейных уравнений. . . . . . . . . . . . . . . . . . . . . . . . 4

3. Решение систем линейных алгебраических уравнений . . . . . . . .. . . . . . . . . . . .8

4. Аппроксимация функций с помощью метода наименьших квадратов . . . . . .15

5. Решение обыкновенных дифференциальных уравнений. . . . . . . . . . . . . . . . . 21

6. Многомерная оптимизация, Линейное программирование . . . . . . . . . . . . . . .25

Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32