Методические указания.

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

a₁₁x₁ + ... + a_1j x_j + ... + a_1n x_n  Y₁

. . . . . . . . . . . . . . .

a_ix₁ + ... + a_ij x_j + ... + a_in x_n  Y_i (59)

. . . . . . . . . . . . . . .

a_m1x₁ + ... + a_mj x_j + ... + a_mn x_n  Y_m

Ограничения по сбыту продукции, представленные в виде неравенств, имеют вид:

x₁  X₁

. . . . . .

x_j  X_j (60)

. . . . . .

x_n X_n,

где 1, ... , i , ... , m - количество типов оборудования;

1, ... , j , ... , n - количество видов выпускаемой продукции;

Y₁, ... , Y_i , ... , Y_m - фонд времени работы оборудования i-ого вида, час.;

a_ij - время работы станка i -го типа при производстве единицы продукции j-го вида;

x₁ , ... , x_j , ... , x_n - объемы производства продукции.

X_j - максимальное количество продукции j-го вида, которое может быть продано за данный период времени.

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

a₁₁x₁ + ... + a_1j x_j + ... + a_1n x_n + Z₁ = Y₁

. . . . . . . . . . . . . . .

a_ix₁ + ... + a_ij x_j + ... + a_in x_n + Z_i = Y_i (61)

. . . . . . . . . . . . . . .

a_m1x₁ + ... + a_mj x_j + ... + a_mn x_n + Z_m = Y_m

x₁ + K₁ = X₁

. . . . . .

x_j + K_j = X_j (62)

. . . . . .

x_n + K_n = X_n,

Целевая функция, максимизирующая прибыль предприятия, имеет вид :

F = x₁ ( Ц₁ - С₁) +...+ x_j ( Ц_j - С_j) +... + x_n( Ц_n- С_n) - Е_у-п - A₁ Z₁ - ... - A_i Z_i -

- ... - A_n Z_n  max (63)

где Z₁, ... ,Z_i , ... , Z_n - недозагрузка оборудования i-ого вида, час.;

A₁ , ..., A_i , .., A_n - амортизационные отчисления на 1 час простоя оборудования i-ого вида;

K_j - разница между максимальным и фактическим объемом продаж продукции j-ого вида;

Ц₁,...,Ц_j,...,Ц_n - цена единицы продукции j-ого вида;

С₁,...,С_j,...,С_n - себестоимость производства единицы продукции j-ого вида в части расходов, зависящих от объема производства, руб.;

Е_у-п - условно-постоянные расходы, руб.

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

Нормы затрат времени работы отдельных видов оборудования на производство единицы продукции каждого вида приведены в табл. 12. Условно-постоянные расходы предприятия, цены и себестоимость производства единицы продукции каждого вида в части зависящих от объема работы расходов приведены в табл. 13.

Таблица 12.

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

Вид	Вид продукции			Фонд	Амортиза­цион­ные
оборудования	1	2	3	времени	отчисле­ния
1	1,0	2,0	0	1200	12,0
2	1,2	0,7	1,3	600	14,0
3	0	0,3	2,4	800	8,0
4	0,4	1,7	2,8	1400	26,0

Таблица 13.

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

Наименование	Вид продукции
показателей	1	2	3
Себестоимость производства единицы продукции, руб.	300	600	500
Цена единицы продукции, руб.	400	900	700
Ограничения по сбыту продукции, ед.	нет	400	110
Условно-постоянные расходы предприятия, руб.	28000

Система ограничений, представленная в виде уравнений, будет иметь вид:

x₁ + 2x₂ + z₁ = 1200

1,2x₁ + 0,7x₂ + 1,3x₃ + z₂ = 600

0,3x₂ + 2,4x₃ + z₃ = 800

0,4x₁ + 1,7x₂ + 2,8x₃ + z₄ = 1400

x₂ + k₂ = 400

x₃ + k₃ = 110

Целевая функция, максимизирующая прибыль предприятия, имеет вид:

F = (400-300)x₁ + (900-600)x₂ + (700-500)x₃ - 28000 - 12z₁ - 14z₂ - 8z₃ - - 26z₄  max

или:

F = 100x₁ + 300x₂ + 200x₃ - 28000 - 12z₁ - 14z₂ -8z₃ -26z₄  max

Для упрощения последующих расчетов условно-постоян­ные расходы из целевой функции можно исключить. Тогда целевая функция примет вид:

F = 100x₁ + 300x₂ + 200x₃ - 12z₁ - 14z₂ -8z₃ -26z₄  max

Определение оптимальной структуры производства по видам продукции производится симплекс-методом в табл. 14 - 17. Признаком оптимального плана при использовании симплекс-ме­тода для максимизации целевой функции являются нулевые оценки (Z - C) для переменных, вошедших в базис, и неотрицательные оценки (Z - C) для переменных, не вошедших в базис. В тех случаях, когда коэффициенты в столбцах симплексной таблицы для переменных, не вошедших в базис, неположительны, оптимальный план составлен быть не может. Первоначальный план приведен в табл. 14. Из табл. 14 видно, что базисными переменными первоначального плана являются z₁, z₂, z₃, z₄, k₂ и k₃. Значение целевой функции равно:

-12*1200 + -14*600 + -8*800 + -26*1400 + 0*400 + 0*110 = -65600

Оценки видов продукции (Z - C) составляют:

- для первого вида продукции:

-12*1 + -14*1,2 + -8*0 + -26*0,4 - 100 = -139,2

- для второго вида продукции:

-12*2 + -14*0,7 + -8*0,3 + -26*1,7 +0*1 - 300 = -380,4

- для третьего вида продукции:

-12*0 + -14*1,3 + -8*2,4 + -26*2,8 + 0*1 - 200 = -310,2

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

Отрицательные оценки переменных, не входящих в базис, и наличие положительных элементов в столбцах симплекс-таб­лицы, соответствующих этим переменным, свидетельствует о том, что первоначальный план не является оптимальным и может быть улучшен. Для улучшения первоначального плана необходимо в столбцах табл. 14, соответствующих переменным, не входящим в базис, найти разрешающий элемент. Для первой итерации при этом в каждом столбце, не входящем в базис и имеющем отрицательную оценку (Z - C), надо выбрать элемент, обеспечивающий минимальное частное от деления свободного члена уравнения на величину данного элемента.

₀₁ = min (1200/1; 600/1,2; 1400/0,4) = 600/1,2 = 500

₀₂ = min (1200/2; 600/0,7; 800/0,3; 1400/1,7; 400/1) = 400/1 = 400

₀₃ = min (600/1,3; 800/2,4; 1400/2,8; 110/1) = 110/1 = 110

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

₀₁*( Z₁ - C₁) = 500*(-139,2) = -69600

₀₂*( Z₂ - C₂) = 400*(-380,4) = -152160 (min)

₀₃*( Z₃ - C₃) = 110*(-310,2) = -34122

Таблица 14.

Базис	Сбаз.	А0	С1=100	С2=300	С3=200	С4=-12	С5=-14	С6=-8	С7=-26	С8=0	С9=0
			А1	А2	А3	А4	А5	А6	А7	А8	А9
А4	-12	1200	1	2	0	1	0	0	0	0	0
А5	-14	600	1,2	0,7	1,3	0	1	0	0	0	0
А6	-8	800	0	0,3	2,4	0	0	1	0	0	0
А7	-26	1400	0,4	1,7	2,8	0	0	0	1	0	0
А8	0	400	0	[1]	0	0	0	0	0	1	0
А9	0	110	0	0	1	0	0	0	0	0	1
Z - C		-65600	-139,2	-380,4	-310,2	0	0	0	0	0	0

Таблица 15.

Базис	Сбаз.	А0	С1=100	С2=300	С3=200	С4=-12	С5=-14	С6=-8	С7=-26	С8=0	С9=0
			А1	А2	А3	А4	А5	А6	А7	А8	А9
А4	-12	400	1	0	0	1	0	0	0	-2	0
А5	-14	320	[1,2]	0	1,3	0	1	0	0	-0,7	0
А6	-8	680	0	0	2,4	0	0	1	0	-0,3	0
А7	-26	720	0,4	0	2,8	0	0	0	1	-1,7	0
А2	300	400	0	1	0	0	0	0	0	1	0
А9	0	110	0	0	1	0	0	0	0	0	1
Z - C		86560	-139,2	0	-310,2	0	0	0	0	380,4	0

Таблица 16.

Базис	Сбаз.	А0	С1=100	С2=300	С3=200	С4=-12	С5=-14	С6=-8	С7=-26	С8=0	С9=0
			А1	А2	А3	А4	А5	А6	А7	А8	А9
А4	-12	133,3	0	0	-1,0833	1	-0,8333	0	0	-1,4167	0
А1	100	266,667	1	0	1,0833	0	0,8333	0	0	-0,5833	0
А6	-8	680	0	0	2,4	0	0	1	0	-0,3	0
А7	-26	613,333	0	0	2,3667	0	-0,3333	0	1	-1,4667	0
А2	300	400	0	1	0	0	0	0	0	1	0
А9	0	110	0	0	[1]	0	0	0	0	0	1
Z - C		123680,4	0	0	-159,4	0	116,0	0	0	299,2	0

Таблица 17.

Ба-	Сбаз.	А0	С1=100	С2=300	С3=200	С4=-12	С5=-14	С6=-8	С7=-26	С8=0	С9=0
зис			А1	А2	А3	А4	А5	А6	А7	А8	А9
А4	-12	252,46	0	0	0	1	-0,8333	0	0	-1,4167	1,0833
А1	100	147,504	1	0	0	0	0,8333	0	0	-0,5833	-1,0833
А6	-8	416,00	0	0	0	0	0	1	0	-0,3	-2,4
А7	-26	352,996	0	0	0	0	-0,3333	0	1	-1,4667	-2,3667
А2	300	400	0	1	0	0	0	0	0	1	0
А3	200	110	0	0	1	0	0	0	0	0	1
Z - C		141215,0	0	0	0	0	116,0	0	0	299,2	159,4

В табл. 14 разрешающий элемент выделен квадратными скобками. Для включения переменной x₂ в состав базиса вместо переменной k₂ необходимо методом Жордана-Гаусса необходимо произвести алгебраические преобразования, сложение и вычитание строк симплексной таблицы таким образом, чтобы разрешающий элемент стал равен единице, а все остальные элементы этого столбца стали равны нулю. Для этого из каждого элемента первой строки табл. 14 необходимо вычесть соответствующий элемент пятой строки, умноженный на 2, из каждого элемента второй строки табл. 14 необходимо вычесть соответствующий элемент пятой строки, умноженный на 0,7 и т. д.

Результаты преобразований приведены в табл. 15. При этом в столбце "базис" элемент А₈, соответствующий переменной k₂, заменен элементом А₂, соответствующим переменной x₂. В столбце "С_баз." оценка с₈ (0) заменена оценкой с₂ (300). Оценки (Z - - C) составили:

(Z₂ - C₂) = 300*0 - 300 = 0;

(Z₈ - C₈) = -2*(-12) + -0,7*(-14) + -0,3*(-8) + -1,7*(-26) + 1*300 = = 380,4.

Остальные оценки не изменились. Величина целевой функции составила:

-12*400 + -14*320 + -8*680 + -26*720 + 300*400 = 86560

Отрицательные оценки (Z - C) в табл. 15 имеют переменные x₁ и x₃. Наличие положительных элементов в столбцах А₁ и А₃ свидетельствует о том, что план, приведенный в табл. 15, не является оптимальным и может быть улучшен в результате включения в базис переменной x₁ или x₂. Определение разрешающего элемента в столбцах А₁ и А₃ производится так же, как для первой итерации.

Вторая итерация.

₀₁ = min (400/1; 320/1,2; 720/0,4) = 320/1,2 = 266,7

₀₃ = min (320/1,3; 680/2,4; 720/2,8; 110/1) = 110/1 = 110

₀₁*( Z₁ - C₁) = 266,7*(-139,2) = -37120 (min)

₀₃*( Z₃ - C₃) = 110*(-310,2) = -34122

Разрешающий элемент в табл. 15 выделен квадратными скобками. Преобразования табл. 15 в табл. 14 производятся в вышеописанной последовательности. Каждый элемент второй строки табл. 16 получен как частное от деления соответствующего элемента второй строки табл. 15 на коэффициент 1,2. Каждый элемент первой строки табл. 16 получен в результате вычитания из элемента первой строки табл. 15 соответствующего элемента второй строки табл. 15, деленого на коэффициент 1,2. Например, в табл. 16 в столбце А_о элемент первой строки рассчитан следующим образом:

400 - 320/1,2 = 133,3.

Элемент четвертой строки табл. 16 в столбце А_о рассчитан следующим образом:

720 - 320*0,4/1,2 = 613,333.

Аналогично рассчитаны все элементы первой и четвертой строк табл. 16.

Результаты преобразований приведены в табл. 16. При этом в столбце "базис" элемент А₅, соответствующий переменной z₂, заменен элементом А₁, соответствующим переменной x₁. В столбце "С_баз." оценка с₅ (-14) заменена оценкой с₁ (100). Оценки (Z- - C) составили:

(Z₁ - C₁) = 100*0 - 100 = 0;

(Z₃ - C₃) = -12*(-1,0833) +100*(1,0833) + -8*(2,4) + -26*(2,3667)+

+ 300*0 + 0*1 - 200 = -159,4;

(Z₅ - C₅) = -12*(-0,08333) +100*(0,08333) + -8*0 + -26*(-0,3333)+

+ 300*0 + 0*0 - (-14) = 116,0;

(Z₈ - C₈) = -12*(-1,4167) +100*(-0,5833) + -8*(-03) + -26*(-1,4667)+

+ 300*1 + 0*0 - (-14) = 299,2

Остальные оценки не изменились. Величина целевой функции составила:

-12*133,3 + 100*266,667 + -8*680 + -26*613,333 + 300*400 = 123680,4

Отрицательную оценку (Z - C) в табл. 16 имеет переменная x₃. Наличие положительных элементов в столбце А₃ свидетельствует о том, что план, приведенный в табл. 16, не является оптимальным и может быть улучшен в результате включения в базис переменной x₃. Определение разрешающего элемента в столбце А₃ производится так же, как для предыдущих итераций.

Третья итерация.

₀₃ = min (266,667/1,0833; 680/2,4; 613,3/2,37; 110/1) = 110/1 = 110

₀₃*( Z₃ - C₃) = 110*(-159,2) = -17512

Разрешающий элемент в табл. 16 выделен квадратными скобками. Преобразования табл. 16 в табл. 17 производятся по аналогии с предыдущими итерациями.

В результате выполненных преобразований оценка для столбца А₉ составила:

(Z₉ - C₉) = -12*(1,0833) +100*(-1,0833) + -8*(-2,4) + -26*(-2,3667) + + 300*0 + 200*1 - 0 = 159,4

Величина целевой функции составила:

-12*252,46 + 100*147,504 + -8*416 + -26*352,996 + 300*400 + +200*110 = 141215,0

В последней строке табл. 17 все оценки (Z - C) неотрицательные. Следовательно план, приведенный в табл. 17 является оптимальным и дальнейшие улучшения его невозможны. Значения переменных, вошедших в базис и соответствующих оптимальному плану, приведены в столбце А_о табл. 17. Оптимальные объемы производства по видам продукции составляют:

- первый вид (x₁) - 147,504 ед.;

- второй вид (x₂) - 400 ед.;

- третий вид (x₃) - 110 ед.

Недоиспользование производственной мощности по видам оборудования составляет:

- первый вид (z₁) - 252,46 час.;

- второй вид (z₂) - 0 час.;

- третий вид (z₃) - 416 час.;

- четвертый вид (z₄) - 352,996 час.

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

Для контроля правильности выполненных расчетов рекомендуется проверить соответствие полученных оптимальных значений переменных ограничениям задачи. Несоответствие данным ограничениям показывает, что расчеты с помощью симплекс-метода выполнены неправильно.

147,5 + 2*400 + 252,46 = 1200

1,2*147,5 + 0,7*400 + 1,3*110 = 600

0,3*400 + 2,4*110 + 416,0 = 800

0,4*147,5 + 1,7*400 + 2,8*110 + 353,0 = 1400

400 + 0 = 400

110 + 0 = 110

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

Прибыль предприятия с учетом условно-постоянных расходов составит 141215,0 - 28000 = 113215,0 ед.