Математические методы производственных систем
Содержание.
- Минимизация затрат на выполнение комплекса работ при заданном времени.
- Расчетная часть
- Минимизация времени выполнения комплекса работ при заданных затратах
- Минимизация суммарных затрат по комплексу работ и обьекту
Исходные данные.
MN-83,значит A=3.
Дано:
Комплекс, состоящий из 8 работ, порядок выполнения которых определяется сетевым графиком.
По работам сетевого графика установлены следующие значения характеристик:
Таблица 1
Порядковый № работы
Характеристики |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
аk |
15 |
20 |
10 |
15 |
10 |
15 |
20 |
10 |
вk |
-1 |
-2 |
-3 |
-4 |
-1 |
-2 |
-3 |
-4 |
dk |
4 |
3 |
2 |
1 |
4 |
3 |
2 |
1 |
Dk |
10 |
8 |
3 |
3 |
9 |
7 |
6 |
2 |
Расчетная часть
1.Выпишем все пути, ведущие
из источника в сток сетевого
графика, и вычислим
L₁{1;2;5;8} 4+3+4+1=12 10+8+9+2=29
L₂{3;5;8} 2+4+1=7 3+9+2=14
L₃{4;6;8} 1+3+1=5 3+7+2=12
L₄{1;8} 4+1=5 10+2=12
L₅{1;2;5;6;7} 4+3+4+3+2=16 10+8+9+7+6=40
L₆ {3;5;6;7} 2+4+3+2=11 3+9+7+6=25
L ₇{4;7} 1+2=3 3+6=9
Tmin=16 Tmax=40
Таким образом, время выполнения
комплекса работ может
16≤ T ≤40
2.Построим математическую модель данной задачи.
2.1 Строим систему ограничений:
1 гр. dx=t₁ ≥4 ; t₂ ≥3 ; t₃ ≥2 ; t₄ ≥1 ; t₅ ≥4; t₆ ≥3 ; t₇ ≥2 ; t₈≥1
2гр. Dk= t₁ ≤ 10 ; t₂ ≤ 8 ; t₃ ≤ 3 ; t₄ ≤ 3 ; t₅ ≤ 9 ; t₆ ≤ 7 ;t₇ ≤ 6 ; t₈≤ 2
Система ограничений примет следующий вид:
τ₁≤6 ; τ₂≤5 ; τ₃≤1 ; τ₄≤2 ; τ₅≤5 ; τ₆≤4 ; τ₇≤4 ; τ₈≤1
t₁+t₂+t₅+t₈≤T
t₃+t₅+t₈≤T
t₄+t₆+t₈≤T
t₁+t₈≤T
t₁+t₂+t₅+t₆+t₇≤T
t₃+t₅+t₆+t₇≤T
t₄+t₇≤T
τ₁=t₁-4 » t₁=τ+4
τ₂=t₂-3 » t₂=τ₂+3
τ₃=t₃-2 » t₃=τ₃+2
τ₄=t₄-1 » t₄=τ₄+1
τ₅=t₅-4 » t₅=τ₅+4
τ₆=t₆-3 » t₆=τ₆+
τ₇=t₇-2 » t₇=τ₇+2
τ₈=t₈-1 » t₈=τ₈+1
После несложных преобразований система ограничений примет вид:
t₁+t₂+t₅+t₈≤T-12
t₃+t₅+t₈≤T-7
t₄+t₆+t₈≤T-4
t₁+t₈≤T-5
t₁+t₂+t₅+t₆+t₇≤T-16
t₃+t₅+t₆+t₇≤T-11
t₄+t₇≤T-3
2.2.Строим целевую функцию по формуле: Z=
Целевая функция при основных переменных имеет вид
Z=15+20+10+15+10+15+20+10=100
100+(-1)t₁+(-2)t₂+(-3)t₃+(-4)
При замене tkᵥ на τk получим:
Z=100+(-1)(τ₁+4)+(-2)(τ₂+3)+(-
+(-4)(τ₈+1)→min
или
Z=60-τ₁ - 2τ₂ - 3τ₃ - 4τ₄ - τ₅ - 2τ₆ - 3τ₇ - 4τ₈→min
Исключив константу, полученную целевую функцию запишем в следующем виде:
Z'=τ₁+2τ₂+3τ₃+4τ₄+τ₅+2τ₆+3τ₇+
Целевая функция Z будет стремиться к минимуму при Z', стремящемуся к максимуму.
3.Представим исходную задачу в матричной форме.
-Ԏ₁ |
-Ԏ₂ |
-Ԏ₃ |
-Ԏ₄ |
-Ԏ₅ |
-Ԏ₆ |
-Ԏ₇ |
-Ԏ₈ |
b | |
y₁ |
1 |
6 | |||||||
y₂ |
1 |
5 | |||||||
y₃ |
1 |
1 | |||||||
y₄ |
1 |
2 | |||||||
y₅ |
1 |
5 | |||||||
y₆ |
1 |
4 | |||||||
y₇ |
1 |
4 | |||||||
y₈ |
1 |
1 | |||||||
y₉ |
1 |
1 |
1 |
1 |
T-12 | ||||
y₁₀ |
1 |
1 |
1 |
T-7 | |||||
y₁₁ |
1 |
1 |
1 |
T-4 | |||||
y₁₂ |
1 |
1 |
T-5 | ||||||
y₁₃ |
1 |
1 |
1 |
1 |
T-11 | ||||
y₁₄ |
1 |
1 |
1 |
1 |
1 |
T-16 | |||
y₁₅ |
1 |
1 |
T-3 | ||||||
Z дв |
-1 |
-2 |
-3 |
-4 |
-1 |
-2 |
-3 |
-4 |
0 max |
Таблица 2.
Составим двойственную(
Таблица 3.
-y₁ |
-y₂ |
-y₃ |
-y₄ |
-y₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
τ₁ |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
τ₂ |
-1 |
-1 |
-1 |
-2 | ||||||||||||
τ₃ |
-1 |
-1 |
-1 |
-3 | ||||||||||||
τ₄ |
-1 |
-1 |
-1 |
-4 | ||||||||||||
τ₅ |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
-6 |
-5 |
-1 |
-2 |
-5 |
-4 |
-4 |
-1 |
12-Т |
7-Т |
4-Т |
5-Т |
11-Т |
16-Т |
3-Т |
0 min |
Перейдем от задачи на минимум
к задаче на максимум. Для этого
целевую функцию умножим на -1.
Таблица 4.
-y₁ |
-y₂ |
-y₃ |
-y₄ |
-y₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
τ₁ |
-1 |
-1 |
-1 |
-1 |
-1 | |||||||||||
τ₂ |
-1 |
-1 |
-1 |
-2 | ||||||||||||
τ₃ |
-1 |
-1 |
-1 |
-3 | ||||||||||||
τ₄ |
-1 |
-1 |
-1 |
-4 | ||||||||||||
τ₅ |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-12 |
Т-7 |
Т-4 |
Т-5 |
Т-11 |
Т-16 |
Т-3 |
0 max |
Полученный план(табл.4) содержит отрицательные элементы в последнем столбце, поэтому не является опорным планом и его необходимо преобразовать.Процесс преобразования интерационный ( с помощью симплекс-метода).Необходимо воспользоваться правилом получения опорного плана.
1 шаг. Выбираем ведущими
1-ю строку и 1-ый столбец (табл.5) и произведем
пересчет элементов, используя правило
пересчета симплексного метода.
Таблица 5.
-τ₁ |
-y₂ |
-y₃ |
-y₄ |
-y₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
у₁ |
-1 |
1 |
1 |
1 |
1 | |||||||||||
τ₂ |
-1 |
-1 |
-1 |
-2 | ||||||||||||
τ₃ |
-1 |
-1 |
-1 |
-3 | ||||||||||||
τ₄ |
-1 |
-1 |
-1 |
-4 | ||||||||||||
τ₅ |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-18 |
Т-7 |
Т-4 |
Т-11 |
Т-11 |
Т-22 |
Т-3 |
6 max |
2шаг.Выберем ведущими 2-ю строку
и 2-й столбец(табл.5) и произведем пересчет
элементов.
Таблица 6.
-τ₁ |
-τ₂ |
-y₃ |
-y₄ |
-y₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
у₁ |
-1 |
1 |
1 |
1 |
1 | |||||||||||
у₂ |
-1 |
1 |
1 |
2 | ||||||||||||
τ₃ |
-1 |
-1 |
-1 |
-3 | ||||||||||||
τ₄ |
-1 |
-1 |
-1 |
-4 | ||||||||||||
τ₅ |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-23 |
Т-7 |
Т-4 |
Т-11 |
Т-11 |
Т-27 |
Т-3 |
-16 max |
3 шаг. Выберем ведущими 3-ю строку
и 3-й столбец (табл.6) и произведем
пересчет элементов.
Таблица 7.
-τ₁ |
-τ₂ |
-τ₃ |
-y₄ |
-y₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
у₁ |
-1 |
1 |
1 |
1 |
1 | |||||||||||
у₂ |
-1 |
1 |
1 |
2 | ||||||||||||
у₃ |
-1 |
1 |
1 |
3 | ||||||||||||
τ₄ |
-1 |
-1 |
-1 |
-4 | ||||||||||||
τ₅ |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-23 |
Т-8 |
Т-4 |
Т-11 |
Т-12 |
Т-27 |
Т-3 |
-19 max |
4 шаг.Выберем ведущими 4-й столбец и 4-ю строку (табл.7) и произведем пересчет элементов.
Таблица 8.
-τ₁ |
-τ₂ |
-τ₃ |
-τ₄ |
-y₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
у₁ |
-1 |
1 |
1 |
1 |
1 | |||||||||||
у₂ |
-1 |
1 |
1 |
2 | ||||||||||||
у₃ |
-1 |
1 |
1 |
3 | ||||||||||||
у₄ |
-1 |
1 |
1 |
4 | ||||||||||||
τ₅ |
-1 |
-1 |
-1 |
-1 |
-1 |
-1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-23 |
Т-8 |
Т-6 |
Т-11 |
Т-12 |
Т-27 |
Т-5 |
-27 max |
5 шаг.Выберем ведущими 5-й столбец и 5 строку (табл.8) и произведем пересчет элементов.
Таблица 9.
-τ₁ |
-τ₂ |
-τ₃ |
-τ₄ |
-τ₅ |
-y₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
у₁ |
-1 |
1 |
1 |
1 |
1 | |||||||||||
у₂ |
-1 |
1 |
1 |
2 | ||||||||||||
у₃ |
-1 |
1 |
1 |
3 | ||||||||||||
у₄ |
-1 |
1 |
1 |
4 | ||||||||||||
у₅ |
-1 |
1 |
1 |
1 |
1 |
1 | ||||||||||
τ₆ |
-1 |
-1 |
-1 |
-1 |
-2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв. |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-28 |
Т-13 |
Т-6 |
Т-11 |
Т-17 |
Т-32 |
Т-5 |
32 max |
6 шаг.Выберем ведущими 6-й столбец и 6 строку (табл. 9 ) и произведем пересчет элементов.
Таблица 10.
-τ₁ |
-τ₂ |
-τ₃ |
-τ₄ |
-τ₅ |
-τ₆ |
-y₇ |
-y₈ |
-yֹ₉ |
-y₁₀ |
-y₁₁ |
-y₁₂ |
-y₁₃ |
-y₁₄ |
-y₁₅ |
b | |
у₁ |
-1 |
1 |
1 |
1 |
1 | |||||||||||
у₂ |
-1 |
1 |
1 |
2 | ||||||||||||
у₃ |
-1 |
1 |
1 |
3 | ||||||||||||
у₄ |
-1 |
1 |
1 |
4 | ||||||||||||
у₅ |
-1 |
1 |
1 |
1 |
1 |
1 | ||||||||||
у₆ |
-1 |
1 |
1 |
1 |
2 | |||||||||||
τ₇ |
-1 |
-1 |
-1 |
-1 |
-3 | |||||||||||
τ₈ |
-1 |
-1 |
-1 |
-1 |
-1 |
-4 | ||||||||||
Z дв |
6 |
5 |
1 |
2 |
5 |
4 |
4 |
1 |
Т-28 |
Т-13 |
Т-10 |
Т-11 |
Т-21 |
Т-36 |
Т-5 |
40 max |

- Математические методы решения задачи о получении оптимального плана перевозок (транспортной задачи)
- Математические методы решения задач оптимального размещения предприятий
- Математические модели
- Математические модели
- Математические модели
- Математические модели в маркетинге
- Математические модели в образовании
- Математические методы и модели исследования операций
- Математические методы и модели принятия решений в коммерческой деятельности
- Математические методы и модели принятия решений в коммерческой деятельности
- Математические методы исследования в экономике
- Математические методы исследования операций в экономике
- Математические методы, их виды
- Математические методы Метод Жардана-Гаусса