Специальные задачи линейного программирования в производственном менеджменте

10.2. Специальные задачи линейного программирования в производственном менеджменте

Задачи дробно-линейного программирования

Общая задача дробно-линейного программирования состоит в определении экстремального значения функции

= =                                (2.1)

при условиях

, i = 1, ..., m,                             (2.2)

xj  0,  j=1,...,n ,                                  (2.3)

где cj, dj, bi и aij - некоторые числа,  причем  > 0 в области допустимых решений. Такое условие не нарушает общности задачи, поскольку в том случае когда эта величина отрицательна, знак минус можно отнести к числителю. Как и в случае основной задачи линейного программирования, экстремальное значение целевая функция (2.1) принимает в одной из вершин допустимого  многогранника (естественно, при условии, что эта задача имеет оптимальный план).

Рассмотрим несколько содержательных примеров на составление математической модели.

Пример 1. Для производства n видов изделий предприятие использует m типов взаимозаменяемого оборудования. Каждый из видов изделий необходимо изготовить в количестве bj единиц (j=1,..,n), причем каждый из типов оборудования может быть занят изготовлением этих изделий не больше чем ai часов (i=1,...,m). Время изготовления одного изделия j-го вида на i-м типе оборудования равно aij часам, а затраты, связанные с производством одного изделия на данном типе оборудования равны cij рублей. Определить сколько изделий каждого вида на каждом из типов оборудования следует произвести так, чтобы себестоимость одного изделия была минимальной.

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

Рекомендуемые материалы

  (себестоимость одного изделия)

 (i=1, ..., m) – (ограничения на время),

 (j = 1, ..., n) – (ограничения на выпуск изделий),

Xij  0,  (i=1,...,m),  ( j=1,...,n)    - (условия неотрицательности).

Пример 2. Для выполнения n различных работ могут быть использованы рабочие m квалификационных групп. При выполнении j-й работы i-й группой рабочих выработка в единицу времени равна cij  (i=1,...,m), ( j=1,...,n) рублей. Общий фонд времени, в течение которого i-я группа рабочих может быть занята выполнением работ, не превышает bi единиц времени, а объем j-й работы равен aj рублей. Составить такой план выполнения работ, при котором производительность труда является максимальной.

Пусть Xij - время, выделяемое рабочими i-й квалификационной группы на j-ю работу. Тогда

   – (производительность труда),

     (i=1,...,m)  - (ограничения на время),

     (j=1,...,n) – (ограничения на объем работы),

Xij  0, (i = 1, ..., m), (j = 1, ..., n) – (условия неотрицательности).

Сформулированная выше задача (2.1)-(2.3) может быть сведена к задаче линейного программирования. Для этого следует обозначить

                                                 (2.4)

и ввести новые переменные , (j = 1, ..., n).   (2.5)

Тогда исходную задачу  (2.1)-(2.3) можно записать в виде

                                               (2.6)

при условиях

,    (i=1,...,m),              (2.7)

                                                    (2.8)

0,  ( j=1,...,n), 0.

Задача (2.6) - (2.8) является задачей линейного программирования и , следовательно, ее решение можно найти известными методами. Зная оптимальный план этой задачи, на основе соотношений (2.5) получим оптимальный план исходной задачи  (2.1) - (2.3).

Пример 3 .

=  

2 * X1 + X2 + X3 + 3 * X4 £ 300

X1 + 2 * X3 +  X4 £ 70

X1 + 2 * X2 + X 3 £ 340

Xj  0, (j = 1, ..., 4).

Сведем данную задачу к задаче линейного программирования. Для этого обозначим  через  и введем новые переменные

  ,   (j=1,...,4).  В результате приходим к следующей задаче:

 8 * Y1 + 3Y2 + 2 * Y3 + Y4

2 * Y1 + Y2 + y3 + 3 * Y4 - 300 * Y0  £  0

Y1 + 2 * Y3 + Y4 - 70 * Y0 £ 0

Y1 + 2 * Y2 + y3 - 340 * Y0 £ 0

Y1 +   Y2 + Y3 +  Y4 = 1

Y0, Yj  0,  ( j=1,...,4).

Решив данную задачу получим:

 (Y0, Y1, Y2, Y3, Y4) = ( 1/70, 1, 0, 0, 0)

Используя соотношения , определяем оптимальный план исходной задачи

 (X1, X2, X3, X4) = (70, 0, 0, 0), F() = 8.

Задачи целочисленного программирования

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

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

Математическая модель линейной целочисленной задачи может быть записана следующим образом:

F() =                        (1)

, bi  0, i = 1, ..., m,                      (2)

xj  0, j = 1, ..., n, xj – целые.                                  (3)

Существует эвристический подход к решению задач целочисленного программирования (ЗЦП), основанный на решении ЗЦП как задачи ЛП. Использование процедур округления нецелочисленного оптимального решения задачи ЛП дает возможность получать приближенное оптимальное целочисленное решение. Например, если в оптимальном решении двумерной задачи ЛП значения переменных х1 и х2 оказались равными 3,5 и 4,4 соответственно, то в качестве кандидатов на роль приближенного целочисленного оптимального решения необходимо рассмотреть точки (3;4), (4;4), (4;5), (3;5) полученные в результате округления. Заметим однако, что истинное оптимальное целочисленное решение может не совпадать ни с одним из четырех, указанных выше.

ПРИМЕР

F() = x1 – 3×x2 + 3×х3

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

2×x1 + x2 - х3 £ 4

4×x1 - 3×x2 £ 2

-3×x1 + 2×x2 + х3 £ 3

x1, х2, х3 ³ 0, целые.

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

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

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

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

Дробный алгоритм решения полностью целочисленных задач

Необходимым условием применения данного алгоритма является целочисленность всех коэффициентов и правых частей ограничений исходной задачи. Например, ограничение х1 + (1/3) ×х2 £ 13/2 записывается в виде 6×х1 + 2×х2 £ 39, в котором дроби отсутствуют.

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

Пусть последняя симплексная таблица задачи с ослабленными ограничениями имеет следующий вид:

Через x_i (i = 1, ..., m) обозначены базисные переменные, а через w_j (j = 1, ..., n) – небазисные переменные.

Рассмотрим i-ю строку симплексной таблицы, которой соответствует нецелое значение базисной переменной x_i, и выразим x_i через небазисные переменные:

, b_i – нецелое.

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

Пусть b_i = [b_i] + f_i, a_ij = [a_ij] + f_ij.

Отсюда следует , что

0 < f_i < 1, 0 £ f_ij < 1.

ПРИМЕР

Теперь наше уравнение принимает следующий вид:

Поскольку все переменные x_i и w_i принимают целые значения, правая часть уравнения должна быть целочисленной, откуда следует, что левая часть уравнения также должна принимать целые значения. Далее, так как f_ij ³ 0 и w_i ³ 0 для всех i и j, то

.

Следовательно, выполняется неравенство .

Это означает, что

, поскольку f_i < 1.

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

.

Последнее ограничение перепишем в виде равенства

, где S_i – неотрицательная дополнительная переменная, которая по определению должна принимать целые значения. Такое ограничение-равенство определяет отсечение Гомори для полностью целочисленной задачи.

Из симплексной таблицы следует, что w_i = 0, и, таким образом, S_i = – f_i, т. е. данная компонента решения не является допустимой. Это означает, что полученное ранее решение не удовлетворяет новому ограничению. В такой ситуации следует использовать двойственный симплекс-метод, реализация которого обеспечивает отсечение некоторой области многогранника решений, не содержащей точек с целочисленными координатами.

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

Получим новую таблицу:

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

Название дробный алгоритм связано с тем обстоятельством, что все ненулевые коэффициенты введенного отсечения меньше единицы. Общее число ограничений порожденной задачи не может превышать (m + n).

Процесс определения оптимального плана методом Гомори включает следующие этапы:

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

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

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

4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают процесс.

ПРИМЕР

F() = 7×x1 + 9×x2

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

-x1 + 3×x2 £ 6  -x1 + 3× x2 + x3 = 6

7×x1 + x2   £ 35  7×x1 + x2 + x4 = 35

x1, х2 ³ 0, целые; x1, ..., x4 ³ 0, целые.

Таблица 1

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

x2 + 7/22×x3 + 1/22×x4 = 7/2.

Следовательно, уравнение отсечения Гомори имеет вид

- 7/22×x3 - 1/22×x4 + = -1/2

В результате получаем новую таблицу:

Таблица 2

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

- 1/7×x4 - 6/7× + = -4/7

Таблица 3

В результате получили оптимальное целочисленное решение исходной задачи:

x1 = 4, x2 = 3, F() = 55.

Дадим геометрическую интерпретацию задачи. На рис. 1 показано, что введение двух ограничений позволяет получить новую экстремальную точку с координатами (4;3), в которой достигается оптимум исходной целочисленной задачи.

1 ОТСЕЧЕНИЕ: - 7/22×x3 - 1/22×x4 + S₁ = -1/2 или

- 7/22×x3 - 1/22×x4  £ -1/2

Тогда из таблицы 1 получим

-7/22×(х1 - 3×х2 + 6) - 1/22× (-7×x1 - х2 + 35) £ -1/2         Þ

7×(х1 - 3×х2 + 6) + (-7×x1 - х2 + 35) ³ 11       Þ     х2 £  3.

2 ОТСЕЧЕНИЕ:      - 1/7×x4 - 6/7×S₁ + S₂ = -4/7  или

Ещё посмотрите лекцию "Производительность труда" по этой теме.

- 1/7×x4 - 6/7×S₁ + S₂ £ -4/7

Теперь из таблиц 1 и 2 получим

- 1/7×(-7×x1 - х2 + 35)  - 6/7×(7/22×x3 + 1/22×x4 - 1/2)  £  -4/7    Þ

-1/7×(-7×x1 - х2 + 35) - 6/7×[7/22×(х1 - 3×х2 + 6) + 1/22×(-7×x1 - х2 + 35) - 1/2 ] £ -4/7 Þ х1 + х2 £ 7.

Рис. 1. Графическая интерпретация задачи