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

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

Имя

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

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

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

(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₅=142, x₆=100, x₇=122 (7)

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

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

(9)

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

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

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

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

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

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

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

~ С			34 20 8 23 0 0 0
~ С	Базис	Н	x₁ x₂ x₃ x₄ x₅ x₆ x₇	Пояснения
0	Х₅	142	2 0 2 3 1 0 0	z₀ = H
0	Х₆	100	1 5 4 2 0 1 0
0	Х₇	122	3 4 0 1 0 0 1
	z₀ -z	0 - z	-34 -20 -8 -50 0 0 0
0	Х₅		0 -8/3 2 7/3 1 0 -2/3	min (26; 35,6;122)=26
0	Х₆		0 11/3 4 5/3 0 1 -1/3
34	Х₁		1 4/3 0 1/3 0 0 1/3
	z₀ -z	4148/3-z	0 76/3 -8 -35/3 0 0 34/3
23	Х₄	26	0 -8/7 6/7 1 3/7 0 -2/7
0	Х₆	16	0 39/7 18/7 0 -5/7 1 1/7
34	Х₁	32	1 12/7 -2/7 0 -1/7 0 3/7
	z₀ -z	1686-z	0 12 2 0 5 0 8	все D_j³0

Используя формулы исключения получаем для системы уравнений (5) новый предпочитаемый эквивалент и новую вспомогательную систему:

(11)

Первые три уравнения этой системы представляют некоторый предпочитаемый эквивалент системы уравнений (5) и определяют базисное неотрицательное решение (10) и производственную программу х₁= , х₂=0, х₃=0, х₄=0, а из последнего уравнения системы (11) получается выражение функции цели через свободные переменные:

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

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

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

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

(13)

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

x₁=32, x₂=0, x₃=0, x₄=26, x₅=0, x₆=16, x₇=0 (14)

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

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

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

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

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

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

z = 1686 - - 2x₃ - 5x₅ - 8 x₇ (17)

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

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

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

Проверим соотношение H=Q^-1B

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

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

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

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

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

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

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

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

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

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

+ 5у₂+ 4у₃³20

2у₁+ 4у₂ ³8

3у₁+ 2у₂+ 1у₃³23

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

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

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

2у₁+ 1у₂+ 3у₃³ 34

+ 5у₂+ 4у₃³ 20 (2)

2у₁+ 4у₂ ³ 8

3у₁+ 2у₂+ 1у₃³ 23

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

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

x ₁ (2у₁+ у₂+ 3у₃- 34) = 0 y₁ (2x₁ + 2x₃+ 3x₄- 142) = 0

x ₂ ( 5у₂+ 4у₃- 20) = 0 y₂ ( x₁ +5x₂+ 4x₃+ 2x₄- 100) = 0

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

x ₄(3у₁+ 2у₂+ у₃ - 23) = 0

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

2y₁+ y₂+ 3y₃ - 34 = 0

3y₁+ 2y₂+ y₃- 23 = 0

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

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

2y₁+ 3y₃ - 34 = 0

3y₁+ y₃- 23 = 0

откуда следует у₁=5, у₃=8.

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

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

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

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

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

H + Q^-1T 0.

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

(2)