Лекция: Графическое решение задачи линейного программирования

▼

Пример

Словесная формулировка задачи

Фирма изготовляет два вида изделий.

Для производства изделий используются два исходных продукта и. Возможные запасы этих продуктов и нормы их расхода на производство каждого изделия приведены в таблице.

Изучение рынка сбыта показало, что суточный спрос на изделие 1-ого вида никогда не превышает спроса на изделие 2-ого вида более чем на тонну. Кроме того, установлено, что суточный спрос на изделие 1-ого вида никогда не превышает тонн.

Оптовая цена одной тонны изделия 1-ого вида равна тыс. у.е., 2-ого вида равна тыс. у.е.

Какой объем изделий каждого вида должна производить фирма в сутки, чтобы суточный доход от реализации продукции был максимальным?

Математическая формулировка задачи

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

1) С помощью каких искомых величин можно выразить числом заданную цель на основе заданных исходных данных?

2) Каким алгебраическим выражением можно представить заданную цель с помощью исходных данных и соответствующих искомым величинам переменных?

3) Какие алгебраические ограничения должны быть наложены на переменные, чтобы выполнялись все заданные исходные условия?

Ответы на эти вопросы для рассматриваемой задачи:

1) — суточные объемы производства изделий 1-ого вида и 2-ого вида (в тоннах);

2)

3)

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

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

1

2

3

4

5

6

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

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

1) множества точек, удовлетворяющих уравнению (обозначено прямой с соответствующим номером);

2) множества точек, удовлетворяющих строгому неравенству (обозначено стрелкой).

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

Рис. 1.5.

Целевая функция геометрически представляется (рис. 1.6) прямой, соответствующей произвольно выбранному значению. Выбирая последовательно увеличивающиеся значения (направление увеличения обозначено стрелкой и определяется вектором, координатами которого являются коэффициенты целевой функции), можно найти оптимальное решение

Рис. 1.6.

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

▲

Обобщая рассмотренный пример, может быть доказана

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

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

(1.1)

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

(1.2)

(1.3)

Допустим, что система (1.2) при условии (1.3) совместна и ее многоугольник решений ограничен. Каждое из неравенств (1.2) и (1.3), как отмечалось выше, определяет полуплоскость с граничной прямой:. Линейная целевая функция (1.1) при фиксированных значениях является уравнением прямой линии:. Построим многоугольник решений системы ограничений (1.2) и график линейной целевой функции (1.1) при (рис. 1.7).

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

Рис. 1.7.

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

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

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

1. Прямая, передвигаясь в направлении вектора (максимизация) или противоположно ему (минимизация), постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная целевая функция не ограничена на многоугольнике решений как сверху, так и снизу (рис. 1.8).

Рис. 1.8.

2. Прямая, передвигаясь, все же становится опорной относительно многоугольника решений (рис. 1.9, рис. 1.10, рис. 1.11). Тогда в зависимости от вида области линейная целевая функция может быть ограниченной сверху и неограниченной снизу (рис. 1.9), ограниченной снизу и неограниченной сверху (рис. 1.10), либо ограниченной как снизу, так и сверху (рис. 1.11).

Рис. 1.9.

Рис. 1.10.

Рис. 1.11.

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

▼

Пример

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

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

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