Информатика. Боброва Л.В - 23 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

23
Решение задачи включает три этапа:
1. Построение математической модели.
2. Построение начального плана решения.
3. Оптимизация начального плана.
3.2.1. Построение математической модели
Обозначим
Х
ij
– количество продукции, отправляемой со склада i в магазин j:
C
ij
– стоимость перевозки единицы продукции со склада i в магазин j.
Математическая модель будет состоять из ряда ограничений:
а) исходя из физического смысла задачи (количество и стоимость продукции
не могут быть отрицательными величинами)
Х
ij
≥ 0; C
ij
≥ 0. (1)
б) ограничения по предложению (со складов нельзя вывести продукции
больше, чем там имеется):
⎪
⎩
⎪
⎨
⎧
≤++++
≤++++
≤
+
+++
20
25
15
3534333231
2524232221
1514131211
XXXXX
XXXXX
XXXXX
(2)
в) ограничения по спросу (в магазины следует завести не меньше
продукции, чем им требуется):
⎪
⎪
⎪
⎩
⎪
⎪
⎪
⎨
⎧
≥++
≥++
≥++
≥++
≥++
15
8
5
12
20
352515
342414
332313
322212
312111
XXX
XXX
XXX
XXX
XXX
(3)
Общая стоимость перевозок (целевая функция) равна:
XXXXX
XXXXX
XXXXXX
Z
i
ij
j
3534333231
2524232221
1514131211
3
1
5
1
ij
34184
34215
24301
C
⋅+⋅+⋅+⋅++
+⋅+⋅+⋅+⋅++
+⋅+⋅+⋅+⋅+⋅=
∑∑
=
==
(4)
Необходимо определить такие значения переменных
X
ij
, которые
удовлетворяют ограничениям (1), (2) и (3) и обращают в минимум целевую
функцию Z (4). В такой постановке задача является транспортной задачей
линейного программирования.
Необходимым и достаточным условием разрешимости транспортной задачи
является условие баланса:
∑∑
==
=
5
1
3
1 j
j
i
i
mS
(5)
где
∑
=
3
1i
i
S
- суммарное количество продукции на складах

Страницы