Задача линейного программирования. Три типа оборудования

Страницы работы

Фрагмент текста работы

ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

(Н. П. Чурляева учеб. пособие «Методы математического моделирования». – САА, Красноярск 2001)

Все задачи математического программирования сводятся к одной общей постановке: найти значения переменных х1, х2...... хn, доставляющих max(min) заданной целевой функции F(х1, х2,..., хn)и удовлетворяющих одновременно ряду условий – ограничениям:

gi (x1, x2,...xn) < > bi;                  i = 1, 2,...., m;       xj > 0.   (1)

Задача линейного программирования возникает, если целевая функция F и все ограничения gi линейны относительно х12,..., хn , т.е.:

;                  ;      i = 1,…, m.  (2)

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

Таблица

Тип оборудования

Затраты времени (станко-час) на обработку одного изделия

Общий фонд рабочего времени оборудования

А1

А2

Токарное

Сварочное

Шлифовальное

12

4

3

4

4

12

300 ч.

120 ч.

250 ч.

Прибыль (млн.р.)

30

40

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

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

12·x1 + 4·x2 < 300                                          (3)

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

4·x1 + 4·x2 < 120,                                           (4)

3·x1 + 12·x2 < 250.

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

x1 > 0,            x2 > 0.                                                 (5)

Прибыль от реализации x1 изделий типа A1 и x2 изделий типа A2 составит F = 30x1 + 40x2, млн. р.

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

graf1.jpg

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

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

4·x1 + 4·x2 = 120,

3·x1 + 12·x2 = 250.

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

Fmax   30 × 12 + 40 × 18 = 1080 млн.р.

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

1.  Вместо прямых, задаваемых неравенствами типа (3), (4), (5), строим плоскости

gi  = ai1 · x1 + ai2 · x2 + ai3 · x3 = bi;        i = 1, 2,…, m.

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

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

4.         Вместо прямой постоянного уровня строим плоскость, задаваемую целевой функцией F = с1 · x1 + с2 · x2 + c3 · x3 и пересекающую многогранник решений.

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

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

Похожие материалы

Информация о работе