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

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

(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