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

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

Если в задаче ЛП содержится не более трех переменных величин, то ее можно решить графически. Покажем это на конкретной задаче.

В составлении рациона используются два вида продуктов, содержащих вещества А, В и С. Содержание этих веществ в продуктах и цена единицы продукта представлены в таблице 2.1:

Таблица 2.1

Вид продукта	Содержание вещества	Цена за единицу (руб.)
	А	В	С
I
II

Какое количество продуктов каждого вида необходимо расходовать, чтобы получить наиболее дешевый рацион, если должно быть потреблено не менее 60 единиц вещества А, не менее 40 единиц вещества В и не более 50 единиц вещества С?

Пусть (х, х₂) – рацион. Тогда f = 6x+ 5x– стоимость рациона.

Условие составления рациона определяется системой неравенств:

2x+ Зх₂ 60, 4x+ х₂ 40, x+ х₂ 50.

Каждое из неравенств системы задает полуплоскость в системе координат xох₂; система неравенств задает пересечение полуплоскостей

Рис. 2.1. Геометрический метод

Область решения системы неравенств, т.е. множество всех рационов (x, x), представляет собой пятиугольник АВСДЕ. Построим опорную прямую, т.е. график уравнения

f = 6 x + 5 x

при некотором значении f, например, при f = 0. Это будет прямая линия, проходящая через начало координат. При ее перемещении параллельно самой себе в направлении нормального вектора

(6; 5) значение f (свободного коэффициента уравнения) будет возрастать и ясно, что в точке Е функция принимает наименьшее значение, а в точке В – наибольшее значение. Находим координаты точки Е, решая систему уравнений:

Находим значение f, соответствующее точке Е.

Ответ: Наиболее дешевый рацион получается, если включить в него 6 ед. первого продукта и 16 ед. второго продукта. Этот рацион стоит 116 рублей.

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

Дата добавления: 2014-10-31