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

 

 

 

               

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

 

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

Предположим, что предприятие или цех выпускает 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)

 

Удельные прибыли

Норма расхода

Запасы ресурсов

Заданы  удельные прибыли, нормы расхода  и запасы ресурсов и компьютер  решает поставленную задачу симплекс-методом.

 

26	35	18	30
2	5	1	4	126
3	0	7	2	84
2	1	4	0	75

 

  (4), (5), (6)

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

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

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

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

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

 

                       Z = 26∙x₁+35∙x₂+18∙x₃+30∙x₄→max      (8)

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

 

2∙x₁+5∙x₂+1∙x₃+4∙x₄≤126

                                3∙x₁+0∙x₂+7∙x₃+2∙x₄≤84

                              2∙x₁+1∙x₂+4∙x₃+0∙x₄≤75                       (9)

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

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

 

 

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

 

Z=26∙x₁+35∙x₂+18∙x₃+30∙x₄+0∙x₅+0∙x₆+0∙x₇→max

2∙x₁+5∙x₂+1∙x₃+4∙x₄+1∙x₅=126

3∙x₁+0∙x₂+7∙x₃+2∙x₄+      1∙x6=84                  (11)

2∙x₁+1∙x₂+4∙x₃+0∙x₄+            1∙x7=75

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

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

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

 

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

11

     x₁=0, x₂=0, x₃=0, x₄=0, x₅=126, x₆=84, x₇=75   (13)

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

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

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

 

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

 

     (15)

 

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

    или             т.е.  х₂ £ 126/5

 

 

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

х₁=0, х₂=126/5, х₃=0, х₄=0; x₅=0 ; x₆=84; x₇= 249/5  (16)

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

 

 

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

          2/5x₁      +   x₂   + 1/5x₃ + 4/5x4  + 1/5x₅ = 126/5

       3x₁ + 7x₃ +2x4 + x₆ = 84                                           (17)

           8/5x₁  +  19/5x₃ – 4/5x₄ -1/5x5 +x7 = 249/5

      

 

 

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

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

1

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

 

             (19)

 

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

 

       (20)

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

 

 

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

-26∙x₁-35∙x₂-18∙x₃-30∙x₄= 0 – z      (21)

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

2x₁+5x₂+x₃+4x₄ + x5=126

                                3x₁+7x₃+2x₄ + x6=84

                2x₁+x₂+4x₃ + x7=75

 

                -26x₁-35x₂-18x₃-30x₄= 0 – z  (22)

 

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

-12х₁ - 11х₃ – 2x4 + 7х₅ = 882 – z     (23)

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

    2/5x₁      +   x₂   + 1/5x₃ + 4/5x4  + 1/5x₅ = 126/5

    

    3x₁ + 7x₃ +2x4 + x₆ = 84                                          

                                                                            (24)

    8/5x₁  +  19/5x₃ – 4/5x₄ -1/5x5 +x7 = 249/5

     

     -12x₁   -   11x₃  - 2x4  + 7x₅ = 882 - z

 

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

min(D_j<0) = min(-12, -11, -2) = -12 = D₁  

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

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

  x₂  -  11/5x₃ + 8/15 x4  + 1/5x₅   - 2/5 x₆  = 14

                x1 +  7/3x₂ + 2/3x_{3      +} 1/3 x₆  + x₇ = 13                    (25)