Список предметов
Оптимальный план производства (линейное программирование)
118 / 152
Уважаемые коллеги!
 Целями данного урока является не изложение теории из курса матпрограммирования, а более простая цель - показать практическое применение знаний, которые Вы получаете в процессе изучения раздела "математическое программирование" в курсе высшей математики. Поэтому изложение будет максимально простым, но не совсем "каноническим".

Задача

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


П1П2П3П4ОбъемП5
Р181081036009
Р2474618505
Р3433515003
Цена2530403533

Решение.
Обозначим через x1..x4 число изготавливаемых продуктов. Тогда условие задачи может быть записано в следующем виде:

25x1 + 30x2 + 40x3 + 35x4 → max
8x1 + 10x2 + 8x3 + 10x4 ≤ 3600
4x1 + 7x2 + 4x3 + 6x4 ≤ 1850
4x1 + 3x2 + 3x3 + 5x4 ≤ 1500
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥ 0

Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную y1, y2 и у3. Тогда общая оценка сырья, используемого на производство продукции, составит

3600y1 + 1850y2+ 1500y3 → min

Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида, т. е. y1, y2 и у3 должны удовлетворять следующей системе неравенств:
8y1 + 4y2+ 4y3 ≥ 25
10y1 + 7y2+ 3y3 ≥ 30
8y1 + 4y2+ 3y3 ≥ 40
10y1 + 6y2+ 5y3 ≥ 35
y1 ≥ 0
y2 ≥ 0
y3 ≥ 0

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

Приведем математическую модель задачи к каноническому виду.Для этого избавимся от знаков неравенств посредством ввода дополнительных переменных и замены знака неравенства на знак равенства. Дополнительная переменная добавляется для каждого неравенства, причем эта переменная указывается в целевой функции с нулевым коэффициентом. Правило ввода дополнительных переменных: при ">=" - переменная вводится в неравенство с коэффициентом (-1); при "<=" - с коэффициентом (+1).

25x1 + 30x2 + 40x3 + 35x4 - 0x5 - 0x6 - 0x7 → max
8x1 + 10x2 + 8x3 + 10x4 + x5 = 3600
4x1 + 7x2 + 4x3 + 6x4 + x6 = 1850
4x1 + 3x2 + 3x3 + 5x4 + x7 = 1500

Экономический смысл введенных дополнительных переменных - остатки соответствующих ресурсов каждого вида. Для решения задачи составим симплекс-таблицу.
Симплекс-таблица составляется так:
         В графе "Базис" записываются вектора переменных, принимаемые за базисные. На первом этапе это – A5, A6, A7. Базисными будут переменные, каждая из которых входит только в одно уравнение системы, и нет такого уравнения, в которое не входила бы хотя бы одна из базисных переменных.
         В следующий столбец  записываются коэффициенты целевой функции, соответствующие каждой переменной. Столбец В – столбец свободных членов. Далее идут столбцы коэффициентов Аi при  i –й переменной. 





25304035000
iБазисCBA1 A2 A3 A4 A5 A6 A7
1A503600810810100
2A6018504746010
3A7015004335001
4Fi-Ci0-25-30-40-35000

Под столбцом свободных членов записывается начальная оценка F0 = CiBi = 0*3600+0*1850+0*1500=0 .
Остальные оценки записываются под столбцами соответствующих векторов:
F1 - C1 = 0*8 + 0*4 + 0*4 - 25 = -25 
F2 - C2 = 0*10 + 0*7 + 0*3 - 30 = -30 
F3 - C3 = 0*8 + 0*4 + 0*3 - 40 = -40 
F4 - C4 = 0*10 + 0*6 + 0*5 - 35 = -35 
Следует отметить, что оценки для базисных векторов всегда равны нулю.

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

Шаг 2: Для отрицательных оценок вычисляются величины:

Θ1 = min{ Bi / Ai }= min{ 3600/8 ; 1850/4; 1500/4 } = min{450; 462.5; 375} = 375
Θ2 = min{ Bi / Ai }= min{ 3600/10 ; 1850/7; 1500/3 } = min{360; 264.29; 500} = 1850/7
Θ3 = min{ Bi / Ai }= min{ 3600/8 ; 1850/4; 1500/3 } = min{450; 462.5; 500} = 450
Θ4 = min{ Bi / Ai }= min{ 3600/10 ; 1850/6; 1500/5 } = min{360; 308.33; 300} = 300

Θ1 (F1 - C1 ) = 375 * (-25) = - 9375
Θ2 (F2 - C2 ) = 1850/7 * (-30) = - 55500/7
Θ3 (F3 - C3 ) = 450 * (-40) = - 18000
Θ4 (F4 - C4 ) = 300 * (-35) = - 10500

Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае  минимально -18000, поэтому выбираем третий столбец, а в качестве так называемого разрешающего элемента выбирается первый элемент третьего столбца (по значению Θ3 ) – 8 (выделен в таблице).

 Шаг 3: Третья строка таблицы делится на 8 и вычитается из остальных строк с коэффициентами, позволяющими ввести в базис третий столбец. В сущности, применяется метод исключения неизвестных, известный как метод Жордана – Гаусса..





25304035000
iБазисCBA1 A2 A3 A4 A5 A6 A7
1A340
45011,2511,251/800
2A6012.5
0
0.5
0
0.25
-1/8
0.25
0
3A70501/3
-0,25
0
5/12-1/8
01/3
4Fi-Ci
01520015500












В итоге получаем все положительные оценки Fi - Ci, что означает оптимальность полученного плана. То есть необходимо выпускать 450 единиц продукции третьего вида, чтобы выручка была максимальной и составляла 18 тысяч.

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

25x1 + 30x2 + 40x3 + 35x4 + 33x5 → max
8x1 + 10x2 + 8x3 + 10x4 + 9x5 ≤ 3600
4x1 + 7x2 + 4x3 + 6x4 + 5x5 ≤ 1850
4x1 + 3x2 + 3x3 + 5x4 + 3x5 ≤ 1500
x1 ≥ 0
x2 ≥ 0
x3 ≥ 0
x4 ≥ 0
x5 ≥ 0

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

25x1 + 30x2 + 40x3 + 35x4 + 33x5 - 0x6 - 0x7 - 0x8 → max
8x1 + 10x2 + 8x3 + 10x4 + 9x5 + x6 = 3600
4x1 + 7x2 + 4x3 + 6x4 + 5x5 + x7 = 1850
4x1 + 3x2 + 3x3 + 5x4 + 3x5 + x8 = 1500





2530403533000
iБазисCBA1 A2 A3 A4 A5 A6 A7 A8
1A6036008108109
100
2A701850474650
10
3A8015004335300
1
4Fi-Ci
0-25-30-40-35-33000













Θ1 = min{ Bi / Ai }= min{ 3600/8 ; 1850/4; 1500/4 } = min{450; 462.5; 375} = 375
Θ2 = min{ Bi / Ai }= min{ 3600/10 ; 1850/7; 1500/3 } = min{360; 264.29; 500} = 1850/7
Θ3 = min{ Bi / Ai }= min{ 3600/8 ; 1850/4; 1500/3 } = min{450; 462.5; 500} = 450
Θ4 = min{ Bi / Ai }= min{ 3600/10 ; 1850/6; 1500/5 } = min{360; 308.33; 300} = 300
Θ5 = min{ Bi / Ai }= min{ 3600/9 ; 1850/5; 1500/3 } = min{400; 370; 500} = 370

Θ1 (F1 - C1 ) = 375 * (-25) = - 9375
Θ2 (F2 - C2 ) = 1850/7 * (-30) = - 55500/7
Θ3 (F3 - C3 ) = 450 * (-40) = - 18000
Θ4 (F4 - C4 ) = 300 * (-35) = - 10500
Θ5 (F5 - C5 ) = 370 * (-33) = - 12210

Из этих элементов выбирается тот, для которого вычисленное произведение минимально, в нашем случае  минимально -18000, поэтому выбираем третий столбец, а в качестве так называемого разрешающего элемента выбирается первый элемент третьего столбца (по значению Θ3 ) – 8 (выделен в таблице).





2530403533000
iБазисCBA1 A2 A3 A4 A5 A6 A7 A8
1A34045011.2511,251,125
1/800
2A7012,5
0
0,5
0
0,25
1/8
-1/8
1/40
3A80501/3
-0,25
0
5/12-1/8
-1/8
0
1/3
4Fi-Ci
0152001512
5
00













В итоге получаем все положительные оценки Fi - Ci, что означает оптимальность полученного плана. То есть необходимо выпускать 450 единиц продукции третьего вида, чтобы выручка была максимальной и составляла 18 тысяч.
Таким образом, введение нового продукта никак не повлияет на стратегию предприятия по максимизации выручки.
0  


 Транспортная задача | Описание курса | Теория вероятности