Задание №1

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

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

Количество каждого из товаров задаётся с помощью производственной программы:

, где

X1, x2, x3, x4 - кол-во 1-ой, 2-ой, 3-ей и 4-ой продукции соответственно.

Технологическая матрица затрат показывает какое количество ресурсов требуется для производства 1 единицы продукции. Каждому виду продукции соответствует столбец в технологической матрице затрат А. Каждая строка матрицы А соответствует одному из видов ресурсов. Чтобы получить расход каждого ресурса при заданной производственной программе перемножим матрицу А и вектор производственной программы X:

Каждый элемент полученного вектора равен расходу соответствующего ресурса при заданной производственной программе, т.е. при x_1, x_2, x_3, x₄ . Так как матрица А указывает на необходимое количество определённого ресурса для производства 1 единицы продукции, то умножая это число на общее количество продукции данного вида мы получим расход данного ресурса для производства заданного количества определённого вида продукции. Сложив расход ресурса по всем видам продукции, мы получим общий расход ресурса.

Вектор В указывает на располагаемое количество ресурсов. Каждый элемент соответствует одному виду ресурса. Таким образом, при производстве при заданной производственной программе X и объеме располагаемых ресурсов B должны выполняться неравенства для каждого ресурса:

; ;

_{Вектор С указывает на прибыль от продажи 1 единицы продукции каждого вида. Каждый элемент вектора соответствует одному виду продукции. Чтобы найти прибыль от каждого вида продукции следует помножить вектор производственной программу X на вектор удельной прибыли С:}

_{Сложив элементы полученного вектора мы получим совокупную прибыль от продажи всей продукции при заданном векторе производственной программы X. Так как x1, x2, x3, x4 – неизвестные запишем полученное выражение в виде функции:}

Для достижения максимальной прибыли требуется найти максимум полученной функции z. При этом x₁, x₂, x₃, x₄ по смыслу 0. Учитывая условия ограничения по ресурсам, получим задачу на условный экстремум:

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

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

х₅ – остаток ресурса 1-го вида,

х₆ – остаток ресурса 2-го вида,

х₇ – остаток ресурса 3-го вида.

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

Б	x1	x2	x3	x4	x5	x6	x7	h		Базисные решения
x5	1	0	2	5	1	0	0	110		(0;0;0;0;110;126;114)
x6	3	6	0	4	0	1	0	126	1/3
x7	2	4	1	3	0	0	1	114
z	-30	-28	-9	-23	0	0	0	0
x5	0	-2	2	11/3	1	-1/3	0	68		(42;0;0;0;68;0;30)
x1	1	2	0	4/3	0	1/3	0	42	(-1) (-2) (30)
x7	0	0	1	1/3	0	-2/3	1	30
z	0	32	-9	17	0	10	0	1260
x5	0	-2	0	3	1	1	-2	8		(42;0;30;0;8;0;0)
x1	1	2	0	4/3	0	1/3	0	42
x3	0	0	1	1/3	0	-2/3	1	30	(9) (-2)
z	0	32	0	20	0	4	9	1530

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

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

первого вида -

второго вида -

третьего вида -

Узкими местами производства, т.е. ресурсами, использующимися полностью, являются 2-ой и 3-ий ресурсы, и соответственно.

Максимальная прибыль:

При решении мы получили обращенный базис:

, где

1-ый столбец – столбец симплексной таблицы, 2-ой – столбец , а 3-ий – столбец

Также, при решении мы получили и базис:

, где

1-ый столбец – столбец симплексной таблицы, 2-ой – столбец , а 3-ий – столбец

Выполним проверку:

- верно

- вектор свободных членов системы ограничений

- вектор-столбец конечной симплексной таблицы

- верно

Решим исходную задачу графическим методом

Так как в базисе отсутствуют и , исключим их из модели

