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

Примеры решения типовых задач

Пример 1. Найти наибольшее и наименьшее значения функции  в области решений системы линейных неравенств

Решение

1. Построим область решений системы линейных неравенств.

                          у

 

 

                                                     

                                1                  

                 

                                О            2                        x

                                                              

                                

 

Прямая () , точки для построения  и . Так как  верно, то полуплоскость обращена в сторону точки .

Прямую ()  строим по точкам  и ; неравенство  верное, полуплоскость направлена к началу координат.

Прямая ()  построена по точкам  и ; полуплоскость обращена в сторону .

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

2. Построим градиент функции . Это вектор с координатами  с началом в точке . Перпендикулярно градиенту построим одну из линий уровня.

3. Параллельным движением линии уровня в направлении градиента   найдем точку «входа» линии уровня в область – это точка О(0,0). Вычислим значение функции в этой точке: .

4. Продолжая движение линии уровня в направлении градиента , найдем точку «выхода» линии уровня из области – это точка А. Для определения ее координат решим систему уравнений прямых  и :  Решение системы уравнений  и . Вычислим значение функции в точке : .

Ответ: , .

 

 

Задачи для самостоятельного решения

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

1) 2) 3)

4)   5)      6)          7)

 

 

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

Примеры решения типовых задач

Пример 2. Задача о рационе

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

При составлении суточного рациона кормления скота можно использовать свежее сено не более 50 кг и силос не более 85 кг. Рацион должен содержать не менее 30 кормовых единиц, 1000 г белка, 100 г кальция и 80 г фосфора. Определить оптимальный рацион, исходя из условия минимума себестоимости.

В таблице 4 приведены данные о содержании указанных компонентов в 1 кг каждого корма и себестоимость этих кормов.

Таблица 7

Корм	Компоненты				Себестоимость, ден. ед.
	кормовые единицы	белок, г/кг	кальций, г/кг	фосфор, г/кг
Сено свежее, кг	0,5	40	1,25	2	1,2
Силос, кг	0,5	10	2,5	1	0,8

Решение

Этап 1. Составление математической модели задачи.

Обозначим через  и  количество кг сена и силоса, которое предполагается включить в рацион. Естественно, что , . Из условия задачи следует, что  (кг);  (кг).

Количество кормовых единиц в рационе можно выразить суммой , что должно быть, по условию, не меньше 30: (ед.), или .

Ограничения по содержанию в рационе белка, кальция и фосфора имеют вид:  

(г), или  (для белка);

(г), или  (для кальция); 

(г) (для фосфора).

Себестоимость рациона в принятых обозначениях можно выразить формулой (руб.). Итак, математическая модель задачи построена.

Математическая постановка задачи: найти неотрицательные значения переменных  и , которые удовлетворят системе линейных неравенств

и при которых целевая функция принимает наименьшее значение .