Реферат: Линейное программирование

(5)

– функция Лагранжа, - множители Лагранжа.

– функция n+m переменных .

Рассмотрим стационарные точки функции , которые получим, приравняв к нулю частные производные по и по :

(6)

(7)

Если в стационарной точке (x*, y*) функция достигает минимума, то обеспечивает минимум функции q(x) и при выполнении ограничений (3), т.е. даёт решение задачи.

Задача на условный минимум целевой функции q(x) при наличии ограничений типа равенств сводится к задаче на определение стационарных точек функции Лагранжа .

3. Линейное программирование: формулировка задач и их графическое решение

3.1. Задача ЛП

Рассмотрим на примере задачи фирмы Reddy Mikks. Небольшая фабрик изготовляет два вида красок: для наружных (E) и внутренних (I) работ. Продукция поступает в оптовую продажу. Для производства красок используется два исходных продукта – A и B. Максимально возможные суточные запасы этих продуктов составляют 6т и 8т соответственно. Расходы A и B на производство 1т соответствующих красок приведены в таблице.

Исходный продукт	Расход на тонну краски		Максимальный запас, т.
краска E	краска I
A	1	2	6
B	2	1	8

Суточный спрос на краску I никогда не превышает спроса на краску E более чем на 1т. Спрос на I не превышает 2т. Оптовая цена за 1т краски E – 3000$, I – 2000$. Какое количество краски каждого вида фабрика должна производить, чтобы доход от реализации продуктов был максимальным?

Так как нужно определить объём производства каждого вида краски, переменными в модели являются:

x ­E – суточный объём производства краски E (в тоннах);

xI – суточный объём производства краски I (в тоннах).

Обозначив доход (в тыс. $) через , можно дать математическую формулировку целевой функции: определить (допустимые) значения x­E и xI, максимизирующие величину общего дохода

Ограничения на расход исходных продуктов:

(для A)

(для B)

Ограничения на величину спроса на продукцию:

Потребуем выполнения условия неотрицательности переменных:

Получили математическую модель:

Определить суточные объёмы производства (в т.) краски I и E, при которых достигается

(целевая функция)

при ограничениях

3.2. Графическое решение задачи ЛП

Построим область допустимых решений, в которой одновременно выполняются все ограничения. Искомое пространство решений – многоугольник ABCDEF. Пространство решений содержит бесконечное число точек, являющихся допустимыми решениями, но, несмотря на это, можно найти оптимальное решение, если выяснить, в каком направлении возрастает целевая функция модели z=3x­E+2xI. На график наносят ряд параллельных линий, соответствующих уравнению целевой функции при нескольких произвольно выбранных и последовательно возрастающих значениях , что позволяет определить наклон целевой функции и направление её увеличения. На видно, что оптимальному решению соответствует точка C, являющаяся пересечением прямых