Лекция Экономикоматематическая модель транспортной задачи

• Название: Лекция Экономикоматематическая модель транспортной задачи
• Дата: 18.01.2023
• Размер: 1.63 Mb.
• Имя файла: Lekcija111.pdf
• Тип: Лекция; #893356

1
Лекция 1.
Экономико-математическая модель транспортной задачи
1. Общие понятия
Математическое программирование ("планирование") – это направление математики, изучающее методы отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются в экономических, организационных, военных и других системах для решения так называемых распределительных задач.
Распределительные задачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности.
При построении математической модели в этом случае можно выделить следующие основные этапы:
1. Определение цели решения задачи, т.е. чего хотят добиться, решая данную задачу.
2. Определение параметров модели, т.е. заранее известных фиксированных факторов, на значение которых исследователь не влияет.
3. Формирование управляющих переменных, значения которых являются решением задачи и при изменении которых можно достичь поставленной цели.
4. Определение области допустимых решений, т.е. ограничений, которым должны удовлетворять управляющие переменные.
5. Выявление неизвестных факторов, т.е. величин, которые могут изменяться случайным или неопределенным образом.
6. Выражение цели через управляющие переменные, параметры и неизвестные факторы, т.е. формирование целевой функции, называемой также критерием эффективности или критерием оптимальности задачи.
С учетом перечисленных выше этапов построения математической модели введем следующие условные обозначения:
a − параметры модели;
x − управляющие переменные или решения;
X − область допустимых решений (ОДР);
ξ
− случайные или неопределенные факторы;

2
F − целевая функция, или критерий эффективности (критерий оптимальности), которая записывается как F = F(x, a, ξ) .
В соответствии с введенными обозначениями математическая модель задачи имеет следующий вид:
𝐹 𝑥, 𝑎, 𝜉 → 𝑒𝑥𝑡𝑟
!∈!
, где 𝑒𝑥𝑡𝑟 = 𝑚𝑖𝑛
𝑚𝑎𝑥
Задача предполагает нахождение такого оптимального решения
𝑥
∗
∈ 𝑋, чтобы при данных фиксированных параметрах a и с учетом неизвестных факторов ξбыл получен экстремум целевой функции F , т.е.
𝐹
∗
= 𝐹 𝑥
∗
, 𝑎, 𝜉 = 𝑒𝑥𝑡𝑟
!∈!
𝐹 𝑥, 𝑎, 𝜉
Таким образом, оптимальное решение − это решение, предпочтительное
(наилучшее) перед другими по определенному критерию эффективности
(одному или нескольким).
Линейное программирование (ЛП) является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач ЛП следующие:
1) показатель оптимальности F = F(x, a,) представляет собой линейную
функцию от элементов решения x;
2) ограничительные условия, налагаемые на возможные решения, имеют вид системы линейных равенств или неравенств, которая называется системой ограничений. Если в систему ограничений входят неравенства и уравнения, то
ЗЛП называется общей. Если система ограничений состоит лишь из одних неравенств, то такая ЗЛП называется стандартной. Если система ограничений состоит лишь из одних уравнений, то такая ЗЛП называется канонической.
Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование − это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий.
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином

3 виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:
• задача об оптимальном использовании ресурсов при производственном планировании;
• задача о смесях (планирование состава продукции);
• задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или "задача о рюкзаке");
• транспортные задачи (анализ размещения предприятия, перемещение грузов).
Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:
• математические модели большого числа экономических задач линейны относительно искомых переменных;
• данный тип задач в настоящее время наиболее изучен. Для него разработаны специальные методы, с помощью которых эти задачи решаются, и соответствующие программы для ЭВМ;
• многие задачи линейного программирования, будучи решенными, нашли широкое применение;
• некоторые задачи, которые в первоначальной формулировке не являются линейными, после ряда дополнительных ограничений и допущений могут стать линейными или могут быть приведены к такой форме, что их можно решать методами линейного программирования.
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
Рассмотрим примеры некоторых типовых задач, решаемых при помощи методов линейного программирования. Такие задачи имеют реальное экономическое содержание.

