ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.04.2021
Просмотров: 908
Скачиваний: 4
41
13
23
33
450,
x
x
x
+
+
=
14
24
34
100.
x
x
x
+
+
=
Неотрицательность
объемов
поставок
:
0,
1...3,
1...4
ik
x
i
k
≥
=
=
.
(3)
Задача
состоит
в
минимизации
суммарных
расходов
на
производство
и
пе
-
ревозку
.
Поэтому
в
качестве
целевой
функции
получим
следующее
выра
-
жение
:
(
) (
)
(
)
11
12
13
14
21
22
23
24
31
32
33
34
11
12
13
14
21
22
23
24
31
32
33
34
9
8
2
3
4
6
5
2
3
4
5
8
max.
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+ +
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
→
(4)
Таким
образом
,
целевая
функция
(4)
и
ограничения
(1–3)
представ
-
ляют
собой
математическую
модель
для
решения
поставленной
задачи
.
В
случае
,
когда
необходимо
минимизировать
только
транспортные
расходы
,
из
целевой
функции
исключается
выражение
,
описывающее
про
-
изводственные
затраты
.
Целевая
функция
в
этом
случае
примет
вид
:
11
12
13
14
21
22
23
24
31
32
33
34
3
4
6
5
2
3
4
5
8
max.
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
+
+
+
+
+
+
+
+
+
→
(4`)
При
этом
все
ограничения
останутся
прежними
.
Задача
2.
Строительный
песок
добывается
в
трёх
карьерах
и
достав
-
ляется
на
четыре
строительные
площадки
.
Данные
о
производительности
за
день
(
a
i
в
тоннах
),
потребностях
в
песке
строительных
площадок
(
b
k
в
тоннах
),
затратах
на
добычу
песка
(
d
i
в
р
./
т
)
и
транспортных
расходах
(
c
ik
)
приведены
в
следующей
таблице
.
b
k
a
i
40 35 30 45
d
i
46
34
40
4
1
3
3
1
5
2
6
9
5
4
4
2
3
1
Недостающее
количество
песка
– 30
т
в
день
–
можно
обеспечить
следующими
тремя
путями
:
I –
увеличение
производительности
первого
карьера
,
что
повлечёт
за
собой
дополнительные
затраты
в
3
р
.
на
добычу
1
т
сверх
плана
;
II –
увеличение
производительности
второго
карьера
с
дополнитель
-
ными
затратами
в
2
р
./
т
сверх
плана
;
III –
эксплуатация
нового
карьера
с
общими
запасами
30
тонн
,
затра
-
тами
на
добычу
5
р
./
т
и
на
транспортировку
к
указанным
строительным
площадкам
:
c
41
= 2,
c
42
= 3,
c
43
= 1,
c
44
= 2 (
р
./
т
).
Построить
модель
определения
плана
закрепления
строительных
пло
-
щадок
за
карьерами
и
оптимального
варианта
расширения
поставок
песка
.
42
Решение
.
Обозначим
через
x
ik
объем
поставки
продукции
от
i
-
го
карьера
на
k
-
ю
строительную
площадку
.
Данная
транспортная
задача
не
является
сбалансированной
(
45
30
35
40
40
34
46
+
+
+
≤
+
+
).
Поэтому
в
за
-
даче
без
дополнительных
условий
(I–III)
ограничения
на
выпуск
продук
-
ции
будут
выглядеть
следующим
образом
:
11
12
13
14
46,
x
x
x
x
+
+
+
=
21
22
23
24
34,
x
x
x
x
+
+
+
=
(1)
31
32
33
34
40.
x
x
x
x
+
+
+
=
Ограничения
на
потребление
продукции
:
40
31
21
11
≤
+
+
x
x
x
,
35
32
22
12
≤
+
+
x
x
x
,
(2)
30
33
23
13
≤
+
+
x
x
x
,
14
24
34
45.
x
x
x
+
+
≤
Неотрицательность
объемов
поставок
:
0,
1...3,
1...4.
ik
x
i
k
≥
=
=
(3)
Задача
состоит
в
минимизации
суммарных
расходов
на
производство
и
перевозку
.
Поэтому
в
качестве
целевой
функции
получим
следующее
вы
-
ражение
:
(
)
(
) (
)
11
12
13
14
21
22
23
24
31
32
33
34
11
12
13
14
21
22
23
24
31
32
33
34
2
3
4
3
2
5
6
4
3
5
9
4
min.
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
→
(4)
Варианты
расширения
поставок
фактически
необходимы
для
того
,
чтобы
сбалансировать
задачу
и
обеспечить
потребности
строительных
площадок
.
Поэтому
для
того
чтобы
учесть
данные
варианты
,
введем
новые
переменные
и
изменим
ограничения
(1–2)
и
целевую
функцию
(4).
Пусть
x
4k
–
объем
поставки
песка
из
нового
четвертого
карьера
на
k
-
ю
строительную
площадку
;
z
1
–
объем
дополнительного
производства
на
первом
карьере
,
z
2
–
объем
дополнительного
производства
на
втором
карь
-
ере
.
Тогда
ограничения
(1)
будут
заменены
на
следующие
:
1
14
13
12
11
46
z
x
x
x
x
+
≤
+
+
+
,
2
24
23
22
21
34
z
x
x
x
x
+
≤
+
+
+
,
(1`)
40
34
33
32
31
≤
+
+
+
x
x
x
x
,
41
42
43
44
30.
x
x
x
x
+
+
+
≤
Ограничения
(2)
на
следующие
:
11
21
31
40,
x
x
x
+
+
=
12
22
32
35,
x
x
x
+
+
=
(2`)
43
13
23
33
30,
x
x
x
+
+
=
14
24
34
45.
x
x
x
+
+
=
Неотрицательность
объемов
поставок
:
1
2
0,
1...4,
1...4; ,
0.
ik
x
i
k
z z
≥
=
=
≥
(3`)
Целевая
функция
примет
вид
:
(
)
(
)
(
)
11
12
13
14
1
21
22
23
24
2
31
32
33
34
11
12
13
14
21
22
23
24
31
32
33
34
41
42
43
44
02
5
3
5
4
3
2
5
6
4
3
5
9
4
2
3
2
min.
x
x
x
x
z
x
x
x
x
z
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
→
(4`)
Задача
3.
Первый
склад
(
S
1
)
имеет
сталь
двух
марок
: 3000
т
марки
«
А
»
и
4000
т
марки
«
Б
».
Второй
склад
(
S
2
)
также
имеет
сталь
двух
марок
:
5000
т
марки
«
А
»
и
2000
т
марки
«
Б
».
Сталь
должна
быть
вывезена
в
два
пункта
потребления
:
в
пункт
P
1
необходимо
поставить
2000
т
стали
марки
«
А
», 3000
т
марки
«
Б
»
и
остальные
2000
т
стали
любой
марки
.
Аналогично
второй
пункт
потребления
P
2
должен
получить
6250
т
стали
,
из
них
1000
т
стали
марки
«
А
»
и
1500
т
стали
марки
«
Б
».
Известно
,
что
2000
т
стали
марки
«
А
»
могут
быть
заменены
на
1600
т
стали
марки
«
Б
» (
но
не
на
-
оборот
).
Стоимость
перевозок
в
рублях
за
тонну
составляет
:
из
пункта
S
1
в
пункты
P
1
и
P
2
1
р
.
и
1,5
р
.,
из
пункта
S
2
в
P
1
и
P
2
соответственно
2
р
.
и
1
р
.
Составить
модель
оптимального
плана
перевозок
.
Решение
.
Обозначим
через
g
ik
x
объем
поставки
стали
g
-
й
марки
из
i
-
го
склада
на
k
-
й
пункт
потребления
.
Подобные
задачи
(
со
взаимозаме
-
няемыми
ресурсами
)
решаются
путем
выражения
объемов
одного
ресурса
в
единицах
другого
.
Например
,
в
данной
задаче
выпишем
все
ограничения
в
единицах
стали
марки
«
Б
».
В
таблице
приведены
основные
параметры
задачи
,
выраженные
в
единицах
стали
марки
«
Б
».
Тип
ограничения
Марка
стали
В
исходных
едини
-
цах
В
единицах
стали
марки
«
Б
»
марка
«
А
» 3000
2400
Запасы
на
складе
S
1
марка
«
Б
» 4000
4000
марка
«
А
» 5000
4000
Запасы
на
складе
S
2
марка
«
Б
» 2000
2000
марка
«
А
» 2000
1600
марка
«
Б
» 3000
3000
Потребность
1-
го
пункта
потребления
любой
марки
2000
1600*
марка
«
А
» 1000
800
марка
«
Б
» 1500
1500
Потребность
2-
го
пункта
потребления
любой
марки
3750
3000*
•
В
качестве
стали
«
любой
марки
»
логично
выбрать
сталь
марки
«
А
»,
ко
-
торую
затем
можно
заменить
на
меньшее
количество
стали
марки
«
Б
».
44
Как
видим
,
общая
потребность
в
стали
обоих
пунктов
потребления
составляет
11 500
тонн
(
в
единицах
стали
марки
«
Б
»),
в
то
время
как
об
-
щий
запас
(
обоих
складов
)
составляет
12 400
тонн
.
Задача
не
является
сба
-
лансированной
.
Тогда
ограничения
на
наличие
ресурсов
будут
выглядеть
следующим
образом
:
3000
12
11
≤
+
A
A
x
x
,
4000
12
11
≤
+
B
B
x
x
,
(1)
5000
22
21
≤
+
A
A
x
x
,
21
22
2000.
B
B
x
x
+
≤
Ограничения
на
потребление
стали
марки
«
Б
» (
т
.
к
.
она
не
заменима
маркой
«
А
»):
11
21
3000,
B
B
x
x
+
≥
(2)
12
22
1500.
B
B
x
x
+
≥
C
таль
марки
«
А
»,
как
и
остаток
«
любой
марки
»,
может
быть
замене
-
на
сталью
марки
«
Б
»,
поэтому
к
ограничениям
(2)
для
каждого
склада
не
-
обходимо
добавить
ограничения
на
общее
количество
поставляемой
стали
всех
марок
,
выраженное
в
единицах
стали
марки
«
Б
»:
(
) (
)
11
21
11
21
0,8
6200,
A
A
B
B
x
x
x
x
+
+
+
=
(3)
(
) (
)
12
22
12
22
0,8
5300.
A
A
B
B
x
x
x
x
+
+
+
=
Здесь
6200
и
5300 –
общая
потребность
соответственно
1-
го
и
2-
го
пунктов
потребления
стали
обеих
марок
,
выраженная
в
единицах
стали
марки
«
Б
»
(
подробнее
–
см
.
табл
.
к
задаче
3),
а
2000
1600
8
,
0
=
–
коэффициент
перевода
стали
марки
«
А
»
в
сталь
марки
«
Б
».
Неотрицательность
объемов
поставок
:
{
}
"
Б
"
,
"
А
"
,
2
..
1
,
2
..
1
,
0
∈
=
=
≥
g
k
i
x
g
ik
. (4)
Задача
состоит
в
минимизации
суммарных
расходов
на
производство
и
перевозку
.
Поэтому
в
качестве
целевой
функции
получим
следующее
выражение
:
(
)
(
) (
) (
)
11
11
12
12
21
21
22
22
1,5
2
min.
A
B
A
B
A
B
A
B
x
x
x
x
x
x
x
x
+
+
+
+
+
+
+
→
(5)
Целевая
функция
(5)
и
ограничения
(1–4)
представляют
собой
мате
-
матическую
модель
для
решения
поставленной
задачи
.
Задача
4.
Компания
«
Рекорд
»
имеет
4
различных
сборочных
линии
на
своём
главном
заводе
.
Управляющий
производством
имеет
5
служащих
45
и
желает
назначить
по
одному
служащему
к
каждой
из
сборочных
линий
.
Каждый
из
этих
служащих
может
работать
на
любой
сборочной
линии
,
но
с
различными
затратами
,
связанными
с
индивидуальным
опытом
и
мастер
-
ством
.
Эти
затраты
приведены
в
таблице
.
Сборочная
линия
Сужащий
1 2 3 4
Служащий
1
Служащий
2
Служащий
3
Служащий
4
Служащий
5
23
18
25
20
16
19
22
20
24
18
22
20
22
24
20
27
18
30
28
25
Каким
образом
следует
управляющему
производством
прикрепить
служащих
к
сборочным
линиям
с
тем
,
чтобы
минимизировать
общие
за
-
траты
?
Решение
.
Введем
переменные
{ }
1
,
0
∈
ik
x
следующим
образом
:
x
ik
= 1,
если
i
-
й
служащий
назначается
на
k
-
ю
производственную
линию
,
в
про
-
тивном
случае
x
ik
= 0.
Данная
задача
не
является
сбалансированной
–
коли
-
чество
служащих
больше
количества
производственных
линий
.
Тогда
ог
-
раничения
задачи
будут
выглядеть
следующим
образом
:
4
1
1,
1...5
ik
k
x
i
=
≤
=
∑
(1)
–
сотрудник
не
может
быть
назначен
на
две
линии
одновременно
,
кроме
того
,
один
из
сотрудников
останется
неназначенным
;
5
1
1,
1...4
ik
i
x
k
=
=
=
∑
(2)
–
на
каждую
линию
обязательно
будет
назначен
один
сотрудник
;
{ }
1
,
0
∈
ik
x
(3)
–
ограничение
на
переменные
по
условию
.
Задача
состоит
в
минимизации
общих
затрат
на
производство
.
По
-
этому
в
качестве
целевой
функции
получим
следующее
выражение
:
11
12
13
14
21
22
23
24
31
32
33
34
41
42
43
44
51
52
53
54
23
19
22
27
18
22
20
18
25
20
22
30
20
24
24
28
16
18
20
25
min.
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
→
(4)