Экономика цеха промышленного предприятия

 

 

1. Решение задачи линейного программирования с размерностью n=2 без применения ЭВМ.

В соответствии с вариантом  № 35 условие задачи: Цех промышленного предприятия выпускает 2 типа краски для внутренних (А) и наружных (В) работ. Для производства красок требуется 2 вида сырья (С1 и С2), запасы сырья определяются возможностями поставщиков. Известен доход от реализации 1 кг краски каждого типа. Необходимо составить оптимальный план производства красок обоих типов, обеспечивающий максимальный суммарный доход от реализации продукции.

Табл.1.1 Численные значения для задачи №1

Вид сырья	Запас сырья, кг	Нормы расхода сырья на 1 кг краски
		А	В
Сырье1	6300	9	7
Сырье2	5000	5	10
Доход от реализации 1 кг краски,y.e.		200	200

Обозначение искомых переменных: Х₁- план по производству краски А, кг

                                                          Х₂- план по производству краски В, кг

Составление математической модели:

1) целевая функция: F(X)= 200X₁ + 200X₂ → max; (1)

2) ограничения:        9Х₁ + 7 Х₂ ≤ 6300; (2)

                                 5Х₁ + 10Х₂ ≤ 5000;  (3)

3) граничные условия: Х₁ ≥ 0; Х₂ ≥ 0

1.1. Графический  метод решения задачи ЛП, n=2

1) Построение области  допустимых решений (рис.1): отображаю на плоскости (Х₁, Х₂) неравенства, (2): Х₁=0, Х₂=6300/7=900;

                                        Х₂=0, Х₁=6300/9=700;

И неравенство (3): Х₂ =0, Х₁=5000/5=1000;

                               Х₁=0, Х₂ =5000/500.

Также отображаем на плоскости  неравенства - граничные условия: Х₁ ≥ 0; Х₂ ≥ 0.

2) Построение лини уровня  целевой функции.

Зададимся произвольным значением  целевой функции, F= 12000.

F= 150Х₁ + 200Х₂=12000; (4)

И тогда из (4): Х₁=0, Х₂=60;

                        Х₂=0, Х₂=80.

Зададимся большим значением  целевой функции, F= 15000.

F= 150Х₁ + 200Х₂=15000; (5)

И тогда из (5): Х₁=0, Х₂=75;

                        Х₂=0, Х₂=100.

Таким образом, стрелка на рис.1 указывает направление максимизации функции.

Рис.1 Результата решения  графическим методом

Вывод: из рис.1 очевидно, что  оптимальное решение задачи будет  наблюдаться при Х₁=510 кг, Х₂=245 кг – планы по производстве красок А и В соответственно. Таким образом, суммарный доход от реализации будет равен F=510 * 200+ 245 * 200 = 151000 y.e.

2. Решение задачи симплекс-методом (аналитическая реализация).

Приводим математическую модель в стандартную форму:

Максимизационную Ц.Ф. заменяем на равнозначную ей минимизационную Z’= -Z = -200 Х₁- 200 Х₂; (6)

Ограничения в виде неравенств (2),(3) приводим к стандартной форме  в виде равенств, путем ввода неотрицательных  переменных Х₃,Х₄:

9Х₁ + 7 Х₂ + Х₃ = 6300; (7)

5Х₁ + 10Х₂ + Х₄ = 5000. (8)

Граничные условия: все переменные неотрицательны Х_i≥0, где i=1..4.

 

Начальное приближение, опорное  решение:

Х₁=0    Свободные                          Х₃≠0    Базисные

Х₂=0    переменные                        Х₄≠0    переменные

Используя уравнения (7),(8), выразим базисные переменные через свободные:

Х₃=   6300   -7Х₂ - 9Х₁

Х₄=   5000   - 10Х₂ - 5Х₁

F’=      0      - 200 Х₁-200 Х₂

 

Решение:

Х₁=0    Свободные                          Х₃=6300    Базис

Х₂=0    переменные                        Х₄=5000   

Анализ решения: решение  допустимое, т.к. все Х неотрицательны, но неоптимальное, т.к.  коэффициенты при Х₁, Х₂ отрицательны, соответственно их увеличение приведет к уменьшению целевой функции.

 

2 этап. Первая итерация  i=1.

Начнем увеличивать Х₂, т.к. коэффициент при нем в целевой функции наиболее отрицателен. Таким образом Х₂ переходит в базис.

В свободную переменную нужно перевести  ту, которая быстрее обратиться в нуль:

Х₃=   6300   -7Х₂ - 9Х₁                    Х₃=0 при Х₂=6300/7=900

Х₄=   5000   - 10Х₂ - 5Х₁          Х₄=0 при Х₂=5000/10=500 min

F’=      0      - 200 Х₁-200 Х₂

Соответственно, проведем обмен  Х₂↔ Х₄ и определим решение:

Выражаю базисные переменные через свободные:

Х₄=5000 - 10Х₂ – 5Х₁ т.к. это уравнение содержит обе обмениваемые переменные, отсюда выражаю Х₂ и подставляю в остальные уравнения:

Х₂= 500 -  0,5Х₁ – 0,1Х₄;

Х₃= 6300 – 7(500 -  0,5Х₁ – 0,1Х₄) – 9Х₁;

F’= 0 -  200Х₁ – 200(500 -  0,5Х₁ – 0,1Х₄); -привожу подобные и получаю уравнения (9),(10) соответственно:

Х₂=    500         -0,5Х₁ – 0,1Х₄;

Х₃ =   2800       - 5,5Х₁ + 0,7Х₄; (9)

F’=   -100000    -100Х₁ + 20Х₄;  (10)

Решение:

Х₁=0   свободные                     Х₂= 500    базис                   F’=-100000

Х₄=0   переменные                   Х₃=2800

Анализ решения: решение  допустимое, т.к. Х_i≥0, где i=1..4

Неоптимальное, т.к. коэффициент  Х₁ в ц.ф. отрицателен, его дальнейшее увеличение приведет к уменьшению ц.ф.

 

3 этап. Вторая итерация  i=2.

Начнем увеличивать Х₁, т.к. коэффициент при нем отрицательный в ц.ф., т.е. Х₁≠0 переходит в базис.

Определю, какую из базисных переменных Х₂,Х₃ перевести в свободные, для этого определю какая из них быстрее обратится в ноль:

 

Х₂=  500 – 0,5Х₁ – 0,1Х₄         Х₂=0 при Х₁=500/0,5=1000

Х₃=2800 – 5,5Х₁ + 0,7Х₄         Х₃=0 при Х₁=2800/5,5=509,09 min

F’= -100000 – 100Х₁+ 20Х₄

Производим обмен Х₁↔Х₃ и определяем текущее решение, выразим базисные переменные через свободные:

Х₂=  500 – 0,5Х₁ – 0,1Х₄;      (11)      

Х₃=2800 – 5,5Х₁ + 0,7Х₄;      (12)     

F’= -100000 – 100Х₁+ 20Х₄;   (10)

Из уравнения (12), содержащего обе  обмениваемые переменные, выразим Х₁ и подставим в (11),(10):

Х₁= 509,09      – 0,182Х₃ + 0,127Х₄;

Х₂= 245,455     + 0,091Х₃ – 0,1635Х₄;

F’= -150909  + 18,2Х₃ + 13,7Х₄;  

Анализ решения:  Х₃=0   отсутствует резерв

                             Х₄=0    по сырью

Х₁=509,09 кг, план производства краски А

Х₂=245,455 кг, план производства краски Б

F’=-150909 → F=150909 y.e. -прибыль от реализации.

 

 

 

3. Решение задачи симплекс-методом (табличная реализация).

Мат. модель задачи составлена ранее и остается без изменения (п. 1.2).

1 этап: начальное приближение  – опорное решение.

Х₁=0   свободные               Х₃≠0    базис

Х₂=0   переменные             Х₄≠0

Воспользуемся м.м. задачи в стандартной форме (уравнения 6-8):

Z’= -Z = -300 Х₁- 500 Х₂;

9Х₁ + 7 Х₂ + Х₃ = 6300;

5Х₁ + 10Х₂ + Х₄ = 5000.

 

С помощью этих уравнений  выразим базисные переменные через свободные:

 

Х₃= 6300   – 7Х₂ -9Х₁;     

Х₄= 5000   - 10Х₂ - 5Х₁;             система уравнений (А)

Z’=   0        -200Х₁ – 200Х₂;

 

 

 

Используя (А), составим симплекс-таблицу:

Таблица 1.3.1

Ц.Ф. Базис	Свободные члены уравнений	Свободные переменные
		-Х1	-Х2
F’	0 -100000	200 -100	200 -20
Х3	6300 -3500	9 -3,5	7 -0,7
Х4	5000 500	5 0,5	10 0,1

 

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

1 этап, опорное решение:  Х₁=0   свободные              Х₃=6300    базис

                                          Х₂=0      переменные            Х₄=5000

Анализ решения: 1) все  элементы столбца свободных членов неотрицательны, а значит решение  допустимое;

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

2 этап. Первая итерация  i=1.

а) выбор разрешающего столбца: выбираю столбец, который соответствует  максимально положительному коэффициенту в строке ц.ф., помечаю его двойной чертой. В моей задаче это столбец –Х₂.

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

Таким образом, в моей задаче это строка Х₄, также помечаю двойной чертой.

в) Заполнение нижних углов  таблицы:

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

г) Формирование таблицы текущего решения:

• обмен переменных Х₂↔Х₄
• в верхний угол каждой клетки разрешающей строки и столбца заносятся вычисленные коэффициенты без изменения;
• В остальные клетки заносится сумма верхних и нижних коэффициентов аналогичной клетки предыдущей таблицы.

д) Формирование таблицы  текущего решения:

 

 

 

 

Ц.Ф. Базис	Свободные члены уравнений	Свободные переменные
		-Х1	-Х4
F’	-100000 -50960	100 -18,2	-20 12,74
Х3	2800 509,09	5,5 0,182	-0,7 0,1274
Х2	500 -254,8	0,5 -0,091	0,1 0,0637

Текущее решение:

Х₁=0   свободные                     Х₂= 500    базис                   F’= -10000