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

Расчетно-графическая работа

по курсу «Методы Оптимизации»

 

Вариант № 11

 

 

Выполнил студент

Группы И-5-6

Логинов Д.О.

Проверил

Казаков О.А.

 

Москва 2008

Задача 1.

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

 

Исключим  из неравенств и целевой функции:

 

Выражаем из неравенств :

 

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

 

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

 

Строим линию уровня:

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

 

По теореме:

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

 

На графике видно, что точка максимума находится в точке .

Найдём значение всех угловых точек в данной области и значения целевой функции в них:

 

 

Так как , то оптимальная точка _,

 

Задание 2.

Решить задачу линейного программирования симплекс-методом.

 

 

Перейдём к основной задаче линейного программирования:

 

Введём фиктивные переменные, чтобы избавиться от неравенств:

 

Выбираем фиктивные переменные в качестве базисных переменных:

 

Решение допустимо, так как все свободные члены положительные.

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

 

Выбираем  в качестве новой базисной переменной.

Проверим выполнение условия :

Не подходит, так не выполняется условие

Найдём :

 

Выбираем первое уравнение, так как  минимально:

 

Решение допустимо, так как все свободные члены положительные.

 

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

 

Задание 3.

Решить задачу условной минимизации методом множителей Лагранжа.

 

Формируем функцию Лагранжа:

 

Минимум функции будет там, где будет минимум функции Лагранжа (то есть в стационарной точке функции Лагранжа).

 

Стационарные точки функции Лагранжа:

	1	2	3	4	5	6	7
	0	0	0	2	- 2	- 1,11	1,11
	0	2	-2	0	0	- 1,66	1,66
	2	2	2	0	0	0	0
	3	0	0	3	3	0	0
	0	- 0,75	0,75	- 0,5	0,5	0,9	- 0,9
	1	1	1	1	1	1	1

 

Точка 1 не удовлетворяет условию , значит решение недопустимо.

Так как , следовательно, точки 3, 5, 6, являются недопустимыми.

Точки 2, 4, 7 являются допустимыми.

 

Вычислим значение функции Лагранжа и самой функции в этих точках:

 

Минимальное значение функции в точке

 

 

Задание 4.

Найти градиент и гессиан целевой функции.

Построить линейную и квадратичную модель целевой функции в заданной точке. Найти стационарные точки квадратичной модели.

Изобразить на рисунке линии уровня квадратичной модели.

 

Нахождение градиента

Градиент – вектор, координаты которого равны частным производным функции по соответствующим аргументам

Градиент для функции двух переменных имеет вид:

 

Нахождение гессиана

Гессиан – матрица, обратная вторым частным производным функции

Для функции двух переменных имеет вид:

 

 

Найдем значение целевой функции, градиента и гессиана в точке

 

Нахождение линейной модели

Линейная модель – это касательная плоскость к поверхности,

  – точка касания, вычисляется по формуле:

 

 

Расчетно-графическая работа

по курсу «Методы Оптимизации»

 

Вариант № 11

 

 

Выполнил студент

Группы И-5-6

Логинов Д.О.

Проверил

Казаков О.А.

 

Москва 2008

Задача 1.

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

 

Исключим  из неравенств и целевой функции:

 

Выражаем из неравенств :

 

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

 

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

 

Строим линию уровня:

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

 

По теореме:

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

 

На графике видно, что точка максимума находится в точке .

Найдём значение всех угловых точек в данной области и значения целевой функции в них:

 

 

Так как , то оптимальная точка _,

 

Задание 2.