Контрольные вопросы и задания

1. Когда задача ЛП имеет каноническую форму?

2. Когда задача ЛП имеет стандартную форму?

3. Приведите к канонической форме задачи ЛП:

а) б)

4. Приведите к стандартной форме задачи линейного программирования:

а)

б)

§2. Займемся рыбоводством. Графический метод решения задачи линейного программирования

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

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

Задача 1. Озеро можно заселить двумя видами рыб и. Средняя масса рыбы равнакг для видаи 1 кг для вида. В озере имеется два вида пищи:и. Средние потребности одной рыбы видасоставляет 1ед. кормаи 3 ед. кормав день. Аналогичные потребности для рыбы видасоставляют 2 ед.и 1 ед.. Ежедневный запас пищи поддерживается на уровне 500 ед.и 900 ед.. Как следует заселить озеро рыбами, чтобы максимизировать общую массу рыб?

Решение. Обозначим через число рыб видаи черезчисло рыб вида. Общая масса рыб будет равна. Кормаэтим рыбам потребуетсяединиц в день. Поскольку дневной запас кормаограничен величиной 500 ед., то мы должны ввести ограничения

Для корма получаем аналогично второе ограничение:

Кроме того, и.

Получили задачу линейного программирования:

Решим эту задачу графическим способом. Допустимые планы задачи располагаются в первом квадрате, т.к. .

Неравенство определяет полуплоскость. Для построения этой полуплоскости построим сначала прямую. Для построения прямой необходимо найти две точки на этой прямой. Пологая, находим, т.е. прямаяпересекает ось () в точке (500,0). Если взять, то. Через точки (0,250) и (500; 0) проводим прямую. Удобно взять точку (0;0). Если координаты удовлетворяют первому неравенству

Поэтому неравенство задает ту полуплоскость, которая содержит точку (0; 0). Отметим стрелками на чертеже выбранную полуплоскость. Аналогичным образом находим полуплоскость, заданную неравенством

Прямая - граница этой полуплоскости – пересекает координатные оси в точках (300; 0) и (0; 900). Область допустимых планов будет четырехугольник

Изучим поведение функции цели

,

для которой мы хотим найти точку максимума. Выясним, как изменяется значение целевой функции при переходе от точки к точке. Векторпоказывает направление и величину смещения. При смещении на векторцелевая функция изменяется на величину

Величина равна скалярному произведению вектораи вектора, образованного коэффициентами приив функции цели.

Этот вектор называют нормальным вектором целевой функции. Если вектор смещения перпендикулярен, т.е.то целевая функция не изменит своего значения:

.

Если угол между векторами иострый, то> 0, посколькуможно вычислять и как произведение длин векторовна косинус угла между ними. Если же угол междуитупой, то< 0. Нормальный вектор целевой функции показывает направление возрастание целевой функции, ибо в случаекосинус угла между этими векторами равен единице, идостигает максимально возможного длязначения.

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

Изобразим на рисунке 1 линию уровня нашей целевой функции. Прямаяпроходит через начало координат и перпендикулярна вектору. Из рисунка видно, что точкой максимума будет точки- точка пересечения прямыхи

Для нахождения координат точки составляем систему уравнения, в которую входят уравнения прямыхи:

Решением этой системы будет пара чисел: .

Итак, найден оптимальный план . В этой точке целевая функция имеет значение.

Смысл найденного ответа такой. Наибольшей будет общая масса рыб при условии, если в озере будет 260 рыб вида и 120 рыб видаи равна эта масса 640 кг.

Задача 2. На велосипедном заводе выпускают гоночные и дорожные велосипеды. Производство устроено так, что вместо двух дорожных велосипедов завод может выпустить один гоночный, причем гоночный велосипед приносит в 1,5 раза больше прибыли. Завод может произвести 700 дорожных велосипедов в день, однако склад может принять не более 500 велосипедов в день. Сколько нужно выпускать в день гоночных и сколько дорожных велосипедов, для того чтобы завод получал максимальную прибыль?

Решение. Обозначим через число гоночных, а черезчисло дорожных велосипедов, выпускаемых заводом ежедневно. Посколькугоночных велосипедов по производству эквивалентныдорожных велосипедов, то общее число «условных» велосипедов равно. Оно не может быть более 700. Получаем ограничение:

Возможности склада обуславливают второе ограничение:

Очевидно, .

Прибыль пропорциональна величине

Получаем задачу ЛП стандартной формы:

Решаем ее графически.

Нормальный вектор целевой функции изображен на чертеже в увеличенном масштабе. Нам важна не его длина, а его направление. Точкой максимума будет точкаВ– точка пересечения прямыхl₁и l₂. Ее координаты определяем из системы

Итак, завод должен выпускать 200 гоночных и 300 дорожных велосипедов в день. При этом прибыль завода будет максимальна.

Решая задачу линейного программирования графическим способом, мы можем встретиться со следующими случаями:

На рисунке а) изображен случай, когда целевая функция имеет единственную точку максимума – точку А и единственную точку минимума – точку О. В случае б) максимума у целевой функции нет, так как она может неограниченно возрастать. Точек минимума в случае б) бесконечно много. Все точки отрезка [СК] будут точками минимума. В случае в) целевая функция имеет единственную точку максимума и не имеет минимума (не ограничена с низу). В случае г) область допустимых планов пустая. Решений нет.

Выводы:

Решая задачу линейного программирования графически, нужно проделать следующие действия:

1. Преобразуйте задачу к стандартной форме, если это необходимо.

2. Для каждого неравенства выполните действия:

а) для неравенства ах + by ≤ с (или ах + by ≥ с) постройте прямую ах + by = с(l);

б) возьмите «пробную» точку, которая не лежит на прямой l, и выясните, какое из неравенств выполняется: ах + by < с или ах + by > с;

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

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

4. Если D = , то решений нет.

Если D ≠ , то изобразите вектор нормали целевой функции.

5. Изобразите линии уровня целевой функции , которые образуют семейство параллельных прямых, перпендикулярных вектору.

6. Определите по чертежу точку максимума или минимума (точку выхода или входа).

7. Вычислите значение целевой функции в точке экстремума (максимума или минимума).