Задания для решения в аудитории

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

Виды древесины	Шкафы	Серванты	Запасы
Береза	0,25	1	5,25
Сосна	1/3	0,25	35/12
Дуб	0	1	1
Кедр	1	0	1
Липа	0,5	0,5	3
Ель	1/2	0,25	9/4

2. Для изготовления тортов и пирожных используются следующие виды кондитерских добавок: ванилин, кокосовая стружка, какао, сахарная пудра, разрыхлитель теста. Затраты на производство единицы продукции приведены в таблице. Необходимо составить план выпуска продукции так, чтобы сахарная пудра и разрыхлитель были полностью израсходованы.

Вид добавок	Пирожные	Торты	Запасы
Ванилин	1	3	18
Кокосовая стружка	0	1	5
Какао	1	0	8
Сахарная пудра	1/3	1/3	2
Разрыхлитель	0,25	0,5	2

3. Для изготовления хлеба и булок «Хлебокомбинат» использует муку, воду, соль, сахар, яйца, молоко. Затраты на производство единицы продукции приведены в таблице. Необходимо составить план выпуска продукции так, чтобы сахар и соль были полностью израсходованы.

Продукты	Хлеб	Булки	Запасы
Мука	1/3	1	8
Вода	¼	1/3	37/12
Яйца	1	½	9
Молоко	1/3	½	11/3
Соль	¼	½	7/4
Сахар	1/2	1/4	2

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

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

Пусть дана система линейных неравенств:

Уравнение определяет на плоскости х₁Ох₂ прямую, которая разбивает эту плоскость на две полуплоскости, каждая из которых лежит по одну сторону от прямой. Системе неравенств удовлетворяет множество точек (х₁; х₂), лежащих в пересечении полуплоскостей, заданных неравенствами системы.

Для нахождения экстремального значения целевой функции при геометрическом методе решения используют на плоскости х₁Ох₂ вектор, который обозначается . Этот вектор показывает направление наискорейшего изменения целевой функции. Координаты вектора являются коэффициентами целевой функции Z, т. е. .

Для нахождения решения графическим методом необходимо:

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

2. Построить радиус – вектор

3. Провести линию уровня l₀, которая перпендикулярна ;

4. Переместить линию уровня по направлению вектора для задач на максимум и в направлении, противоположном , для задач на минимум. Решением задачи на min является первая точка, в которой прямая l₀ встречается с областью D при перемещении l₀ в положительном направлении вектора .

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

Если окажется, что прямая l₀ при перемещении параллельна одной из сторон многоугольника, то экстремум достигается во всех точках соответствующей стороны, а задача будет иметь бесчисленное множество решений, в таком случае говорят, что задача имеет альтернативный оптимум.

Пример. Решим задачу из пункта 1.1 графическим способом. Построим полуплоскости, заданные системой ограничений в первом квадранте системы координат (выбор первого квадранта обусловлен неотрицательностью переменных X и Y). Результирующей областью решений является многоугольник ABCDO. Построим вектор или подобный ему (с пропорциональными координатами). Построим линию уровня, перпендикулярную вектору . Возможными точками решения являются точки B и С.

Найдем координаты этих точек и вычислим значение целевой функции в каждой из них.

Для точки В	Для точки С
В (5,5; 7) Z = 27500 + 21000 = 48500 у. д. е.	С (6; 6) Z= 30000 +18000 = 48000 у. д. е.

Большая прибыль соответствует точке В, следовательно оптимальным использованием земельных ресурсов является распределение площадей 5,5 га под посадку огурцов и 7 га – помидоров. При этом будет получена прибыль в размере 48500 у. е. д.