где 1 - , 2 - , 3 - , 4 – градиент целевой функции , 5 – линия уровня, заштрихованная область – область допустимых решений, т.е. значения и , при которых выполняются ограничения. ОДР образует многоугольник. Передвигая линию уровня по направлению градиента, мы пройдём все вершины многоугольника ОДР. Последняя вершина будет соответствовать максимальному значению целевой функции. В данном случае это точка А с координатами (42;30) ( и )

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

Максимальная прибыль:

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

первого вида - (110-42-2

второго вида - (126-42)

третьего вида - (114-42

Задание №2

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

Некое предприятие, использующее те же ресурсы что и предприятие из предыдущей задачи, желает приобрести все эти ресурсы. Оно желает приобрести их по ценам , и соответственно за единицу каждого из трёх ресурсов. Из условий предыдущей задачи нам известны затраты всех 3-х ресурсов для производства для каждого из 4-х видов продукции, количество ресурсов на производстве и прибыль от единицы каждой продукции. Их мы представили в виде матриц и векторов:

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

Для производства продукции 1-ого вида требуется 1 единица 1-ого ресурса, 3 единицы 2-ого ресурса и 2 единицы 3-его ресурса, что соответствует элементам 1-ого столбца матрица А. Прибыль от продажи продукции 1-ого вида равна 30. Следовательно, для целесообразности продажи ресурсов прибыль от продажи 1 единицы 1-ого ресурса, 3-х единиц 2-ого ресурса и 2-х единиц 3-его ресурса должна быть больше, либо равна 30, т.е. прибыли от продажи продукции 1-ого вида:

Соответственные условия должны выполняться и для продукции других видов. Им соответствуют 2-ой, 3-ий и 4-ый столбцы матрицы А, а также 2-ой, 3-ий и 4-ый элементы матрицы-строки прибыли С:

Но при продаже требуется учитывать и интересы покупателя. Естественным желанием покупателя является снижение расходов. Так как предприятие желает закупить весь объём имеющихся ресурсов, то его затраты при ценах , и составят , где коэффициенты при , и - количество имеющихся ресурсов. Таким образом:

Кроме того, так как цены не могут быть отрицательными, то .

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

Мы получили задачу двойственную линейной производственной задаче из 1-ого задания. Отсюда, по 2-ой теореме двойственности, при производственной программе и ценах , и , необходимым и достаточным условием оптимальности решений двойственных задач является выполнение условий:

Учитывая, что для линейной производственной задачи оптимальное решение уже найдено (42, 0, 30. 0), подставим эти значения систему:

Так как 42 и 30 не равны 0, то мы получим систему:

Учитывая, что 1-ый ресурс был избыточным, то, согласно теореме двойственности, его двойственная оценка , получим систему:

Решив её, мы получим и . Оптимальное решение:

(0, 4, 9)

Данные значения , и являются двойственными оценками соответствующих ресурсов, т.е. оценка единицы 1-ого ресурса равна 0, оценка единицы 2-ого ресурса равна 4, а оценка 3-его ресурса равна 9. Эти оценки являются «теневыми» ценами ресурсов. Экономически они указывают на сколько увеличится прибыль при выполнении оптимальной производственной программы, если количество соответствующего ресурса увеличить на единицу, при неизменном количестве остальных ресурсов.

Используя задачу 1, мы можем найти оценку технологии, т.е. на сколько уменьшится прибыль, если будет произведена 1 единица продукции не по оптимальной программе. Оценки технологий получились в конечной симплексной таблице как коэффициенты при соответствующих x в целевой функции. Таким образом, при производстве единицы 2-ой продукции прибыль упадёт на 32, а для 4-ой продукции падение составит 20.

Задание №3

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

При выполнении оптимальной производственной программы из задания 1 2-ой и 3-ий ресурс расходуются полностью, они образовывают «узкие места» производства. Для увеличения прибыли требуется закупить дополнительно данные ресурсы в количестве и . Закупки 1-ого ресурса не требуются, так как этот ресурс избыточен.

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

Оптимальное решение исходной задачи можно представить в виде:

Новое решение будет иметь вид: Если оно допустимо, то требуется. Чтобы структура производства не поменялась, т.е . Отсюда: