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

 

 

 

 

 

 

Оглавление

ДАННЫЕ  ИНДИВИДУАЛЬНОГО ЗАДАНИЯ

Вариант № 14

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

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

 

В индивидуальном задании  матрицы компактно записаны в виде:

                                              

С1	С2	С3	С4			27	39	18	20
a11	a12	a13	a14	B1		2	1	6	5	140
a21	a22	a23	a24	B2		0	3	0	4	90
a31	a32	a33	a34	B3		3	2	4	0	198

         

        2  1  6  5                              140

А=   0  3  0  4                       В =  90            С= 27, 39, 18, 20                   (1)

        3  2  4  0                              198

 

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

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

Найти производственную программу (х₁, х₂, х₃, х₄),

максимизирующую прибыль z=27x₁+39x₂+18x₃+20х₄                                    (2)

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

            2x₁ + x₂ + 6x₃ + 5x₄  £ 140

                 3x₂              + 4x₄  £ 90 , (3)

            3x₁ +2x₂ +4x₃           £ 198

 

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

x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, x₄ ≥ 0 .                                                                        (4)

(2)-(4)- математическая модель линейной производственной задачи:

(2) - целевая функция;

(3) - линейные ограничения задачи (ограничения по ресурсам);

(4) - условие не отрицательности  задачи.

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

2x₁ + x₂ + 6x₃ + 5x₄ + x₅                  = 140

        3x₂ +          4x₄         + x₆          = 90 , (5)

3x₁+ 2x₂ + 4x₃                          + x₇  = 198

где дополнительные переменные имеют  смысл остатков соответствующих  ресурсов.

х₅ - остаток 1-го ресурса;

х₆ - остаток 2-го ресурса;

х₇ - остаток 3-го ресурса.

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

       x_i ³0 , i=1...7 ,  (6)

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

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

х₁= 0, х₂= 0, х₃= 0, х₄ = 0, х₅= 140, х₆= 90, х₇= 198 (7)

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

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

х₅= 140 - 2x₁ - x₂  - 6x₃ - 5x₄

х₆= 90 -          3x₂ -        4x₄                                                                                                                  (8)

х₇= 198 - 3x₁ -2x₂ - 4x₃

 

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

140 - x₂  ≥ 0                    x₂ ≤ 140

90   -3x₂ ≥ 0        или      x₂ ≤ 30 ,             т.е. 0 ≤ x₂ ≤ 30

198 -2x₂ ≥ 0         x₂ ≤ 99

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

х₅= 140 - 2x₁ -   30  - 6x₃ - 5x₄

х₆= 90 -             90 -          4x₄                                                                                                                 

х₇= 198 - 3x₁ –  60 - 4x₃

х₁= 0, х₂= 30, х₃= 0, х₄ = 0, х₅= 110, х₆= 0, х₇= 138                                  (9)

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

min = min (140; 30; 99) = 30,

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

 

2x₁ +            6x₃ + x₄ + х₅ + х₆           = 110

         х₂  +          x₄ +        х₆           = 30                                                     (10)

3 х₁ +          4x₃   -  x₄             - х₆ + х₇ = 138

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

х₁= 0, х₂= 30, х₃= 0, х₄ = 0.   (11)

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

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

z=27x₁+39(30 - x₄ - х₆) +18x₃+20х₄

z=1170 + 27 x₁+18x₃ - 32х₄ - 13х₆                                                                                                  (12) 

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

min( ; ; )=min(55; -; 46)= 46                                                         (13)

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

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

- 27x₁ - 39x₂ - 18x₃ - 20х₄ =0 - z           (14)

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

    2x₁ + x₂   + 6x₃ + 5x₄ + x₅                 = 140

             3x₂ +           4x₄         + x₆          = 90  (15)

    3x₁+ 2x₂ +  4x₃                          + x₇ = 198

- 27x₁ - 39x₂ - 18x₃ - 20х₄                                  =0 - z

Напомним, что разрешающую неизвестную в системе (5) мы брали x₂. Этой переменной в последнем уравнении системы (15) отвечает наименьший отрицательный коэффициент ₄= - 39. Затем мы нашли разрешающий элемент a₂₂=3 и исключили неизвестную x₂ из всех уравнений системы (5), кроме второго. Далее нам пришлось x2 исключать из функции (2). Теперь это можно сделать очень просто, если посмотреть на систему уравнений (15). Очевидно, достаточно умножить второе уравнение на 13 и прибавить к четвертому; получим

-27 x₁ - 18x₃  + 32х₄ + 13х₆= 1170 – z                                                            (16)

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

2x₁ +            6x₃ + x₄ + х₅ + х₆           = 110

         х₂  +          x₄ +        х₆           = 30                                                     (17)

3 х₁ +          4x₃   -  x₄             - х₆ + х₇ = 138

-27x₁ -     18x₃  + 32х₄ +     13х₆             = 1170 – z            

Первые три уравнения этой системы  представляют некоторый предпочитаемый эквивалент (10) системы уравнений (5) и определяют базисное неотрицательное  решение (9) и производственную программу (11), а из последнего уравнения системы (17) получается выражение (12) функции цели через свободные переменные. Очевидно, если имеется хотя бы один отрицательный коэффициент  j при какой-нибудь переменной хj  в последнем уравнении системы (17), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. С помощью (12) мы выяснили, что следует начинать производить продукцию первого вида, т.е. фактически мы нашли в последнем уравнении системы (17) наименьший отрицательный коэффициент

min( j < 0)=min( -18; -27)= -27= 1

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

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

                     x₃ + x₄ + х₅+ х₆  - х₇ = 18

       х₂ +                  x₄             + х₆                 = 30

x₁ +            x₃   - x₄               - х₆ + х₇ =46                                                 (18)

 

             18x₃  + 8х₄ +          7х₆  + 9 х₇  = 2412 - z

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

х₁= 46, х₂= 30, х₃= 0, х₄ = 0, х₅= 18, х₆= 0, х₇= 0                                      (19) 

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

        х₁= 46, х₂= 30, х₃= 0, х₄ = 0                                                                (20)  

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

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

второго вида   х₆= 0                 (21)

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

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

Z=2412 - 18x₃  - 8х₄ - 7х₆  - 9 х₇ ,                                                                                                       (22)