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

Условия задачи:

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

Известны технологическая матрица

А=

затрат ресурсов на производство единицы каждого вида продукции [элемент aij этой матрицы равен количеству ресурса i-го вида (i = 1, 2, 3), которое необходимо затратить в процессе производства единицы продукции j-го вида (j = 1, 2, 3, 4)],

вектор

Объем ресурсов и вектор

удельной прибыли на единицу продукции.

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

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

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

Решение:

1. Формулирование экономико-математическая модели:

Исходя из условий и исходных данных экономико-математическая модель задачи примет вид: найти такой план Х(х1,х2,х3,х4) выпуска продукции удовлетворяющей системе по ограничению ресурсов:

и условию х1≥0,х2≥0,х3≥0,х4≥0,

при котором функция z=60x₁+12x₂+44x₃+17x₄ (2)

принимает максимальное значение.

Или другими словами, найти производственную программу Х(х1,х2,х3,х4) выпуска продукции максимизирующую прибыль:z=60x₁+12x₂+44x₃+17x₄ при ограничениях по ресурсам:

Для решения задачи приведем систему (1) к каноническому виду, для этого введем в систему уравнений дополнительные неотрицательные неизвестные: х₅≥0, х₆≥0, х₇≥0– остаток ресурса определенного вида (неиспользуемое количество каждого ресурса).

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

где среди всех решений, удовлетворяющих условию неотрицательности: х₁≥0, х₂≥0, х₃≥0, х₄≥0, х₅≥0, х₆≥0, х₇≥0.

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

Эту задачу будем решать методом последовательного улучшения плана – симплексным методом.

2. Решение задачи симплексным методом.

2.1. Находим первое базисное решение

Воспользуемся тем, что правые части всех уравнений системы (3) неотрицательны, а сама система имеет такой вид, что дополнительные переменные являются базисными. Приравняв к нулю свободные переменные x1, x2, x3, x4, получаем базисное неотрицательное решение: х₁=0, х₂=0, х₃=0, х₄=0, х₅=180, х₆=160, х₇=109.

Исходная симплексная таблица

1ё	Базис	H								Пояснения
с			х1	х2	х3	х4	х5	х6	х7
	х5
	х6
	х7									54,5
			-60	-12	-44	-17

На данной итерации:

- признак несовместности системы ограничений (признак 1) не выявлен (т.е. нет строки с отрицательным свободным числом (кроме строки целевой функции), в которой не было бы хотя бы одного отрицательного элемента (т.е. отрицательного коэффициента при свободной переменной)).

- признак неограниченности целевой функции (признак 2) не выявлен (т.е. нет колонки с отрицательным элементом в строке целевой функции (кроме колонки свободных чисел), в которой не было бы хотя бы одного положительного элемента).

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

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

2.2. Определение разрешающего элемента.

2.2.1. Определение разрешающей колонки.

Определяем колонки с отрицательными элементами в строке целевой функции (кроме колонки свободных чисел). Из таких колонок выбирается та, которая содержит наименьший элемент в строке целевой функции. Она и будет разрешающей. Колонка «х1» содержит наименьший элемент (–60) в сравнении с другими колонками. Следовательно, ее принимаем в качестве разрешенной.

2.2.2 определение разрешающей строки

Для определения разрешающей строки находим положительные оценочные отношения свободных чисел к элементам разрешающей колонки, строка, которой соответствует наименьшее положительное оценочное отношение, принимается в качестве разрешенной. В нашем случае, наименьшее положительное оценочное отношение 40 соответствует строке «х6», следовательно, она будет разрешающей.

2.2.3. определение разрешающего элемента

Элемент, расположенный на пересечение разрешающей колонки и разрешающей строки, принимается в качестве разрешающего. В нашем примере – это элемент а₂₁=4, который расположен на пересечении строки «х6» и колонки «х1».

Разрешающий элемент показывает одну базисную и одну свободную переменные, которые необходимо поменять местами в симплекс-таблице, для перехода к новому «улучшенному» базисному решению. В данном случае это переменные х6 и х1, в новой симплекс-таблице их меняем местами

2.3. Преобразование исходной симплексной таблицы

Элементы разрешающей строки исходной таблицы делим на разрешающий элемент данной симплекс-таблицы, результаты вписываются в аналогичные ячейки новой симплекс-таблицы (итерация2). Преобразование остальных элементов симплекс-таблицы (т.е. элементов не расположенных в разрешающей строке и разрешающей колонке) осуществляется по правилу «прямоугольника».

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

В результате данных преобразований получили новую симплекс- таблицу(итерация2).

Итерация2.

	Базис	H								Пояснения
			х6	х2	х3	х4	х5	х6	х7
	х5			2,00		-1	1,00	-1
	х1				0,5	0,5		0,25
	х7			4,0		-1	0,0	-0,5		14,5
				-12	-14

В результате проведенных симплекс-преобразований получили новое базисное решение Х(х1,х2,х3,х4,х5,х6,х7)=(40,0,0,0,20,0,29). При данном базисном решении значение целевой функции z=2400, что больше чем при предыдущем базисном решении.

Не совместность системы ограничений в соответствии с признаком 1 в таблице 5.5 не выявлена.

Неограниченность целевой функции в соответствии с признаком 2 в таблице 5.5 не выявлена.

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

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

 

Итерация3.

	Базис	H								Пояснения
			х1	х2	х5	х4	х5	х6	х7
	х3			1,00		-0,5	0,50	-0,5
	х1			-0,5		0,75	-0,25	0,5
	х7			2,0			-1,0	0,5

В результате проведенных симплекс-преобразований получили новое базисное решение Х(х1,х2,х3,х4,х5,х6,х7)=(35,0,10,0,0,0,9). При данном базисном решении значение целевой функции z=2540, что больше чем при предыдущем базисном решении.

Не совместность системы ограничений в соответствии с признаком 1 в таблице не выявлена.

Неограниченность целевой функции в соответствии с признаком 2 в таблице не выявлена.

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

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

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

Таким образом, получили производственную программу: х1=35, х2=0, х3=10, х4=0, которая является оптимальной и обеспечивает предприятию наибольшую возможную прибыль: z=60x₁+12x₂+44x₃+17x₄=60*35+12*0+44*10+17*0=2100+0+440+0=2540.

При этом первый и второй ресурсы будут использованы полностью, т. е. первый и второй ресурсы образуют «узкие места производства»: х5=0,х6=0, а третий ресурс будет иметь остаток: х7=9.

Оптимальное значение целевой функции (максимальная прибыль предприятия) рассматриваемой задачи z=2540, которое достигается при производственной программе Х(35,0,10,0,0,0,9).

3. Решение двойственной задачи

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

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

Предположим, некий предприниматель, занимающийся производством других видов продукции с использованием трех таких же видов ресурсов, предлагает «уступить» ему все имеющиеся ресурсы и обещает платить y1 денежных единиц за каждую единицу первого ресурса, y2 денежных единиц за каждую единицу второго ресурса и y3 денежных единиц за каждую единицу третьего ресурса. Возникает вопрос, при каких значениях y1, y2, y3 можно согласиться с предложением этого предпринимателя.

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

А=

 

Значит, для производства, например, первого вида продукции, предприятие должно затратить 4 единицы ресурса первого вида, 4 единицы ресурса второго вида и 2 единицы ресурса третьего вида, за что оно получит прибыль 60 денежных единиц. Следовательно, согласиться с предложением предпринимателя можно, если он заплатит не меньше, т. е. в ценах y1, y2, y3 это условие будет иметь вид:

4у1+4у2+2у3≥60

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

180у1+160у2+109у3 денежных единиц.

Следовательно, предприниматель будет искать такие значения y1, y2, y3, при которых эта сумма была бы как можно меньше. При этом речь идет о ценах, которые зависят не от цен, по которым эти ресурсы были когда-то приобретены, а о ценах зависящих от применяемых в производстве технологий, объемов ресурсов и прибыли, которую возможно получить за произведенную продукцию.

Таким образом, задача определения расчетных оценок ресурсов приводит к задаче линейного программирования: найти вектор двойственных оценок y(y_1,y₂,y₃), минимизирующий общую оценку всех ресурсов f=180y1+160y2+109y3.

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

Причем оценки ресурсов не могут быть отрицательными, т. е.:y₁≥0 , y₂≥0,y₃≥0, .

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

Т. е. для оптимальных решений x(x₁, x_2,… x_n)и y(y₁,y₂,y₃) пары двойственных задач необходимо и достаточно выполнение условий:

 

 

Ранее в предыдущем пункте было определено, что x₁>0, x₂>0,x₃>0, a x₄=0 и x₂=0, тогда

Но т. к. третий ресурс был избыточным, то по второй теореме двойственности, его двойственная оценка равна нулю, т. е.y₃=0 . Тогда переходим к новой системе уравнений:

4у1+4у2-60=0 28+35-60=0

4у1+2у2-44=0 4*7+2*8-44=0

Откуда получаем y₁=7, у₂=8

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

Тогда общая оценка всех ресурсов равна:

F=180y₁+160y₂+109y₃=180*7+160*8+0=1260+1280=2540

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

y₁=7– показывает, что добавление одной единицы первого ресурса обеспечит прирост прибыли в 7 денежных единиц; y₂=8– показывает, что добавление одной единицы второго ресурса обеспечит прирост прибыли в 8 денежные единицы.

Одновременно технологические оценки из той же строки симплексной таблицы:

∆₂=2– показывает, что если произвести одну единицу продукции второго вида (не входящую в оптимальную производственную программу), то это уменьшит прибыль на 7 денежных единиц;∆₄=6– показывает, что если увеличить выпуск продукции четвертого вида на одну единицу, то это уменьшит прибыль на 9 денежных единиц.

Ответ:

1.Максимальная прибыль предприятия рассматриваемой задачи составляет z=2540, которое достигается при производственной программе Х(35,0,10,0,0,0,9). При этом первый и второй ресурсы будут использованы полностью, т. е. первый и второй ресурсы образуют «узкие места производства»: х₅=0,х₆=0, а третий ресурс будет иметь остаток: х7=9.

2. двойственные оценки ресурсов составляют: у₁=7, у₂=8, у₃=0, что говорит о том, что добавление одной единицы первого ресурса обеспечит прирост прибыли в 7 денежных единиц, а добавление одной единицы второго ресурса обеспечит прирост прибыли в 8 денежные единицы.

 

Транспортная задача

Условие задачи:

Однородный продукт, сосредоточенный на трех складах фирмы в количествах a₁, a₂, a₃ (55, 60, 48) единиц, необходимо распределить между четырьмя магазинами, которым необходимо соответственно b₁, b₂, b₃, b₄ единиц продукта. Стоимость перевозки единицы продукта из i-го пункта отправления (i = 1, 2, 3) в j-й пункт назначения (j = 1, 2, 3, 4) равна cij и известна для всех маршрутов.

Вектор запаса продуктов на складах

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

=(36 44 25 50)

и матрица транспортных тарифов известны

c=

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

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

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

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

Решение:

1. Исходя из условий задачи, каждый поставщик должен дать ровно столько продукции, столько у него есть, а каждый потребитель должен получить ровно столько продукции, сколько ему требуется, т.е. ∑а_i=∑b_i. В случае ∑а_i≠∑b_i, то транспортная задача линейного программирования называется открытой.

Общий объем продукта в нашей задаче в пунктах производства равен:

∑а_i=55+60+48=163,

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

∑b_i=36+44+25+50=155

Т. е. имеем открытую модель транспортной задачи. ∑а_i=163>∑b_i=155.

Для того, чтобы превратить открытую модель транспортной задачи в закрытую, необходимо ввести фиктивный пункт потребления с объемом потребления

∑а_i-∑b_i=163-155=8 -единиц,

При этом тарифы на перевозку продукта в этот пункт потребления будут равны нулю, т. к. фактического перемещения продукта не происходит.

2. Экономико-мате­ма­тическая модель транспортной задачи представляется обычно в виде транспортной таблицы или матрицы.

Исходная транспортная матрица

	В1	В2	В3	В4	В5
А1			4		3		4		5		0
А2			8		5		3		2		0
А3			9		8		2		5		0

3. Построение опорного плана

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

Для построения опорного плана используем метод северо-западного угла:

 

	В1	В2	В3	В4	В5
А1			4		3		4		5		0
А2			8		5		3		2		0
А3			9		8		2		5		0

F=36*4+19*3+25*5+25*3+0*2+10*2+40*5+8*0=621

После расстановки корреспонденции матрица проверяется на вырождение, т. е. должно выполняться условие m+n-1=N _баз,

 

где m – количество строк, n – количество столбцов, N_баз – количество базисных клеток.

Другими словами, количество клеток матрицы, содержащих корреспонденции, должно быть равно сумме строк и столбцов без единицы. В нашем случае это условие соблюдается: 7 = 5 + 3 – 1. План транспортной задачи, отвечающий условию (n + m – 1) называют базисным. Базисными также называются клетки матрицы, содержащие поставки. Клетки, в которых поставки отсутствуют, называются небазисными.

Построим первое базисное допустимое решение по правилу наименьшего элемента в матрице:

	В1	В2	В3	В4	В5
А1			4		3		4		5		0
А2			8		5		3		2		0
А3			9		8		2		5		0

F=11*4+10*8+15*9+44*3+25*2+50*2+8*0=541ткм

Проверяем матрицу на вырождение: 7=5+3-1- условие выполняется, при чем грузооборот или функционал транспортной задачи вычисленный по правилу наименьшего элемента в матрице меньше, чем вычисленный по правилу северо-западного угла. Поэтому принимаем в качестве базисного решения: решение вычисленное по правилу наименьшего элемента в матрице.

4. Проверка плана на оптимальность.

4.1. Расчет потенциалов.

Потенциалы – это такие числа, которые по определенным правилам назначаются каждой строке и каждому столбцу. Потенциалы строк обозначим u_i, потенциалы столбцов – v_j. Они могут принимать любые значения.

Выбираем базисную клетку с максимальным расстоянием. В нашей матрице это клетка А₃В₁. Присвоим строке, в которой находится эта клетка, потенциал, равный 0 (u₃ = 0). Далее можно рассчитать потенциалы столбцов по базисным клеткам строки 3 по формуле: v_j=u_i+c_ij

Потенциал первого столбца v₁ = u₃ + c₃₁ = 0 + 9 = 9;

третьего: v₃ = u₂ + c₂₃ = 0 + 2 = 2;

пятого: v₅ = u₂ + c₂₅ = 0 + 0 =0.

Рассчитанные потенциалы записываем напротив соответствующих столбцов ниже матрицы. Поскольку по всем базисным клеткам строки 3 потенциалы столбов найдены, переходим к расчету потенциалов строк.

Потенциал строки 1 рассчитываем по найденному потенциалу столбца 1 и базисной клетке А₁В₁ по формуле u_i = v_j -c_ij,

Где u₁ = v₁ – c₁₁ = 9 –4 = 5.

Для строки 2 потенциал будет равен:

u₂ = v₁ – c₂₁ = 9 – 8 = 1.

Также рассчитываем потенциалы для всех строк и столбцов.