Модель задачи оптимального ассортимента продукции.

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

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

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

Для математической записи оптимизационной ассортиментной задачи используем следующий небольшой пример. В цехе пищевого предприятия вырабатывается три вида продукции П₁, П₂, П₃. Известны виды используемых ресурсов в процессе производства P₁, P₂, Р₃, нормы расхода их на единицу готовой продукции и наличие каждого ресурса. В качестве критерия оптимальности принята прибыль на единицу каждого вида продукции. Численная информация задачи представлена в табл.4.

В качестве искомых неизвестных принимаются x₁, x₂, x₃, означающие количества включаемых в план производства видов продукции соответственно П₁, П₂, П₃.

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

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

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

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

Таблица 4

Виды основных ресурсов	Расход ресурсов на 1т продукции, т	Наличие ресурсов, т
П1	П2	П3
P1
P2
Р3
Прибыль на 1т, руб.

 

 

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

14x₁ + 28x₂ + 5x₃< 700

21x₁ + 21х₂ + 5х_з <630

6x₁+6x₂+1x₃<162

Выпуск продукции не может быть отрицательным, поэтому

х₁ ≥ 0, х₂ ≥ 0, х₃ ≥ 0.

Общая сумма прибыли (целевая функция)

F = 28х₁ + 49х₂ + 9х₃ = max.

 

Для решения задачи симплексным методом неравенства преобра­зуются в эквивалентные равенства путем добавления в каждое нера­венство по одному дополнительному неизвестному с коэффициентом + 1 и нулевым уравнением прибыли. Для удобства расчетов левые и правые части уравнений меняются местами. В этом случае исходные неравенства примут вид симплексных уравнений:

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

В столбцах таблицы записывают: в первом (С_j) - прибыль единицы продукции, которая вводится в план выпуска; во втором (p₀) – неизвестные, включаемые в план; в третьем (х₀) – свободные величины; в остальных - коэффициенты при неизвестных уравнениях. В верхней части этих столбцов отражаются коэффициенты при неизвестных целевой функции.

 

Исходная таблица

сj	p0	x0
x1	x2	x3	x4	x5	x6
	x4
	x5
	x6
Zj - Cj		-28	-49	-9

 

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

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

При решении задач на максимум целевой функции наличие в целевой строке отрицательных чисел указывает на возможность начала или продолжения решения задачи. Порядок решения таков: из отрицательных чисел целевой строки выбирается наибольшее по модулю. Столбец, в котором оно находится, принимается за ключевой (или разрешающий) и для удобства расчетов выделяется. В нашем примере таким столбцом будет x₂, имеющий в целевой строке наибольшую по модулю величину - 49.

Затем элементы столбца x₀ (свободные величины) делят на соответствующие коэффициенты ключевого столбца и полученные результаты сопоставляют между собой. Строка с наименьшим отно­шением принимается за ключевую и также для удобства выделяется. В нашем случае 700/I4 = 25, 630/21= 30, 162/6 = 27. Наимень­шее отношение 25 имеет срока х₄, она и будет ключевой. Ключевой элемент 28.

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

В столбцах Р₀ и С_j занимают место вводимая в план неиз­вестная x₂ с прибылью 49 (1-я итерация). Остальные элемен­ты преобразуются по следующему правилу:

- для преобразуемого элемента в его столбце находят элемент ключевой строки, а в его строке - элемент ключевого столб­ца;

- соответствующие элементы ключевой строки и ключевого столбца перемножаются и полученное произведение делят на ключе­вой момент;

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

Следуя этому правилу, преобразование элементов столбца х₀ будет:

 

630 -

162 -

0 -

 

Включение на первой итерации в план неизвестной х₂ (выпуск продукции П₂ вида) обеспечит сумму прибыли 1225 руб.

1-ая итерация

сj	p1	x0	x1	x2	x3	x4	x5	x6
	x2		1/2		5/28	1/25
	x5		21/2		5/4	-3/4
	x6				-1/14	-3/14
Zj - Cj		-7/2		-1/4	7/4

 

Решение задачи продолжается, так как в целевой строке два отрицательных элемента. Наибольший по модулю элемент - 7/2. Он находится в столбце х₁, который принимается за ключевой, а ключевой строкой будет х₆ (25:1/2=50; 105:21/2=10; 12:3=4). Элементы таблицы преобразуются в том же порядке по изложенному правилу и записываются в новую таблицу (2-я итерация).

 

2-я итерация

сj	p2	x0	x1	x2	x3	x4	x5	x6
	x2				4/21	1/14		-1/6
	x5				3/2			-7/2
	x1				-1/42	-1/14		1/3
Zj - Cj				-1/3	3/2		7/6

 

В полученном на 2-й итерации плане ключевым столбцом будет х₃, ключевой строкой х₅ (23:4/21=121; 63:3/2=42, при отрицательном элементе отношение не определяется), ключевым элементом 3/2. Элементы ключевой строки преобразуются деле­нием их на ключевой элемент (3-я итерация). Остальные элементы преобразуются рассмотренным выше или более упрощенным способом, смысл которого заключается в следующем:

- для преобразуемого элемента в его столбце уже преобразованный элемент ключевой строки (в новой таблице, 3-я итерация), а в его строке - еще не преобразованный элемент ключевого столбца (в предыдущей таблице);

- найденные элементы перемножаются и полученный результат вычитается из значения элемента, которое он имел до преобразо­вания.

Этот новый результат является преобразованным элементом и записывается в новой таблице в том же самом месте. По этому правилу преобразуем элементы столбца х₆.

3-я итерация

сj	p2	x0	x1	x2	x3	x4	x5	x6
	x2					1/14	-8/23	5/18
	x3						2/3	-7/3
	x1					-1/14	1/63	5/18
Zj - Cj					3/2	2/9	7/18

 

Для элемента -1/6 в его столбце уже преобразованный элемент ключевой строки в новой таблице -7/3. Этот элемент умножается на еще не преобразованный элемент ключевого столбца 4/21. Полученный результат вычитается из преобразуемого элемента и записывается в новой таблице:

-1/6 - (-7/3 * 4/21) = 5/18

Также и для двух других элементов:

1/3 – [(-7/3) - (-1/42)] = 5/18; 7/6 – [(-7/3) * (-1/3)] = 7/18

Остальные элементы преобразованы в таком же порядке и записаны в таблицу (3-я итерация).

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

Как видно из таблицы, оптимальный план предусматривает выпуск продукции П₁ - 5 ед. (х₁ = 5), П₂ вида - 15 ед. (х₂ = 15), П₃ вида - 42 ед. (х₃ = 42). Дополнительные неизвестные в план не вошли, следовательно, х₄ = 0, х₅ = 0, х₆= 0. Подставив значе­ния неизвестных в уравнения, получим:

14*5 + 28*15 + 5*42 + 0 = 700

21*5 + 21*15 + 6*42 + 0 = 630

6*6+ 6*15 + 1*42 + 0 = 162

F = 28*5 + 49*15 + 9*42 = 1253

При постановке задачи были приняты ограничения только по запасам сырья (P₁, P₂, Р₃). Другие ограничения не учитывались. Но если бы в плане требовалось предусмотреть ассортиментные соотношения (например, выпуск продукции П₁ вида должен быть не меньше выпуска продукции П₂ вида, т.е. х₁ х₂), то в систему неравенств добавляется это ограничение:

Эта система преобразуется в симплексные уравнения и ре­шается по изложенным правилам.

 

Проведем анализ оптимального плана.

1) Запасы сырья трех видов используются полностью без остатка, так как х₄ = х₅ = х₆ = 0.

2) Рассмотрим элементы матрицы.

Элементы столбца х₄ свидетельствуют: если запасы P₁ будут увеличены на I ед. (х₄ = 1), то выпуск продукции П₂ вида увели­чится на 1/14 ед. (х₂ = 15 + 1/14), выпуск продукции П₃ вида не изменится, выпуск продукции П₁ вида уменьшится на 1/14 ед. (5 - 1/14). Сумма прибыли увеличится на 1,5 руб.

Элементы столбца х₅ показывают, что увеличение запасов P₂ на I ед. (х₅ = I) позволит увеличить выпуск продукции П₃ вида на 2/3 ед., П₁ вида на 1/63 ед., прибыль на 2/9 руб. и снизить выпуск продукции П₂ вида на 8/23 ед. Изменения объемов производства и суммы прибыли вызовет и увеличение запасов Р₃ (столбец х₆). Снижение запасов сырья приводит к изменениям выпуска продукции и суммы прибыли в обратном порядке.

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