ЛИНЕЙНАЯ ПРОИЗВОДСТВЕННАЯ ЗАДАЧА

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

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

(1)

Требуется составить производственную программу (x₁, x₂, x₃, x₄), максимизирующую прибыль

(2)

при ограничениях по ресурсам: (3)

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

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

уравнений (5)

где дополнительные переменные имеют смысл остатков соответствующих ресурсов. Среди всех решений системы уравнений (5), удовлетворяющих условию неотрицательности х₁³0, х₂³0,… ,х₅³0,…, х₇³0. (6)

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

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

x₁=0, x₂=0, x₃=0, x₄=0, x₅=103, x₆=148, x₇=158 (7)

первые четыре компоненты которого определяют производственную программу x₁=0, x₂=0, x₃=0, x₄=0(8)

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

(9)

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

или т.е. 0 £ х₁£ 37

Дадим х₁ наибольшее значение х₁=37, которое она может принять при нулевых значениях других свободных неизвестных, и подставим его в (9). Получаем для системы уравнений (5) частное неотрицательное решение х₁=37, х₂=0, х₃=0, х₄=0; x₅=29; x₆=0; x₇=84 (10)

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

, а разрешающим элементом будет а₂₁=4.

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

36 32 10 13 0 0 0

Базис

x₁ x₂ x₃ x₄ x₅ x₆ x₇

Пояснения

Х₅

103

2 3 4 1 1 0 0

z₀ =

Х₆

148

4 2 0 2 0 1 0

Х₇

158

2 8 7 0 0 0 1

z₀ -z

0 - z

-36 -32 -10 -13 0 0 0

Х₅

0 2 4 0 1 -1/2 0

Х₁

1 1/2 0 1/2 0 ј 0

Х₇

0 7 7 -1 0 -1/2 1

min (29/2; 64;12)=12

z₀ -z

1332-z

0 -14 -10 5 0 9 0

min (-14;-10) = -14

Х₅

0 0 2 2/7 1 -5/14 -2/7

Х₁

1 0 -1/2 4/7 0 2/7 -1/14

Х₂

0 1 1 -1/7 0 -1/14 1/7

z₀ -z

1500-z

0 0 4 3 0 8 2

все D_j³0

Применим известные формулы исключения

a`_ij=a_ij – (a_is/a_rs)*a_rj

a`_iq=a_iq – (a_is/a_rs)*a_rq

b`_i=b_i - (a_is/a_rs)*b_r

b`_r=b_r/a_rs

s=1, r=2

a`₁₂=3-2/4 *2= 2

a`₁₃=4

a`₁₄=1-2/4 *2=0

a`₁₅=1

a`₁₆=0-2/4*1= -2/4

a`₁₇=0

a`₃₂=8-2/4* 2= 7

a`₃₃=7

a`₃₄=0-2/4* 2= -1

a`₃₅= 0

a`₃₆=0-2/4 *1= -2/4

a`₃₇=1

a`₂₁=a₂₁/a₂₁=1

a`₂₂=a₂₂/a₂₁=1/2

a`₂₃=0

a`₂₄=1/2

a`₂₅=0

a`₂₆=1/4

a`₂₇=0

a`₄₁= 0

a`₄₂= -14

a`₄₃= -10

a`₄₄=5

a`₄₅=0

a`₄₆=9

a`₄₇=0

a`₁₁=a`₃₁=0

b`₁=103-148/4*2=29

b`₂=148/4=37

b`₃=158-148/4*2=84

Получаем для системы уравнений (5) новый предпочитаемый эквивалент

2x₂ + 4x₃ + x₅ - 1/2x₆ = 29

x₁ + 1/2x₂ + 1/2x₄ + 1/4x₆ = 37 (11)

7x₂+ 7x₃- x₄-1/2x₆+ x₇= 84

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

Представим соотношение (2) в виде уравнения -36х₁ - 14х₂ - 10х₃ - 13х₄ = 0 – z (13)

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

(14)

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

-14х₂ - 10х₃ + 5х₄ - 9х₆ = 1332 – z (15)

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

(16)

Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент (11) системы уравнений (5) и определяют базисное неотрицательное решение (10) и производственную программу (12), а из последнего уравнения системы (16) получается выражение функции цели через свободные переменные. Получим следующий предпочитаемый эквивалент системы условий, который определит для системы (5) новое базисное неотрицательное решение и уже третью производственную программу, для исследования которого нам придется выразить функцию z=1332+14x₂+10x₃-5x₄-9x₆ через новые свободные переменные, удалив оттуда переменную х₂, ставшую базисной.

Очевидно, если имеется хотя бы один отрицательный коэффициент Dj при какой-нибудь переменной x_j в последнем уравнении системы (16), то производственная программа не является наилучшей и можно далее продолжать процесс ее улучшения. Мы нашли в последнем уравнении системы (16) наименьший отрицательный коэффициент min(Dj<0) = min(-14,-10) = -14 = D_2. Поэтому принимаем х₂ в системе (11) за разрешающую неизвестную, находим разрешающее уравнение по (17)

и исключаем х₂ из всех уравнений системы (11), кроме третьего уравнения. Укажем разрешающий элемент а₃₂=7.

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

a`_ij=a_ij – (a_is/a_rs)*a_rj

a`_iq=a_iq – (a_is/a_rs)*a_rq

b`_i=b_i - (a_is/a_rs)*b_r

b`_r=b_r/a_rs

s=1, r=2

a`₁₁=0

a`₁₃=4-2/7*7=2

a`₁₄=0+2/7 *1=2/7

a`₁₅=1

a`₁₆= -5/14

a`₁₇=0-2/7*1=-2/7

a`₂₁=1

a`₂₃= -1/2

a`₂₄=4/7

a`₂₅=0

a`₂₆=2/7

a`₂₇= -1/14

a`₃₁= a₃₁/a₃₂=0

a`₃₂=1

a`₃₃= a₃₃/a₃₂=1

a`₃₄= -1/7

a`₃₅= 0

a`₃₆=-1/14

a`₃₇=1/7

a`₄₁= 0

a`₄₂= -14+2*7=0

a`₄₃= 4

a`₄₄=3

a`₄₅=0

a`₄₆=8

a`₄₇=2

a`₁₂=a`₂₂=0

b`₁=29-84/7*2=5

b`₂=37-84/7*1/2=31

b`₃=84/7=12

Эта система преобразуется к виду

2 x₃ + 2/7 x₄ + x₅ – 5/14 x₆ – 2/7 x₇ = 5

x₁ - Ѕ x₃ + x₄ + 2/7 x₆ – 1/14 x₇ = 31 (18)

x₂ + x₃ - 1/7 x₄ – 1/14 x₆ + 1/7 x₇ = 12

4 x₃ + 3 x₄ + 8 x₆ + 2 x₇ = 1500 - z

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

x₁=37, x₂=0, x₃=0, x₄=0, x₅=29, x₆=0, x₇=84 (19)

т.е. определяют производственную программу x₁=37, x₂=0, x₃=0, x₄=0 (20)

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

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

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

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

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

z = 1500 - 4 x₃ - 3 x₄ - 8 x₆ - 2x₇ (22)

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

x₃=0, x₄=0, x₆=0, x₇=0 (23)

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

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

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

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

Следует при этом обратить внимание на то, что последовательное улучшение производственной программы (x₁=0, x₂=0) ® (x₁=37, x₂=0) ® (x₁=31, x₂=12) на графике означает движение от одной вершины многогранника допустимых решений к другой вершине по связывающей их стороне многоугольника.

ДВОЙСТВЕННАЯ ЗАДАЧА

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

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

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

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

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

Аналогично, для трех оставшихся видов продукции:

3у₁+ 2у₂+ 8у₃³32

4у₁+ 7у₃³10

у₁+ 2у₂ ³13

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

Таким образом, проблема определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок у(у₁, y₂, y₃) минимизирующий общую оценку всех ресурсов f = 103у₁+ 148у₂+ 158у₃(1)

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

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

3у₁+ 2у₂+ 8у₃³32 (2)

4у₁+ 7у₃³10

у₁+ 2у₂ ³13

причем оценки ресурсов не могут быть отрицательными y₁ 0, y₂ 0, y₃ 0. (3)

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

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

x ₂ (3у₁+ 2у₂+ 8у₃- 32) = 0 y₂ (4x₁ +2x₂ + 2x₄- 148) = 0

x ₃(4у₁+ 7у₃- 10) = 0 y₃ (2x₁ +8x₂+ 7x₃- 158) = 0 .

x ₄(у₁+ 2у₂ - 13) = 0

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

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

3y₁+ 2y₂+ 8y₃- 32 = 0

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

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

4y₂+ 2y₃ - 36 = 0

2y₂+ 8y₃- 32 = 0

откуда следует у₂=8, у₃=2.

Таким образом, получили двойственные оценки ресурсов у₁=0; у₂=8; у₃=2, (4)

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

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

ЗАДАЧА О "РАСШИВКЕ УЗКИХ МЕСТ ПРОИЗВОДСТВА"

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

Задача состоит в том, чтобы найти вектор T (0, t₂, t₃), максимизирующий суммарный прирост прибыли W = 8t₂ + 2t₃ (1) при условии сохранения двойственных оценок ресурсов (и, следовательно, структуры производственной программы)

(2)