Примеры выполнения заданий

Тема: Простейшие задачи линейного программирования с двумя переменными.

Краткое изложение темы.

Существуют два наиболее распространенных способа решения задач линейного программирования (ЗЛП): графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания и решения (хотя занимает много времени, так как требует тщательного построения чертежа). Также этот метод позволяет практически одновременно найти решение на минимум и максимум, тогда как симплекс-методом придется делать "два подхода".

Основные шаги по решению ЗПЛ графическим методом следующие:

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

- построить линию уровня целевой функции,

- двигать линию уровня в нужном направлении, пока не достигнем крайней точки области - оптимальной точки (или множества). При этом можно найти единственное оптимальное решение (точку), множество (отрезок) или ни одного (область пустая или не ограниченная в нужном направлении).

Примеры выполнения заданий.

Пример 1. Построить множество точек плоскости, координаты которых удовлетворяют следующим соотношениям: .

Решение:

1. Заменить знаки неравенств на знаки точных равенств и выразим у.

2. Построить графики уравнений прямых , .

х 0 1 у -1 0	х 0 1 у 1 0

3. Найти область решений неравенств.

Ответ: Областью решений неравенств является заштрихованная область.

Пример 2. Максимизировать линейную форму при ограничениях: , , .

Решение:

1.Заменить знаки неравенств на знаки точных равенств.

2.Построить графики уравнений прямых , , .

3.Найти область решений неравенств.

(Областью решений неравенств является треугольникMNP)

4. Построим вектор С (2; 2) и проведем опорную прямую, которая при выходе из треугольника решений пройдет через точку Р(3; 15/2), а потому в точке Р линейная функция  принимает наибольшее значение, т. е. максимизируется, и .

Ответ: .

Пример 3.

Для изготовления двух видов изделий I и II используются три вида сырья.

На производство единицы изделия I требуется затратить сырья первого вида 13 кг, сырья второго вида – 32 кг, сырья третьего вида – 58 кг.

На производство единицы изделия II требуется затратить сырья первого вида 24 кг, сырья второго вида – 32 кг, сырья третьего вида – 29 кг.

Производство обеспечено сырьем первого вида в количестве 312 кг, сырьем второго вида – 480 кг, сырьем третьего вида – 696 кг.

Прибыль от реализации единицы готового изделия I составляет 4 усл. ед., а изделия II – 3 усл. ед.

Требуется составить план производства изделий I и II, обеспечивающий максимальную прибыль от их реализации, если заранее планируется изготовление не менее 10 единиц изделий I и II.

Решение:

Ответ: z = 54 усл. ед.