4 2. Примеры задач линейного программирования (ЗЛП)
1. Задача планирования производства
Пример 1.В начале разберем частную постановку задачи планирования производства.
Для изготовления двух видов продукции
P
1
и
P
2
используют четыре вида ресурсов
S
1
,
S
2
,
S
3
,
S
4
. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 1
(числа условные).
Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной.
Таблица 1
Вид ресурса
Запас ресурса
Число единиц ресурса, необходимых при изготовлении единицы продукции
P
1
P
2
S
1 18 1
3 2
S
16 2
1 3
S
5
-
1 4
S
21 3
-
Прибыль, получаемая от реализации единицы продукции, у.е.
2 3
Решение.
Составим экономико-математическую модель задачи.
Введем обозначения:
x
1
, x
2
- число единиц продукции видов P
1
и P
2
, соответственно, запланированных к производству;
F - суммарная прибыль от реализации всей продукции.
Тогда связь между потреблением ресурсов и их запасами можно представить в виде следующей системы неравенств:
x
1
+ 3x
2
≤ 18
,
2x
1
+ x
2
≤ 16
,
x
2
≤ 5
, (1)
3x
1
≤ 21

5
По смыслу задачи переменные
x
1
≥ 0
,
x
2
≥ 0
. (2)
Прибыль F будет равна
F = 2x
1
+ 3x
2
. (3)
Таким образом, необходимо найти такой план выпуска продукции
X = (x
1
, x
2
) , удовлетворяющий условиям (1) и (2), при котором функция (3) примет максимальное значение.
Рассмотрим задачу планирования производства в общей постановке.
Введем обозначения:
n
- количество видов продукции;
m
- количество видов ресурсов;
a
ij
- число единиц ресурса
S
i
, необходимого при изготовлении единицы продукции P
j
;
c
j
- прибыль от реализации единицы продукции P
j
;
b
i
- запас ресурса
S
i
;
x
j
- объем выпуска продукции
P
j
Необходимо составить такой план производства продукции
X = (x
1
, x
2
,..., x
n
)
, при котором прибыль от ее реализации будет максимальной.
В табличной форме запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, можно представить следующим образом
(таблица 2)
Таблица 2
Вид ресурса, S
i
Запас ресурса,
b
i
Число единиц ресурса, необходимых при изготовлении единицы продукции, P
j
P
1
…
P
n
S
1
b
1
a
11
…
a
1n
S
2
b
2
a
21
…
a
2n
…
…
…
…
S
m
b
m
a
m1
…
a
mn
Прибыль, получаемая от реализации единицы продукции, д.е.
c
1
…
c
n

6
Составим экономико-математическую модель задачи планирования производства в общей постановке:
a
ij
x
j
≤ b
i
j=1
n
∑
,
i = 1, 2,..., m
, (4) система неравенств (ограничений), связывающая потребление ресурсов и их запасы;
x
j
≥ 0 , j = 1, 2,..., n , (5) условие на неотрицательность переменных;
F =
c
j
x
j
→ max
j=1
n
∑
, (6) условие максимума прибыли.
Оптимальное решение будем обозначать, как
x
*
= (x
1
*
, x
2
*
,...., x
n
*
)
Тогда задачу планирования производства в общем виде можно сформулировать следующим образом, необходимо найти такой план выпуска продукции
X = (x
1
, x
2
,..., x
n
)
, удовлетворяющий условиям (4) и (5), при котором функция
(6) примет максимальное значение. Решение этой задачи называется оптимальным решением (оптимальным планом) задачи линейного программирования и обозначается следующим образом
x
*
= (x
1
*
, x
2
*
,...., x
n
*
).
2. Задача об использовании мощностей (задача о загрузке оборудования)
Предприятию задается план производства продукции по времени и номенклатуре: требуется за время
T
выпустить
n
1
,
n
2
,…,
n
k
единиц продукции
P
1
,
P
2
,…,
P
k
. При этом для производства данной продукции используется оборудование
S
1
,
S
2
,…,
S
m
. Для каждого оборудования известны производительность
a
ij
(число единиц продукции P
j
, которое можно произвести на оборудовании
S
i
в единицу времени) и затраты b
ij
на изготовление продукции P
j
на оборудовании
S
i
в единицу времени.
Необходимо составить такой план загрузки оборудования, другими словами, так распределить выпуск продукции между используемым оборудованием, чтобы затраты на производство всей продукции были минимальными.
Решение.
Составим экономико-математическую модель задачи.

