Графическое представление.

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

Таблица 5.1.

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

Предположим, изготовлено x₁ изделия типа А₁ и х₂ изделий типа А₂. Тогда всего на их изготовление пошло всего 12х₁ + 4x₂, станко-часов токарного оборудования. Поскольку общий фонд рабочего времени токарных станков не может превышать 300 станко-часов, то имеет место неравенство

12x₁+4x₂ < 300 (5.1.1)

Аналогично для сварочных и шлифовальных работ получаем еще два неравенства:

4x₁+ 4x₂ < 120

3x₁+ 12x₂ < 250 (5.1.2)

Кроме того, ещё два неравенства возникает из факта неотрицательности числа изделий:

x₁ > 0 ; x₂ > 0 (5.1.3)

Прибыль от реализации x₁ изделий типа A₁ и x₂ изделий типа A₂ составит: F = 30x₁ + 40x₂ (млн. р.)

Геометрическая интерпретация поставленной задачи линейного программирования довольно проста в силу двумерности задачи и заключается в следующем. Ограничения (5.1.1) - (5.1.3) определяют выпуклую область допустимых решений задачи, называемую многоугольником решений. Стороны этого многоугольника задаются прямыми линиями, уравнения которых получаем из ограничений (5.1.1) - (5.1.3) заменой знаков >, < на знак равенства.

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

Можно показать, что целевая функция F принимает максимальное значение в одной из вершин заштрихованного многоугольника, а именно в вершине V. Чтобы найти искомую вершину, строим прямую постоянного уровня 30x₁ + 40x₂ = F и перемещаем ее параллельно самой себе, т.е. вдоль вектора{30,40} до тех пор, пока не достигнем границы области допустимых решений. Вершина V является точкой пересечения двух прямых, поэтому ее координата определяются решением системы уравнений

4x₁ + 4x₂ = 120

3x₁ + 12x₂ = 250

Решив эту систему, получим , . Следовательно, изготовив 12 изделий типа А₁ и 18 изделий типа А₂, можно получить максимально возможную прибыль:

F^max 30×12 + 40×18 = 1080 (млн.р.)

Если к изделиям типа А₁ и А₂ добавить хотя бы изделие типа А₃, то геометрическая интерпретация поставленной задачи поиска максимума прибыли существенно усложняется, поскольку от двумерного (плоского) случая n = 2 мы переходим к трехмерному (пространственному) случаю. Тем не менее, и в случае n = 3 возможно наглядное геометрическое решение задачи. Для решения производим следующие действия:

1. Вместо прямых линий, задаваемых неравенствами типа (5.1.1) - (5.1.3), строим плоскости:

g_i = a_i1x₁ + a_i2x₂ + a_i3x₃ = b_i; i = 1, 2, … , m

2. Находим области, определяемые каждым i -м ограничением задачи.

3. Вместо многоугольника решений определяем многогранник решений.

4. Вместо прямой постоянного уровня строим плоскость, задаваемую целевой функцией F = с₁x₁ + с₂x₂ + c₃x₃ и пересекающую многогранник решений.

5. Строим вектор нормальный к плоскости постоянного уровня.

6. Перемещаем плоскость постоянного уровня вдоль С до тех пор, пока не достигнем вершины V многогранника решений, в которой целевая функция F принимает максимальное значение.

7. Определяем координаты точки V и вычисляем значение F в этой точке.

Если число неизвестных задачи линейного программирования n > 3, то наглядное геометрическое представление задачи затруднительно и для ее решения используется так называемый симплекс-метод.

Поиск по сайту: