Содержание. 1. Задача об использовании ресурсов. 2

ТДКС - 2

БРЯНСК - 2015.

1. Задача об использовании ресурсов ……………….……..….2

2. Транспортная задача ………………………………………..11

1 Задача об использовании ресурсов (задача планирования производства).

Предприятие выпускает три вида продукции А, В, С, используя три вида ресурсов R₁, R₂, R₃.

Известны удельные затраты ресурсов, их запасы и прибыль, полученная от реализации единицы продукции.

Необходимо:

а) составить математическую модель задачи;

б) построить математическую модель двойственной задачи;

в) решить исходную задачу и выписать решение двойственной;

г) на основании свойств двойственных оценок оптимального плана провести экономико-математический анализ.

Ресурсы	А	В	С	Запасы
R1
R2
R3
Прибыль

Построим математическую модель данной задачи.

Обозначим через х₁ искомый выпуск изделий А, через х₂ – изделий В, через х₃ – изделий С. Так как на сырье каждого вида имеются нормы затрат, тогда мы можем найти общий объем затрат сырья каждого вида для изготовления всех изделий.

Из таблицы следует, что общий объем сырья R₁ составит 7х₁+10х₂+4х₃, R₂ – 8х₁+10х₂+5х₃, R₃ – 9х₁+5х₂+10х₃. А так как на фонд сырья имеются ограничения, следовательно общий объем сырья каждого вида должен быть не больше общего количества сырья, т.е. получим следующую систему неравенств:

(1)

По экономическому смыслу переменные могут принимать только неотрицательные значения:

(2)

Стоимость всех изделий вида составит – – Соответственно общая стоимость произведенной предприятием продукции составит (3)

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

Z = 12 x₁+14x₂+11x₃ (max)

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

(max)

,

Эти дополнительные переменные по экономическому смыслу означают неиспользуемое при данном плане производства количество сырья того или иного вида. Например, это неиспользуемое количество сырья 1–го вида. Запишем систему основных ограничений в векторной форме:

Вектора , – ЛНЗ, следовательно они образуют базис.

Переменные х₄, х₅, х₆ – базисные переменные; х₁, х₂, х₃ – свободные переменные. Запишем первоначальный опорный план Х₀=(0;0;0;360;400;420)

Для оценки плана составим первую симплексную таблицу.

Б	СБ
									51,429
									46,667
		–12	–14	–11				–560,004	–504	–462

Проведем экономический анализ первой симплекс–таблицы. Дополнительные переменные принимают значения, которые совпадают с лимитами ресурсов предприятия, т.е. они совсем не используются и значения целевой функции равно нулю, т.е. не создают прибыль. Производство не запущено, прибыль равна нулю. Полученный план оптимальным не является. Это видно из индексной строки, т.к. имеются три отрицательные оценки. Эти оценки свидетельствуют не только о возможности увеличения прибыли, но и на сколько ее можно увеличить при введении в план производства единицы того или иного вида продукции. Так, например, число 12 означает, что при введении в план производства одного изделия вида А прибыль увеличится на 12 грн. Если в план производства ввести по одной единице продукции В и С, то прибыль соответственно составит 14 и 11 грн. С экономической точки зрения следует, что наиболее выгодным является включение в план производства продукции вида В. Т.к. число –14 является максимальным по абсолютной величине, то вектор необходимо ввести в базис.

Определим вектор, который необходимо вывести из базиса. Для этого находим θ:; a_i2 > 0, т.е. или

θ = min(36; 40; 84).

С экономической точки зрения мы определили какое количество изделий предприятие может изготовить с учетом норм расходов и имеющихся объемов сырья каждого вида. Учитывая объем сырья и нормы расходов, максимальное количество изделий вида В равно
min(36; 40; 84) = 36 т.е. ограничивающим фактором для производства изделий вида В является объем сырья 1–го вида. Т.е. предприятие может произвести 36 единиц изделия вида В, при этом сырье 1–го вида будет израсходовано полностью. Следовательно, вектор выводим из базиса. Столбец вектора и строка вектора являются ключевыми, число 10, стоящее на пересечении, является ключевым элементом. Составим вторую симплексную таблицу.

			7/10		4/10	1/10			36:4/10=90
						-1			40:1=40
			55/10			-5/10			240/8=30
		-2,2		-5,4	1,4			30х(-5,4)=-162

Мы получили новый опорный план . При данном плане производство выпускает 36 единиц изделий вида В и при этом остается не использованным 40 единиц сырья 2–го вида и 240 единиц сырья 3–го вида, а прибыль составит 504 грн.

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

Числа 1 и 8 показывают, соответственно, сколько потребуется сырья 2 и 3 вида при включении в план производства одного изделия вида С, а число –5,4 в индексной строке показывает на сколько увеличится прибыль предприятия.

Другими словами, если в план производства включить одно изделие вида С, то при этом потребуется уменьшить выпуск изделия вида В на и дополнительных затрат 1 ед. сырья 2–го вида и 8 ед. сырья 3–го вида, а общая прибыль возрастет на 5,4 грн. Аналогичный экономический смысл имеют элементы столбца , а вот элементы столбца имеют несколько иное экономическое содержание. Так число показывает, что при увеличении объемов сырья 1–го вида на одну единицу выпуск изделия вида В увеличится на ед. Для этого потребовалось бы увеличить объем сырья 2–го вида на 1 ед., а 3–го вида –на ед. При этом прибыль предприятия увеличилась бы на 1,4 грн.

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

Следующую симплекс–таблицу составляем аналогично 2–ой итерации.

			0,425			0,075		0,05
			0,313			-0,938		-1/8
		240/8	0,5/8 0,688		8/8	-0,5/8 -0,063		1/8
		1,518			0,357		2,075

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

Оптимальный план выпуска изделий состоит из 24 единиц продукции вида В и 30 – вида С. При этом плане полностью израсходовано сырье 1 и 3 вида, а сырье 2 вида осталось в количестве 10 ед., а прибыль составляет 666 грн.

Двойственность в ЛП

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

(max)

, , .

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

1) покупающая организация старается минимизировать общую стоимость ресурсов;

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

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

.

Согласно второму требованию вводятся ограничения: на единицу А вида продукции расходуется 7 единиц первого ресурса ценой , 8 ед. второго ресурса ценой , 9 ед. третьего ресурса ценой . Стоимость всех ресурсов, расходуемых на производство единицы продукции вида А, равна и должна составить не менее 12, т.е. .

Аналогичные рассуждения проводим для продукции вида В и С и получаем систему неравенств:

,

Получили математическую модель двойственной задачи. В результате решения ИЗ было получено следующее решение:

			0,425			0,075		0,05
			0,313			-0,938		-1/8
		240/8	0,5/8 0,688		8/8	-0,5/8 -0,063		1/8
		1,518			0,357		2,075

; .

Для получения решения ДЗ можно воспользоваться решением ИЗ. По первой теореме двойственности

.

Значение компонент оптимального плана ДЗ не требует дополнительных вычислений – они расположены в индексной строке последней симплексной таблицы ИЗ на пересечении со столбцами векторов, входящих в начальный базис, если к содержимому прибавить коэффициенты целевой функции при соответствующей переменной. Следовательно, ; ; . . Т.к. , то 1 и 3 вид сырья являются дефицитными, в оптимальном плане ИЗ они полностью использованы. следовательно 2 вид сырья недефицитный, в оптимальном плане ИЗ он использован не полностью.

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

Величина двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции ИЗ при увеличении количества сырья соответствующего вида на 1 ед. Так, увеличение количества сырья 1–го вида на 1 ед. приводит к тому, что можно найти новый оптимальный план производства, при котором общая стоимость увеличится на 0,357 и будет равна . А числа, стоящие в столбце, показывают, что полученное увеличение прибыли может быть достигнуто за счет увеличения выпуска изделия В на 0,075 ед. и сокращении выпуска изделия С на 0,063 ед., а расход сырья 2–го вида возрастет на 0,938 ед. Аналогичный анализ мы можем сделать и для 3–го вида сырья. При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи, получим:

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