Программирования

Основная задача линейного программирования формулируется следующим образом. Найти наибольшее или наименьшее значение функции f = если переменные х неотрицательные иудовлетворяют системе уравнений:

.

Эту систему уравнений можно записать в матричной форме где:

, ,

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

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

Задача. Пусть дана функция f = и система ограничений:

Требуется найти оптимальный план. Покажем, как эту задачу можно свести к основной задаче ЛП. В левую часть каждого i - го неравенства добавим неотрицательную величину у такую, чтобы неравенство обратилось в равенство ( = l,2 ,..., m). В результате система неравенства обратится в систему уравнений:

Целевую функцию f запишем в виде:

f =

То есть, по существу целевая функция не изменилась. Предположим, что точка (x , x ,...,x_n, y , y₂,...,y_m) удовлетворяет системе уравнений. Тогда, опуская положительные слагаемые у , получаем, что точка (x , х₂,..., х ) удовлетворяет системе неравенств. Наоборот, если точка (х ,х₂,...,х ) удовлетворяет системе неравенств, то можно подобрать неотрицательные величины у , у₂,...,у_m такие, что точка (x ,х₂,…, х , у , у₂,..., у_m) будет удовлетворять системе уравнений. Наконец, ясно, что если функция f принимает оптимальное значение в точке (x , х₂,...,х , y ,y , , у_m), то она примет оптимальное значение в точке (x ,х₂,...,х ) и наоборот.

Добавочные переменные величины y , у₂,...,у_m называются балансовыми переменными. Если система ограничений задачи ЛП задана неравенствами

,

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

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

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

Таблица 1

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

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

---

Дата добавления: 2015-07-26