Линейная производственная задача

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

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

Примем следующие обозначения:

 i    – номер группы оборудования (i=1, 2, …, m);  

 j    – номер вида изделия (j=1, 2, …, n);

a_ij  – норма времени на обработку единицы i-го изделия на j-ой группе оборудования;

b_i  – действительный фонд времени работы i-й группы оборудования;

x_i  – планируемое количество единиц  j-го изделия;

(x₁, x₂, …, x_n)  – искомый план производства.

 

Какова бы ни была производственная программа (x₁, x₂, …, x_n), ее компоненты должны удовлетворять условию, что суммарное время обработки всех изделий на данной группе оборудования не должно превышать фонда времени работы этой группы оборудования. На обработку x₁ единиц первого изделия на i-й группе оборудования будет затрачено a_i1x₁ единиц времени, на обработку x₂ единиц второго изделия на той же группе оборудования будет затрачено a_i2x₂ единиц времени и т.д. Необходимое время на обработку всех x₁, x₂, …, x_n изделий на i-й группе оборудования будет равно сумме

                                  

Эта сумма не может превышать фонд времени работы i-й группы оборудования, т.е. должна быть £ b_i. Выписывая такие условия для всех m групп оборудования, получаем:

                     (1)

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

                              x₁ ³ 0, x₂, ³ 0, …, x_n³ 0.

                                 (2)

 

Обозначим через с_j прибыль на единицу j-го изделия. При плане производства       (х₁, х₂, …, х_n) прибыль предприятия будет равна:

                              z = c₁x₁ + c₂x₂ + … + c_nx_n.                                  (3)

 

Мы хотим составить производственную программу (х₁, х₂, …, х_n) так, чтобы функция (3) приняла наибольшее значение при выполнении всех других условий.

9

Система линейных неравенств (1), (2) и линейная форма (3) образуют математическую модель задачи о рациональном использовании производственных мощностей. Среди всех решений системы линейных неравенств (1), удовлетворяющих условию неотрицательности (2), необходимо найти такое решение, при котором линейная форма (3) принимает наибольшее возможное значение. Это – задача линейного программирования.

Исходные параметры задачи могут быть представлены в виде технологической матрицы A затрат ресурсов на единицу продукции каждого вида, вектора B объемов ресурсов и вектора C удельной прибыли:

,       ,   C=(c₁, …, c_n)

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

, , ,      или кратко    

Задача состоит в том, чтобы найти производственную программу, максимизирующую

прибыль:

            (4)

при условиях:

        (5)

                         (6)

10

Полученную задачу линейного программирования с двумя переменными можно решить графически. Система линейных неравенств             (5), (6) определяет выпуклый многоугольник OPQRS допустимых решений. Линии уровня функции Z перпендикулярны вектору-градиенту grad Z=(6, 9) и образуют семейство параллельных прямых (градиент указывает направление возрастания функции). Наибольшего значения функция Z достигает в точке R. Координаты этой точки определяют оптимальный план производства x₁=3, x₂=2, а максимальная прибыль будет равна 36.

 

 Последовательное улучшение производственной программы

Предположим теперь, что предприятие может выпускать четыре вида продукции, используя для этого три вида ресурсов. Известна технологическая матрица А затрат любого ресурса на единицу каждой продукции, вектор В объемов ресурсов и вектор С удельной прибыли

                      (7)

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

Математическая модель задачи:

найти производственную программу

                                (x₁, x₂, x₃, x₄)

максимизирующую прибыль

z = 36x₁+ 14x₂ + 25x₃ + 50x₄                                 (8)

при ограничениях по ресурсам

                                                (9)

где по смыслу задачи

                              x₁ ³ 0, x₂ ³ 0, x₃ ³ 0, x₄ ³ 0.                                           (10)   

Получили задачу на условный экстремум. Для ее решения систему неравенств (9) при помощи дополнительных неотрицательных неизвестных х₅, х₆, х₇ заменим системой линейных алгебраических уравнений

                             (11)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (11), удовлетворяющих условию неотрицательности

х₁³ 0, х₂³ 0, …, х₅³ 0, …, х₇³ 0.                                                       (12)

надо найти то решение, при котором функция (8) примет наибольшее значение.

Воспользуемся тем, что правые части всех уравнений системы (11) неотрицательны, а сама система имеет предпочитаемый вид – дополнительные переменные являются базисными. Приравняв к нулю свободные переменные х₁, х₂, х₃, х₄, получаем базисное неотрицательное решение

11

x₁=0, x₂=0, x₃=0, x₄=0, x₅=208, x₆=107, x₇=181                        (13)

первые четыре компоненты которого определяют производственную программу

                                  x₁=0, x₂=0, x₃=0, x₄=0                               (14)

по которой мы пока ничего не производим.

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

                                                 (15)

Мы пока сохраняем в общем решении х₁=х₂=х₃=0 и увеличиваем только х₄. При этом значения базисных переменных должны оставаться неотрицательными, что приводит к системе неравенств

или          т.е.       0 £ х₄ £

Дадим х₄ наибольшее значение х₄ =181/5, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (15). Получаем для системы уравнений (11) частное неотрицательное решение

х₁=0, х₂=0, х₃=0, х₄= ; x₅=27; x₆= ; x₇=0                                        (16)

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

 

а разрешающим элементом будет а₃₄=5. Применив известные формулы исключения, получаем для системы уравнений (11) новый предпочитаемый эквивалент

 

     x₁ + 2x₂ + 2x₃     + x₅        - x₇ = 27

  x₁ + x₂  - x₃         + x₆ - x₇ =                  (17)

                         x₁ +  x₂ + x₃ + x₄          + x₇ =

      

Приравняв к нулю свободные переменные х₁, х₂, х₃, х₇, получаем базисное неотрицательное решение, совпадающее с (16), причем первые четыре компоненты его определяют новую производственную программу

                              х₁=0, х₂=0, х₃=0, х₄= .                        (18)

12

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

Из последнего уравнения системы (17) выражаем базисную переменную х₄ через свободные и подставляем в (8). Получаем

                             (19)

 

Видим, что программа (18) не является наилучшей, так как прибыль будет расти, если мы начнем производить или первую, или вторую, или третью продукцию, но наиболее быстро функция z растет при возрастании х₁. Поэтому принимаем х₁ в системе (17) за разрешающую неизвестную, находим разрешающее уравнение по

 

                                                        (20)

и исключаем х₁ из всех уравнений системы (17), кроме первого уравнения. Получим следующий предпочитаемый эквивалент системы условий, который определит для системы (11) новое базисное неотрицательное решение и уже третью производственную программу, для исследования которого нам придется выразить функцию (19) через новые свободные переменные, удалив оттуда переменную х₁, ставшую базисной. Мы видели выше, как это делается (удаляли х₄ из (8)).

Важно обратить внимание на то, что эти удаления можно выполнить очень просто. Представим соотношение (8) в виде уравнения

-36х₁ - 14х₂ - 25х₃ - 50х₄ = 0 – z                                                       (21)

и припишем его к системе (11). Получается вспомогательная система уравнений

                         (22)

 

Напомним, что разрешающую неизвестную в системе (11) мы выбрали х₄. Этой переменной в последнем уравнении системы (22) отвечает наименьший отрицательный коэффициент D₄=-50. Затем мы нашли разрешающий элемент а₃₄=5 и исключили неизвестную х₄ из всех уравнений системы (11), кроме третьего. Далее нам пришлось х₄ исключать и из функции (8). Теперь это можно сделать очень просто, если посмотреть на систему уравнений (22). Очевидно, достаточно умножить третье уравнение системы (22) на 10 и прибавить к четвертому; получим

-6х₁ - 4х₂ - 5х₃ - 10х₄ = 1810 – z                                      (23)

Таким образом, мы преобразовывали вспомогательную систему уравнений (22) к виду

      x₁ + 2x₂ + 2x₃     + x₅        - x₇ = 27

  x₁  + x₂  - x₃         + x₆ - x₇ =                      (24)

  x₁ +  x₂ + x₃ + x₄          + x₇ =

  -6x₁ - 4x₂ - 5x₃                  +10x₇ = 1810 - z

 

13

Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент (17) системы уравнений (11) и определяют базисное неотрицательное решение (16) и производственную программу (18), а из последнего уравнения системы (24) получается выражение (19) функции цели через свободные переменные. Очевидно, если имеется хотя бы один отрицательный коэффициент D_j при какой-нибудь переменной x_j в последнем уравнении системы (24), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. С помощью (19) мы выяснили, что следует начинать производить продукцию первого вида, т.е. фактически мы нашли в последнем уравнении системы (24) наименьший отрицательный коэффициент

min(D_j< 0) = min(-6, -4, -5) = -6 = D₁                 

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

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