7
Обозначим x
ij
- время, в течение которого на оборудовании
S
i
будет производиться продукция P
j
(
i = 1, 2,..., m
; j =1, 2,..., k ).
По условию задачи, время работы оборудования ограничено, следовательно, справедливы следующие неравенства (система неравенств):
x
11
+ x
12
+... + x
1k
≤ T
,
x
21
+ x
22
+... + x
2k
≤ T
,
(7)
……………………..
x
m1
+ x
m2
+... + x
mk
≤ T
, или, в общем виде:
x
ij
≤ T
j=1
k
∑
,
i = 1, 2,..., m
Из условия задачи также следует, что существует план выпуска продукции по номенклатуре, поэтому необходимо, чтобы выполнялись следующие неравенства:
a
11
x
11
+ a
21
x
21
+... + a
m1
x
m1
≤ n
1
,
a
12
x
12
+ a
22
x
22
+... + a
m2
x
m2
≤ n
2
,
(8)
………………………………..
a
1k
x
1k
+ a
2k
x
2k
+... + a
mk
x
mk
≤ n
k
, или, в общем виде:
a
ij
x
ij
≤ n
j
i=1
m
∑
,
j = 1, 2,..., k .
К ограничениям (7) и (8) необходимо добавить условие на неотрицательность переменных:
x
ij
≥ 0
,
i = 1, 2,..., m
;
j = 1, 2,..., k
(9)
Затраты на производство всей продукции можно записать в виде следующей функции
F = b
11
x
11
+ b
12
x
12
+... + b
mk
x
mk
(10)

8
Теперь можно сформулировать экономико-математическую модель задачи о загрузке оборудования: найти такое решение
X = (x
11
, x
12
,..., x
mk
)
, удовлетворяющее ограничениям (7-9), при котором функция (10) примет минимальное значение.
3. Транспортная задача (ТЗ)
Частным (важным) случаем ЗЛП является транспортная задача.
Рассмотрим частный случай транспортной задачи.
Пример 2. Имеются три поставщика и четыре потребителя некоторого однородного груза. Мощность (запасы единиц груза) поставщиков и спросы
(потребности единиц груза) потребителей, а также затраты на перевозку единицы груза (тарифы) для каждой пары «поставщик – потребитель» сведены в таблицу поставок (таблица 3).
Таблица 3
Поставщики
Запасы поставщиков
Потребители и их потребности
1 2
3 4
20 110 40 110 1
60 1
x
11 2
x
12 5
x
13 3
x
14 2
120 1
x
21 6
x
22 5
x
23 2
x
24 3
100 6
x
31 3
x
32 7
x
33 4
x
34
В верхнем левом углу (i, j) – ячейки находится коэффициент затрат - затраты на перевозку единицы груза от i –го поставщика j-му потребителю (в у.е.).
Задача линейного программирования (транспортная задача) в этом случае ставится следующим образом: найти объемы перевозок для каждой пары
«поставщик – потребитель» так, чтобы
1. мощности всех поставщиков были реализованы;
2. спросы всех потребителей были удовлетворены;
3. суммарные затраты на перевозку были бы минимальными.
Решение. Составим экономико-математическую модель транспортной задачи.
Введем обозначения:
x
ij
- искомый объем перевозок от i поставщика j потребителю.

9
Тогда, исходя из первого условия задачи, составим уравнение баланса для каждой строки таблицы поставок
x
11
+ x
12
+ x
13
+ x
14
= 60
,
x
21
+ x
22
+ x
23
+ x
24
= 120
,
(11)
x
31
+ x
32
+ x
33
+ x
34
= 100
Исходя из второго условия задачи, составим уравнение баланса для каждого столбца таблицы поставок
x
11
+ x
21
+ x
31
= 20
,
x
12
+ x
22
+ x
32
= 110
,
x
13
+ x
23
+ x
33
= 40
,
(12)
x
14
+ x
24
+ x
34
= 110
Очевидно, что объемы перевозок не могут быть отрицательными:
x
ij
≥ 0 ( i = 1, 3; j = 1, 4 ).
Суммарные затраты F на перевозку выражаются через коэффициенты затрат и объемы перевозок:
F = 1⋅ x
11
+ 2 ⋅ x
12
+ 5⋅ x
13
+ 3⋅ x
14
+
1⋅ x
21
+ 6 ⋅ x
22
+ 5⋅ x
23
+ 2 ⋅ x
24
+
+
6 ⋅ x
31
+ 3⋅ x
32
+ 7⋅ x
33
+ 4 ⋅ x
34
(13)
Тогда экономико-математическую модель транспортной задачи можно сформулировать следующим образом: найти такое решение
X = (x
11
, x
12
, x
13
, x
14
,
x
21
, x
22
, x
23
, x
24
,
x
31
, x
32
, x
33
, x
34
) при ограничениях (11) и (12) при котором линейная функция (13) принимает минимальное значение.
Отметим некоторые особенности экономико-математической модели транспортной задачи:
1. система ограничений является системой уравнений, т.е. транспортная задача задается в канонической форме;
2. коэффициенты при переменных системы ограничений равны единице или нулю;
3. каждая переменная входит в систему ограничений два раза, по одному разу в (11) и (12).

10
Запишем транспортную задачу в общем виде. Введем обозначения:
c
ij
- коэффициенты затрат;
M
i
– мощность i поставщика (i =1, m );
N
j
– спрос j потребителя ( j =1, n ).
Тогда систему ограничений можно записать в виде:
x
ij
= M
i
j=1
n
∑
,
(11’)
x
ij
= N
j
i=1
m
∑
(12’)
Целевую функцию можно представить следующим образом:
F =
c
ij
⋅ x
ij
i=1
m
∑
j=1
n
∑
(13’) в этом случае экономико-математическую модель транспортной задачи можно сформулировать таким образом: на множестве ограничений (11’), (12’) найти такое решение
X = (x
11
, x
12
,
..., x
ij
,... ,
x
mn
), при котором значение линейной функции (13’) будут минимальным.
Отметим, что в том случае, когда выполняется равенство
M
i
=
N
j
j=1
n
∑
i=1
m
∑
, транспортная задача называется закрытой, если же баланс нарушен
M
i
≠
N
j
j=1
n
∑
i=1
m
∑
, то транспортная задача называется открытой.
Рассмотрим модель открытой ТЗ.
Открытая ТЗ решается сведением ее к закрытой ТЗ.
Допустим, что необходимо найти оптимальное распределение поставок для следующей таблицы поставок. Это таблица поставок, представлена в сокращенной форме: в первом столбце указаны мощности поставщиков, в первой строке − спрос потребителей. Числа в левом верхнем углу клетки − коэффициенты затрат.

11
В данном случае потребность потребителей больше, чем запасы поставщиков
N
j
j=1
n
∑
>
M
i
i=1
m
∑
. Введем «фиктивного» поставщика, а таблицу поставок добавим дополнительную строку так, чтобы ТЗ стала закрытой:
N
j
j=1
n
∑
=
M
i
i=1
m
∑
(добавим разность). Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу
(например, нулю). Конкретное значение этого числа не влияет на оптимальное распределение поставок.
В случае, когда суммарная мощность поставщиков больше суммарной потребности потребителей, в рассмотрение вводится «фиктивный» потребитель.
N
j =
200
∑
M
i =
190
∑
45
35
55
65
40
4 1
2 5
60
3 2
3 7
90
4 4
5 2
45
35
55
65
40
4 1
2 5
60
3 2
3 7
90
4 4
5 2
10
0 0
0 0

12
В таблице поставок добавляется новый столбец. Коэффициенты затрат добавленного потребителя соответствуют затратам на хранение неотправленного груза. Если информация об этих затратах отсутствует, то их принимают равными одному и тому же числу (например, нулю).
60
60
50
10
50
2 3
2 0
70
2 4
5 0
60
6 5
7 0