Решение задачи оптимального планирования работы технологических линий
Содержание
1. Содержательная постановка оптимизационной задачи
. Математическая модель в аналитическом и информационном виде
. Графический метод решения
. Определение диапазона дефицитности ресурсов bj,
динамики ОДР и дрейфа оптимума
. Решение задачи табличным симплекс-методом
. Решение задачи в среде MS Excel
. Факторы эффективности решения задачи исследования и
оптимального планирования операций
Литература
1.
Содержательная постановка оптимизационной задачи
В цеху по сборке изделий А, В, С, D работают четыре линии. Во время
сборки изделия А линию 1 не используют, а во время сборки изделия D используют
только линии 1 и 3. Эти технологические линии имеют ограничение времени работы
в сутки: линия 1 - 1000 мин, линия 2 - 600 мин, линия 3 - 780 мин, линия 4 -
800 мин.
В таблице 1 приведены продолжительности технологических операций на
линиях во время сборки изделий каждого вида.
Таблица 1
Изделие
|
Продолжительность
технологической операции, мин/изд.
|
|
Линия 1
|
Линия 2
|
Линия 3
|
Линия 4
|
A
|
-
|
1
|
3
|
1
|
B
|
2
|
5
|
1
|
10
|
C
|
3
|
4
|
10
|
20
|
D
|
50
|
-
|
12
|
-
|
Прибыль от продажи изделий: A - 6 y.e.; B - 5 y.e.; C - 6 y.e.; D - 5
y.e.
Определить наиболее выгодный суточный объем выпуска изделий каждого вида,
обеспечивающий максимум прибыли.
2.
Математическая модель в аналитическом и информационном виде
сj - норма расхода i-го вида ресурсов на
управляющую переменную xj
xj - управляющая переменная
bi - виды ресурсов
3.
Графический метод решения
Для данной системы ограничения построим область допустимых решений (ОДР)
которая образуется путем пересечения всех полуплоскостей системы ограничений,
т.е. любая точка ОДР (на границе и внутри области) является допустимым решением
задачи.
Пересечения полуплоскостей строим по точкам пересечения границ
полуплоскостей с осями координат.
При данных условиях ограничения, для построения области необходимо отбросить
две переменные (х3, х4).
Построим
ОДР и целевую функцию, соответствующую данным ограничениям.
Решение задачи методом обхода вершин ОДР
Вершина ОДР
|
Координаты вершины
|
Значения целевой функции F
|
Примечание
|
|
x1
|
x2
|
|
|
A
|
0
|
0,8
|
4
|
|
B
|
2,414
|
0,559
|
17,279
|
Max F
|
2,6
|
0
|
15,6
|
|
D
|
0
|
0
|
0
|
Min F
|
Сравнивая значения целевой функции F в вершинах ОДР, видим, что в точке B
(x1=2,414; x2=0,559) целевая функция достигает своего максимума. Следовательно,
оптимальным планом производства является выпуск изделий в объеме x1=241,4,
x2=55,9, при этом прибыль будет максимальной F=1727,9 у.е.
Решение задачи методом касательной.
Функция F представляет собой пучок параллельных прямых, каждая из которых
соответствует определенному значению функционала. Например, при 4,1x1+4,3x2=5
целевая функция соответствует прямой, пересекающей ОДР. Значение целевой
функции возрастает при параллельном перемещении прямой по направлению стрелки и
достигает максимального значения в вершине С, в которой график целевой функции
является касательной к ОДР.
Оптимальным решением задачи является значение:
х1 = 2,414, х2 = 0,559
f(2,414;0,559) = 17,279*100=1727,9 у.е.,
при этом ЦФ достигает своего максимума.
Определим устойчивость данного оптимального решения при изменении
коэффициентов целевой функции. То есть определим диапазон изменения
коэффициентов целевых функций, при которых оптимум остается неизменным (х1
= 2,414, х2 = 0,559).
Точка
оптимума образуется пересечением дефицитных ограничений 3 и 4.
Определим
диапазон устойчивости коэффициента C1.
С2=const=5.
Построим
графики ЦФ
при
С1=0,5 F1=0,5x1+5x2=4
при
С1=15 F2=15x1+5x2=39
Правая
часть ЦФ вычисляется путем подстановки координат точки оптимума B(2,414,0,559)
в данные уравнения.
Значение
ЦФ меняется в интервале от 4 до 39, образуется центральный пучок целевых
функций с центром в вершине B(2,414;0,559), при котором точка оптимума
устойчива. За пределами диапазона устойчивости С1 точка оптимума
будет меняться. При С1<0,5 угол наклона ЦФ становится таким, что
оптимум из вершины B дрейфует в вершину C. При С1>15 оптимум из
вершины B дрейфует в вершину A.
Определим
диапазон устойчивости коэффициента C2.
С1=const=6
Построим
графики ЦФ
при
С2=2 F3=6x1+2x2=15,6
при
С2=60 F4=6x1+60x2=48
Значение
ЦФ меняется в интервале от 15,6 до 48, образуется центральный пучок целевых
функций с центром в вершине B(2,414;0,559), при котором точка оптимума
устойчива. За пределами диапазона устойчивости С1 точка оптимума
будет меняться. При С1<2 угол наклона ЦФ становится таким, что
оптимум из вершины B дрейфует в вершину A. При С1>60 оптимум из
вершины B дрейфует в вершину C.
4.
Определение диапазона дефицитности ресурсов bj, динамики ОДР и
дрейфа оптимума
Точка оптимума, вершина B, образована пересечением двух дефицитных
ресурсов b3 и b4. Определим диапазон дефицитности ресурса
b3 b3min≤b3≤b3max
и определим дрейф точки оптимума.
При уменьшении b3 прямая перемещается параллельно самой себе и
достигает точки касания к вершине ОДР. При этом точка B дрейфует вдоль (4) и
перемещается в B1`, B1``, B1```. Дальнейшее
уменьшение ресурса b3 находится за пределами ОДР и он становится не
дефицитным. Ресурс, уменьшаясь, образует пучок параллельных прямых, b3min=0,8.
Увеличивая правую часть b3 строим пучок параллельных прямых,
приходим в B2`.3max= 13,1, отсюда следует 80≤b3≤1310
Определим диапазон дефицитности ресурса b4 b4min≤b4≤b4max
и определим дрейф точки оптимума.
При уменьшении b4, образуется пучок параллельных прямых,
предельное значение b4 определяется в вершине касания b4 с
ОДР. За пределами вершины касания b4 становится недефицитным. b4min=2,5.
Точка оптимума перемещается вдоль ограничения (3) и достигает точки B2`.
Увеличивая правую часть b4 строим пучок параллельных прямых,
приходим в B1`.4max= 10,3, отсюда следует 250≤b4≤1030
5. Решение
задачи табличным симплекс-методом
Решим
задачу табличным симплекс-методом, для этого запишем исходную задачу в
каноничной форме.
Запишем исходные данные канонической формы в компактную симплекс-таблицу.
(СТ №1)
Базис
|
bj
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
Элем. преобр.
|
X3
|
1000
|
0
|
2
|
1
|
0
|
0
|
0
|
-
|
600
|
1
|
5
|
0
|
1
|
0
|
0
|
-
|
X5
|
780
|
3
|
1
|
0
|
0
|
1
|
0
|
РС/3
|
X6
|
800
|
1
|
10
|
0
|
0
|
0
|
1
|
-
|
- Cj
|
0
|
-6
|
-5
|
0
|
0
|
0
|
0
|
-
|
Из СТ №1 непосредственно получаем решение: в базис входят
только те переменные, которые имеют «Жорданово исключение».=
(0,0,1000,600,780,800); F1=0
Базис не оптимален, так как существуют Cj < 0
Переходим к новому базису:
1. Вводим в базис переменную х1 т.к. Сj < 0.
Выбираем из них наименьшее.
2. Определяем разрешающий элемент, т.е. переменную, которая
вытесняется из базиса.
Базис
|
bj
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
Элем. преобр.
|
X3
|
1000
|
0
|
2
|
1
|
0
|
0
|
0
|
-
|
X4
|
600
|
1
|
5
|
0
|
1
|
0
|
0
|
II-PC
|
X1
|
260
|
0,333
|
0
|
0
|
0,333
|
0
|
РС
|
X6
|
800
|
1
|
10
|
0
|
0
|
0
|
1
|
IV-PC
|
- Cj
|
0
|
-6
|
-5
|
0
|
0
|
0
|
0
|
V+PC*6
|
(СТ №2)
Базис
|
bj
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
Элем. преобр.
|
X3
|
1000
|
0
|
2
|
1
|
0
|
0
|
0
|
-
|
X4
|
340
|
0
|
4,667
|
0
|
1
|
-0,333
|
0
|
-
|
X1
|
260
|
1
|
0,333
|
0
|
0
|
0,333
|
0
|
-
|
X6
|
540
|
0
|
9,667
|
0
|
0
|
0
|
1
|
РС/9,667
|
1560
|
0
|
-3
|
0
|
0
|
2
|
0
|
-
|
Из СТ №2 непосредственно получаем решение: в базис входят
только те переменные, которые имеют «Жорданово исключение».=
(260,0,1000,340,0,540); F2=1560
Базис не оптимален, так как существуют Cj < 0
Переходим к новому базису:
3. Вводим в базис переменную х2 т.к. Сj < 0.
Выбираем из них наименьшее.
4. Определяем разрешающий элемент, т.е. переменную, которая
вытесняется из базиса.
Базис
|
bj
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
Элем. преобр.
|
X3
|
1000
|
0
|
2
|
1
|
0
|
0
|
0
|
I-PC*2
|
X4
|
340
|
0
|
4,667
|
0
|
1
|
-0,333
|
0
|
II-PC*4,667
|
X1
|
260
|
1
|
0,333
|
0
|
0
|
0,333
|
0
|
III-PC*0,33
|
X2
|
55,862
|
0
|
1
|
0
|
0
|
-0,034
|
0,103
|
РС
|
- Cj
|
1560
|
0
|
-3
|
0
|
0
|
2
|
0
|
V+PC*3
|
(СТ №3)
bj
|
x1
|
x2
|
x3
|
x4
|
x5
|
x6
|
Элем. преобр.
|
X3
|
888,276
|
0
|
0
|
1
|
0
|
0,069
|
-0,207
|
-
|
X4
|
79,31
|
0
|
0
|
0
|
1
|
-0,172
|
-0,483
|
-
|
X1
|
241,379
|
1
|
0
|
0
|
0
|
0,345
|
-0,034
|
-
|
X2
|
55,862
|
0
|
1
|
0
|
0
|
-0,034
|
0,103
|
-
|
- Cj
|
1727,586
|
0
|
0
|
0
|
0
|
1,897
|
0,31
|
-
|
Базис оптимален так как нет Cj < 0
Из СТ №3 непосредственно получаем решение: в базис входят
только те переменные, которые имеют «Жорданово исключение».= (241,379; 55,862;
888,276; 79,31; 0; 0);3=1727,586 - максимальное значение F.
6. Решение
задачи в среде MS Excel
прибыль математический дефицитность оптимум
Проведем расчеты исходной задачи в Excel, с помощью «Поиска решений». При
этом математическая модель остается та же.
Составим табличную модель.
После составления табличной модели выбираем вкладку Данные à Поиск решения. Здесь мы указываем
все необходимые параметры и ограничения, после чего выбираем целевую ячейку H4
и нажимаем «Выполнить».
В результате получаем:
Полученное нами с помощью сервиса «Поиск решения» в Excel значение
совпадает с полученным решением табличного симплекс-метода. Исходя из него,
максимальное значение нашей функции составляет 1727,586 у.е.
Ответ: наиболее выгодный суточный объем выпуска изделий, при котором
максимальная прибыль составит 1727,586 у.е., будет получен при изготовлении
241,38 ед. изделий А, 55,86 ед. изделий В, 0 ед. изделий С и 0 ед. изделий D.
7. Факторы
эффективности решения задачи исследования и оптимального планирования операций
Анализируя полученное решение, можно прийти к выводу, что ограничение
времени работы в сутки линии 3 является ограничивающим фактором в получении
прибыли. Если увеличить время работы третьей линии на 460 минут, будет получена
суммарная прибыль в размере 2600 у.е.
Литература
1. Экономико-математические
методы и модели в управлении морским транспортом. Под редакцией Воевудского
Е.Н. - М. Транспорт, 1988 - 384 с.
2. Громовой
Э.П. Математические модели и методы в планировании и управлении на морском
транспорте - М. Транспорт, 1979 - 360 с.
. Воевудский
Е.Н. Управление на морском транспорте - М. Транспорт, 1993 - 366 с.