x₁ + 2x₂ + 2x₃      + x₅             - x₇ = 27

            3x₂  - x₃   -  x₅ + x₆ + x₇  = 13               (25)

            - x₂ - x₃ + x₄ - x₅       + x₇ = 20

             8x₂ + 7x₃     + 6x₅       + 4x₇ = 1972 - z

Первые три уравнения системы (25) представляют некоторый предпочитаемый эквивалент системы уравнений (11) и определяют базисное неотрицательное решение системы условий рассматриваемой задачи

x₁=27, x₂=0, x₃=0, x₄=20, x₅=0, x₆=13, x₇=0                       (26)

т.е. определяют производственную программу

x₁=27, x₂=0, x₃=0, x₄=20                                     (27)

и остатки ресурсов:

первого вида х₅=0

второго вида х₆=13                                                                    (28)

третьего вида х₇=0

В последнем уравнении системы (25) среди коэффициентов при неизвестных в левой части уравнения нет ни одного отрицательного. Если из этого уравнения выразить функцию цели z через остальные неотрицательные переменные

z = 1972 - 8х₂ - 7х₃ - 6х₅ - 4х₇                                                                (29)

то становится совершенно очевидным (в силу того, что все x_j³ 0), что прибыль будет наибольшей тогда, когда

x₂=0, x₃=0, x₅=0, x₇=0                                              (30)

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

z_max = 1972                                                                            (31)

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

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

14

Таблица 1

			36 14 25 50 0 0 0	Пояснения
	Базис	Н	x1    x2    x3    x4     x5    x6    x7
0	х5	208	4 3 4 5 1   0   0	z0 = H
0	х6	107	2 5 0 2  0   1   0
0	х7	181	3 1 2 5  0    0  1	0
	z0 -z	0 - z	-36 -14 -25 -50 0    0  0
0	х5	27	1 2 2 0 1     0 -1
0	х6	173/5	4/5 23/5 -4/5 0  0    1 -2/5
50	х4	181/5	3/5 1/5 2/5 1 0    0 1/5
	z0 -z	1810-z	-6 -4 -5 0 0     0 10
36	х1	27	1 2 2 0 1     0 -1
0	х6	13	0 3 -12/5 0 -4/5    1 2/5	все Dj ³ 0
50	х4	20	0 -1/5 -4/5 1 -3/5    0 4/5
	z0 -z	1972-z	0 8 7  0 6   0 4

 

где представлены расширенные матрицы вспомогательных систем уравнений       (22) ® (24) ® (25). Эти таблицы принято называть симплексными.

Следует обратить внимание на экономический смысл элементов последней строки последней симплексной таблицы. Например, коэффициент D₃=7 при переменной х₃ показывает, что если произвести одну единицу продукции третьего вида (она не входит в оптимальную производственную программу), то прибыль уменьшится на 7 единиц.

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

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

15

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

Следует при этом обратить внимание на то, что последовательное улучшение производственной программы

(x₁=0, x₄=0) ® (x₁=0, x₄= ) ® (x₁=27, x₄=20)

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

 

Двойственная задача

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

Теперь представим себе, что возникла новая ситуация. Знакомый предприниматель П (Петров), занимающийся производством каких-то других видов продукции, но с использованием трех таких же видов ресурсов, какие имеются у нас, предлагает нам " уступить" по определенным ценам все имеющиеся у нас ресурсы и обещает платить у₁ рублей за каждую единицу первого ресурса, у₂ руб – второго, у₃ руб – третьего. Возникает вопрос: при каких ценах у₁, у₂, у₃ мы можем согласиться с предложением П.

Величины у₁, у₂, у₃ принято называть расчетными, или двойственными, оценками ресурсов. Они прямо зависят от условий, в которых действует наше предприятие.

Напомним, что в нашей задаче технологическая матрица А, вектор объемов ресурсов В и вектор удельной прибыли С имели вид

Для производства единицы продукции первого вида мы должны затратить, как видно из матрицы А, 4 единицы ресурса первого вида, 2 единицы ресурса второго вида и 3 единицы третьего (элементы первого столбца матрицы). В ценах у₁, у₂, у₃ наши затраты составят 4у₁ + 2у₂ + 3у₃, т.е. столько заплатит предприниматель П за все ресурсы, идущие на производство единицы первой продукции. На рынке за единицу первой продукции мы получили бы прибыль 36 руб. Следовательно, мы можем согласиться с предложением П только в том случае, если он заплатит не меньше

4у₁ + 2у₂ + 3у₃ ³ 36.

Аналогично, во втором столбце матрицы А указаны затраты различных ресурсов на производство единицы продукции второго вида. В ценах П эти затраты составят 3у₁ + 5у₂ + у₃, а на рынке за единицу продукции второго вида мы получили бы прибыль 14 рублей. Поэтому перед предпринимателем П мы ставим условие

3у₁ + 5у₂ + у₃ ³ 14

и т.д. по всем видам продукции.

Учтем, что за все имеющиеся у нас ресурсы нам должны заплатить                        208у₁ + 107у₂ + 181у₃ рублей. При поставленных нами условиях предприниматель П будет искать такие значения величин у₁, у₂, у₃, чтобы эта сумма была как можно меньше. Подчеркнем, что здесь речь идет не о ценах, по которым мы когда-то приобретали эти ресурсы, а об этих ценах, которые существенно зависят от применяемых нами технологий, объемов ресурсов и от ситуации на рынке.

16

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

у (у₁, y₂, y₃)

минимизирующий общую оценку всех ресурсов

 

                                           f = 208y₁ + 107y₂ +181y₃                                (1)

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

 

(2)

                                   4y₁ + 2y₂ + 3y₃ ³ 36

3y₁ + 5y₂ + y₃ ³ 14

4y₁          + 2y₃ ³ 25

5y₁ + 2y₂ + 5y₃ ³ 50

 причем оценки ресурсов не могут быть отрицательными

                              y₁ 0, y₂ 0, y₃ 0.                                         (3)

Решение полученной задачи легко найти с помощью второй основной теоремы    двойственности, согласно которой для оптимальных решений (х₁, х₂, х₃, х₄) и (y₁, y₂, y₃) пары двойственных задач необходимо и достаточно выполнение условий

x ₁ (4y₁ + 2y₂ + 3y₃ - 36) = 0              y₁ (4x₁ +3x₂ + 4x₃ + 5x₄ - 208) = 0

x ₂ (3y₁ + 5y₂ + y₃ - 14) = 0              y₂ (2x₁ +5x₂           + 2x₄ - 107) = 0

x ₃ (4y₁           + 2y₃ - 25) = 0             y₃ (3x₁ + x₂ + 2x₃ + 5x₄ - 181) = 0   .

 x ₄(5y₁ + 2y₂ + 5y₃ - 50) = 0                 

Ранее было найдено, что в решении исходной задачи х₁> 0, x₄> 0. Поэтому

4y₁ + 2y₂ + 3y₃ - 36 = 0

   5y₁ + 2y₂ + 5y₃ - 50 = 0

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

у₂=0,

то приходим к системе уравнений

4y₁ + 3y₃ - 36 = 0

5y₁ + 5y₃ - 50 = 0

откуда следует

                                           у₁=6, у₃=4.

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

 

                      у₁=6; у₂=0; у₃=4,                                                        (4)

 

причем общая оценка всех ресурсов равна 1972.

17

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

 

§6. Задача о " расшивке узких мест производства"

При выполнении оптимальной производственной программы первый и третий ресурсы используются полностью, т.е. образуют ² узкие места производства². Будем их заказывать дополнительно. Пусть T(t₁, t₂, t₃)- вектор дополнительных объемов ресурсов. Так как мы будем использовать найденные двойственные оценки ресурсов, то должно выполняться условие

H + Q^-1T  0.

Задача состоит в том, чтобы найти вектор

T (t₁, 0, t₃),

максимизирующий суммарный прирост прибыли

                                                    W = 6t₁ + 4t₃                                                                        (1)

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

 

(2)

                               

предполагая, что можно  надеяться  получить дополнительно не более 1/3 первоначального объема ресурса каждого вида                                               

          (3)

причем по смыслу задачи

                      t₁  0, t₃  0. (4)                                                                            

Переписав неравенства (2) и (3) в виде:

(6)

(5)

    

 

                 

 

 

приходим к задаче ЛП: максимизировать (1) при условиях (5), (6) и (4).

Эту задачу легко решить графически: см. рис. 1. Программа ² расшивки² имеет вид

t₁= , t₂=0, t₃=

 

18

и прирост прибыли составит 519 .

 

Сводка результатов приведена в таблице

                                                                  

 Таблица 1

сj	36	14	25	50	b	x4+i	yi	ti
	4	3	4	5	208	0	6	46 5/12
aij	2	5	0	2	107	13	0	0
	3	1	2	5	181	0	4	60 1/3
xj	27	0	0	20	1972			519 2/3
Dj	0	8	7	0

 

12345Следующая ⇒

Поделиться: