1
Федеральное агентство по образованию
Государственное образовательное учреждение
высшего професси
о
нального образования
«Тихоокеанский государственный университет»
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ ПРИ МИНИМИЗАЦИИ ЗАТРАТ Р
ЕСУРСОВ
ДОРОЖНОГО СТРОИТЕЛЬСТВА
Метод
и
ческие указания и задание к контрольной работе по дисциплине
«Экономико
-
математические методы в проектировании транспортных
сооружений» для студентов специальности 291000
“Автомобильные дороги и аэродромы ”
Хабаровск
Издательство ТОГУ
2006

2
УДК 625.7/.8.003.1
Решение транспортной задачи линейного программирования при минимизации
затрат ресурсов дорожного строительства: метод
и
ческие указания и задание к
контрольной работе по дисциплине «Экономико
-
м
атематические методы в
проектировании транспортных сооружений» для студентов специальности
291000 “Автомобильные дороги и аэродромы ”/ сост. В. А. Ярмолинский.
–
Хабаровск: Изд
-
во Тихоокеанского гос. ун
-
та, 2006.
–
28 с.
В методических указаниях даны рекоме
ндации по методике и
последов
а
тельности выполнения контрольной работы в требуемом объеме.
В контрольной работе отражены вопросы применения экономико
-
математического моделирования в решении задач дорожного строительства.
Для более глубокой проработки соотв
етствующих разделов задания ст
у
денты
должны использовать рекомендуемую учебную и техническую литер
а
туру.
Печатается в соответствии с решениями кафедры автомобильных дорог и
методического совета дальневосточного автодорожного института.

Тихоокеанский государственный
университет, 2006
ЦЕЛЬ КОНТРОЛЬНОЙ РАБОТЫ:

3
Освоение методов линейного программирования для решения транспортной
задачи линейного программирования при минимизации затрат ресурсов
дорожного строительства.
З
АДАЧИ:
–
Построение опорного плана распределения перевозок.
–
Проверка плана перевозок на оптимальность.
–
Построение оптимального плана распределения перевозок.
1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Операцией
называется всякое мероприятие, объединенное единым зам
ыслом и
направленное к достижению какой
-
либо цели. Операция всегда
управляемое
мероприятие.
Решением
называется определенный выбор параметров, имеющихся в
распоряжении исследователя.
Оптимальными
называются решения, которые по тем или иным признакам
пр
едпочтительнее других.
Параметры, совокупность которых образует решение, называются
элементами
решения
.
Кроме элементов решения, в любой задаче экономико
-
математического
моделирования имеются заданные условия или ограничения, фиксированные с
самого начала
операции и которые не могут быть нарушены. В своей
совокупности они формируют
множество возможных решений
.
Для сравнения между собой по эффективности различных решений необходимо
иметь количественный критерий, называемый
показателем эффективности
или
цел
евой функцией
.
Математической моделью
называется схема или макет реального явления
(операции), описываемого с помощью математического аппарата.
Различают
аналитические
и
статистические
модели.
Аналитические модели
более грубы, чем статистические, учитыв
ают меньшее
число факторов, всегда требуют допущений и упрощений. Зато результаты
расчета по ним более обозримы, отчетливее выражают присущие явлению
закономерности и наиболее приспособлены для поиска оптимальных решений.
Статистические модели
более точны
и подробны, не требуют грубых
допущений, позволяют учесть большое (в теории
–
неограниченно большое)
число факторов. Но они громоздки, плохо обозримы, требуют большого
расхода времени решения на ЭВМ и трудны для поиска оптимальных решений.
Для выбора опт
имальных решений наиболее эффективно совместное
применение аналитических и статистических моделей.
Изучаемые реальные явления могут быть
детерминированными
и
случайными
.

4
Детерминированные
явления позволяют результат (исход) операции
предсказать заранее.
Случайные
явления протекают при наличии неопределенных (случайных)
факторов, заставляющих выбирать решения в условиях неопределенности.
Матрицей
называется совокупность чисел, расположенных в виде
прямоугольника.
Уравнения, в которые входят неизвестные т
олько первой степени и никакое
неизвестное не умножается на другое неизвестное, называются
линейными.
2. МЕТОДИКА ВЫПОЛНЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ
Транспортная задача линейного программирования
является задачей области
линейного программирования. Для тр
анспортной задачи характерны все
основные признаки задач линейного программирования:
–
все неизвестные входят в решение уравнения целевой функции только в 1
-
й
степени;
–
все ограничения задачи выражены в форме линейных зависимостей, равенств
или неравенст
в;
–
число линейных зависимостей в задаче должно быть меньше числа
неизвестных.
Критерий оптимальности должен быть задан уравнением целевой функции:
W
=
￥
mn
ij
ﾮ
ￗ
x
c
ij
ij
max
(
min
),
(1)
где
x
ij
–
неизвестные или принимаемые нами решения (в транспортной задаче
количество материала (продукции), перевозимого от
i
-
го поставщика к
j
-
му
потребителю);
c
ij
–
критер
ий оптимальности (в транспортных задачах это себестоимость
перевозок, длина пройденного участка дороги и др.).
Транспортная задача рассматривает перераспределение грузов, товаров между
поставщиками и потребителями. С этой целью должны быть заданы
ограниче
ния в виде равенств или неравенств:
￥
￥
￥
￥
ﾣ
ﾣ
n
j
j
n
j
ij
m
i
i
m
i
ij
b
X
a
X
,
;
(2)

5
где
a
i
–
количество материала (продукции)
i
-
го поставщика;
b
j
–
количество
материала, необходимого
j
-
му потребителю.
Для решения транспортной задачи линейного программирования должно
соблюдаться условие
–
количество линейных уравнений, описывающих задачу,
должно быть меньше числа неизвестных входящих в эту задачу.
Тран
спортные задачи линейного программирования бывают двух типов:
–
открытые;
–
закрытые.
Закрытые
транспортные задачи
характерны тем, что в них мощность
поставщика равна потребности потребителя:
￥
￥
=
n
j
j
m
i
i
b
a
. (3)
Открытые
транспортные задачи те, в которых
мощность поставщиков не
равна потребности потребителей:
￥
￥
ﾹ
n
j
j
m
i
i
b
a
.
(4)
Для решения открытой задачи ее необходимо привести к закрытой путем
введения фиктивного поставщика или потребителя.
Рассмотрим решение транспортной задачи на примере.
Имеется
m
гравийных карьеров,
в которых осуществляется заготовка
материалов (1,2,3,…
i
,..
m
).
Имеется
n
объектов дорожных работ, которым
нужны гравийные материалы (1,2,3,…
j
,..
n
).
Введем обозначения:
a
i
–
количество гравийного материала, которое может
быть по
лучено в
i
-
м карьере, м
³;
b
j
–
количество материала, необходимого
j
-
му объекту дорожно
-
строительных работ,
м
³;
x
ij
–
количество гравийного
материала, перевозимого из
i
-
го карьера на
j
-
й объект (рис. 1),
c
ij
–
себестоимость перевозок или критерий оптимальности
.
Транспортная задача имеет закрытый тип. Необходимо
распределить перевозки
так, чтобы стоимость всего объема перевозок была минимальной.
а
1
а
2
а
3
в
4
в
3
в
2
в
1
а
4
в
5

6
Рис. 1. Схема расположения карьеров и
объектов работ
Задана целевая функция решения задачи
W
=
￥
mn
ij
ﾮ
ￗ
x
c
ij
ij
min
, и
ограничения, отражающи
е
совокупность перевозок из карьеров к объектам
работ,
–
формула (2).
Для наглядности при решении транспортной задачи
составляется матрица
распределения перевозок (табл. 1).
Таблица 1
Поставщик
(карьеры)
Потребитель (объекты работ)
В1
В2
В3
В4
В5
55
90
40
30
20
А1
80
С
11
=10
Х
11
=
С
12
=12
Х
12
=
С
13
=14
Х
13
=
С
14
=18
Х
14
=
С
15
=19
Х
15
=
А2
75
С
21
=11
Х
21
=
С
22
=16
Х
22
=
С
23
=18
Х
23
=
С
24
=20
Х
24
=
С
25
=21
Х
25
=
А3
45
С
31
=13
Х
31
=
С
32
=14
Х
32
=
С
33
=15
Х
33
=
С
34
=16
Х
34
=
С
35
=20
Х
35
=
А4
35
С
41
=18
Х
41
=
С
42
=19
Х
42
=
С
43
=20
Х
43
=
С
44
=10
Х
44
=
С
45
=15
Х
45
=
При распределении перевозок
x
ij
клетки матри
цы могут быть нулевыми или
свободными, либо ненулевыми или базисными.
Для решения транспортной задачи линейного программирования необходимо
иметь опорный или базисный план распределения перевозок. Опорный или
базисный план должен быть допустимым для решен
ия и отвечать следующим
условиям:
m
+
n
–
1 =
N
,
(5)
где
m
–
количество строк;
n
–
количество столбцов,
N
–
число базисных
клеток матрицы распределения
перевозок. Только в этом случае задача имеет
решение.
В рассматриваемом примере
m
+
n
-
1=9
-
1=8.
Для составления опорного плана существует ряд методов, одними из которых
являются:
–
метод северо
-
западного угла;
–
метод наименьшего элемента решения в строке и
ли столбце;
–
метод наименьшего элемента матрицы.
Опорный или базисный план распределения, как правило, не является
оптимальным.

7
План перевозок будет считаться оптимальным, если он среди всех допустимых
планов приводит к минимальной суммарной стоимости пе
ревозок
В методе
северо
-
западного угла
распределение поставок начинается с крайней
левой верхней клетки матрицы и заканчивается в нижнем правом углу
матрицы (табл. 2). Поскольку при распределении перевозок в этом случае не
учитывается стоимость клетки мат
рицы, то метод северо
-
западного угла
является малоэффективным для достижения оптимального плана.
При составлении опорного плана перевозок в выбранную клетку матрицы
стараются записать максимально возможную поставку по данному
направлению. Общее количеств
о клеток матрицы, содержащих перевозки, в
рассматриваемом примере должно быть равно 8 (базисные клетки матрицы
отмечены точками).
Таблица 2
m+n
-
1=9
-
1=8
Поставщик
Потребитель
В1
В2
В3
В4
В5
55
90
40
30
20
А1
80
С
11
=10 •
Х
11
=55
С
12
=12 •
Х
12
=15
С
13
=14 •
Х
13
=10
С
14
=18
Х
14
=0
С
15
=19
Х
15
=0
А2
75
С
21
=11
Х
21
=0
С
22
=16 •
Х
22
=75
С
23
=18
Х
23
=0
С
24
=20
Х
24
=0
С
25
=21
Х
25
=0
А3
45
С
31
=13
Х
31
=0
С
32
=14
Х
32
=0
С
33
=15 •
Х
33
=30
С
34
=16 •
Х
34
=15
С
35
=20
Х
35
=0
А4
35
С
41
=18
Х
41
=0
С
42
=19
Х
42
=0
С
43
=20
Х
43
=0
С
44
=10
•
Х
44
=15
С
45
=15 •
Х
45
=20
Найдем целевую функцию (функционал) для данной задачи по методу северо
-
западного угла:
.
3210
20
15
15
10
15
16
30
15
75
16
10
14
15
12
55
10
3
1
<
@C
X
C
W
mn
ij
ij
ij
￥
ￗ
=
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
=
ￗ
=
В отличие от метода северо
-
западного угла в методе
наименьшего элемента в
строке или столбце
, а также
наименьшего э
лемента матрицы
стремятся
записать максимальную поставку в клетку с наименьшей стоимостью
перевозок, это обстоятельство делает эти методы более предпочтительными,
чем метод северо
-
западного угла. Но критерием выбора того или иного метода
служит значение це
левой функции.
Произведем определение опорного плана перевозок методом
наименьшего
элемента в строке или столбце матрицы
. Для этого начнем запись
максимально возможных поставок в выбранную строку или столбец матрицы.
Если при записи поставок в выбранную
(наиболее дешевую) клетку матрицы
спрос по строке или столбцу удовлетворен не полностью, то в данной строке
или столбце выбирается новая клетка и так до полного удовлетворения спроса
(табл. 3). Только после этого переходят к следующей строке или столбцу.
Таблица 3
m+n
-
1=9
-
1=8
Поставщик
Потребитель

8
55
90
40
30
20
А1
80
С
11
=10 •
Х
11
=55
С
12
=12 •
Х
12
=25
С
13
=14
Х
13
=0
С
14
=18
Х
14
=0
С
15
=19
Х
15
=0
А2
75
С
21
=11
Х
21
=0
С
22
=16 •
Х
22
=65
С
23
=18
Х
23
=0
С
24
=20
Х
24
=0
С
25
=21 •
Х
25
=10
А3
45
С
31
=13
Х
31
=0
С
32
=14
Х
32
=0
С
33
=15 •
Х
33
=40
С
34
=16
Х
34
=0
С
35
=20 •
Х
35
=5
А4
35
С
41
=18
Х
41
=0
С
42
=19
Х
42
=0
С
43
=20
Х
43
=0
С
44
=10 •
Х
44
=30
С
45
=15 •
Х
45
=5
Значение целевой функции согласно данному методу составит
.
3175
5
15
30
10
5
20
40
15
10
21
65
16
25
12
55
10
3
2
<
@C
X
C
W
mn
ij
ij
ij
￥
ￗ
=
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
=
ￗ
=
Мето
д
наименьшего элемента матрицы
предусматривает, что вначале
максимально возможная поставка вводится в наиболее дешевую клетку всей
матрицы (если этих клеток несколько, можно взять любую по выбору). Затем
распределение поставок ведется в порядке приоритет
а для более дешевых
оставшихся клеток матрицы (табл. 4).
Таблица 4
m
+
n
-
1=9
-
1=8
Поставщик
Потребитель
В1
В2
В3
В4
В5
55
90
40
30
20
А1
80
С
11
=10 •
Х
11
=55
С
12
=12 •
Х
12
=25
С
13
=14
Х
13
=0
С
14
=18
Х
14
=0
С
15
=19
Х
15
=0
А2
75
С
21
=11
Х
21
=0
С
22
=16 •
Х
22
=20
С
23
=18
•
Х
23
=40
С
24
=20
Х
24
=0
С
25
=21 •
Х
25
=15
А3
45
С
31
=13
Х
31
=0
С
32
=14
•
Х
32
=45
С
33
=15
Х
33
=0
С
34
=16
Х
34
=0
С
35
=20
Х
35
=
0
А4
35
С
41
=18
Х
41
=0
С
42
=19
Х
42
=0
С
43
=20
Х
43
=0
С
44
=10 •
Х
44
=30
С
45
=15 •
Х
45
=5
Целевая функция опорного пл
ана по методу наименьшего элемента в матрице
составит
.
3210
45
14
5
15
30
10
15
21
40
18
20
16
25
12
55
10
3
3
￥
ￗ
=
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
=
ￗ
=
mn
ij
ij
ij
<
@C
X
C
W
В качестве принятого опорного (базисного) выбираем план, найденный по
методу наименьшего элемента в строке или столбце
2
W
с минимальным
значением целевой
функции 3175 руб·м
³.
Опорный план необходимо проверить на оптимальность. В случае, если
опорный план не является оптимальным (а это случается чаще всего), провести
оптимизацию опорного плана.
Для оптимизации принятого опорного плана воспользуемся методом
Л.В.
Канторовича, названный методом «потенциалов» [2, 5]. Суть метода состоит в
том, что каждая итерация, приближающая исходный (опорный) план к
оптимальному, состоит из двух этапов.
На первом этапе план, полученный в результате предыдущей итерации,
пр
оверяется на оптимальность. Если проверка не прошла и план оказался

9
неоптимальным, то на втором этапе строится новый план, обусловливающий
меньшую стоимость перевозок от поставщиков к потребителям по сравнению с
предыдущим планом. Итерации повторяются до
тех пор, пока не будет
построен оптимальный план.
В методе потенциалов доказывается, что для любого опорного плана могут
быть найдены такие числа
i
U
и
j
V
,
при которых для всех базисных (ненулевых)
клеток матрицы о
порного плана имеет место равенство
ij
j
i
C
V
U
=
+
.
(6)
Сумма потенциалов равна стоимости базисной клетке матрицы.
Для всех клеток матрицы, не
входящих в опорный план (нулевых клеток), где
переменные
x
ij
= 0, должно выполняться следующее условие:
0
ﾣ
-
+
ij
j
i
C
V
U
. (7)
При
назначении потенциалов один из них, (любой), назначается произвольно
(из условия неотрицательности поставок назначают первый потенциал больше
или равный нулю), все остальные потенциалы жестко связаны с первым через
систему линейных уравнений опорного пла
на. Принимаем
1
U
= 0 (табл. 5).
Таблица 5
m+n
-
1=9
-
1=8
Поставщик
Потребитель
В1
В2
В3
В4
В5
U
55
90
40
30
20
А1
80
С
11
=10 •
Х
11
=55
55
-
ﾮ
С
12
=12 •
55
+
Х
12
=25
С
13
=14
Х
13
=0
С
14
=18
Х
1
4
=0
С
15
=19
Х
15
=0
U
1
=0
А2
75
С
21
=11
55
+
Х
21
=0
ﾬ
-
55
С
22
=16
•
Х
22
=65
С
23
=18
Х
23
=0
С
24
=20
Х
24
=0
С
25
=21 •
Х
25
=10
U
2
=4
А3
45
С
31
=13
Х
31
=0
С
32
=14
Х
32
=0
С
33
=15 •
Х
33
=40
С
34
=16
Х
34
=0
С
35
=20 •
Х
35
=5
U
3
=3
А4
35
С
41
=18
Х
41
=0
С
42
=19
Х
42
=0
С
43
=20
Х
43
=0
С
44
=10 •
Х
44
=30
С
45
=15 •
Х
45
=5
U
4
=
-
2
V
V
1
=10
V
2
=12
V
3
=12
V
4
=12
V
5
=17
Составляем систему линейных уравнений опорного плана (только для базисных
клеток матрицы) и находим потенциалы для опорного плана пере
возок.
￯
￯
￯
￯
￯
￮
￯
￯
￯
￯
￯
￭
￬
-
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
2
15
3
20
17
21
12
10
12
15
4
16
12
12
10
10
4
45
4
5
3
35
3
5
5
25
2
5
4
44
4
4
3
33
3
3
2
22
2
2
2
12
1
2
1
11
1
1
U
C
U
V
U
C
U
V
V
C
U
V
V
C
U
V
V
C
U
V
U
C
U
V
V
C
U
V
V
C
U
V

10
Производим проверку на оптимальность (только для нулевых клеток матрицы):
0
2
19
0
17
0
1
16
3
12
0
4
20
4
12
0
6
18
0
12
0
10
20
2
12
0
2
18
4
12
0
2
14
0
12
0
9
19
2
12
0
1
14
3
12
0
10
18
2
10
0
13
3
10
0
3
11
4
10
15
1
5
34
3
4
24
2
4
14
1
4
43
4
3
23
2
3
13
1
3
42
4
2
32
3
2
41
4
1
31
3
1
21
2
1
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
-
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
-
=
-
+
>
=
-
+
=
-
+
<
-
=
-
-
=
-
+
=
-
+
=
-
+
>
=
-
+
=
-
+
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
Проверка показала, что план распределения перевозок не является
оптимальным. В данном случае 2 клетк
и опорного плана (со стоимостью
c
12
и
c
23
) имеют положительную разность. В эти клетки необходимо
перераспределять перевозки при построении нового допустимого плана.
Для введения в новый опорный план должна приниматьс
я только одна клетка с
положительной разностью, стоимость перевозок в которой
C
ij
имеет
наименьшее значение.
Минимальная стоимость перевозок для выявленных свободных клеток
матрицы с положительной разностью
C
12
=
11. В эту клетку необходимо
распределять перевозки при составлении нового опорного плана,
приближающего его к оптимальному.
Для введения в опорный план новой клетки необходимо построить цикл, одна
вершина у которого лежит в свободной клетке, а все остальны
е вершины цикла
находятся в базисных клетках матрицы [3,5]. Количество вершин цикла должно
быть четным и включать не менее 4 вершин. Для свободной клетки со
стоимостью
C
12
может быть построен следующий цикл (табл. 5, рис. 2).
С
11
=10
Х
11
=55
-
55
С
12
=12
Х
12
=25
+55
С
21
=11
Х
21
=0
+55
С
12
=12
Х
12
=65
-
55
+
+

11
Рис. 2. Цикл перераспределения перевозок
Поставка, перераспределяемая по циклу из базисной клетки в свободную,
должна быть равна минимальной поставке
x
ij
отрицательной вершины цикла.
После каждого перераспределения пос
тавки по циклу необходимо производить
проверку. Сумма поставок по строкам и столбцам матрицы должна быть равна
соответственно мощности поставщиков и потребности потребителей:
.
;
1
1
b
a
j
n
j
i
i
m
i
Xij
Xij
=
=
￥
￥
=
=
После перераспределения поставок по циклу одна свободная
клетка матрицы
становиться базисной, а одна базисная клетка
–
свободной. Составляем новый
опорный план (табл. 6).
Таблица 6
m
+
n
-
1=9
-
1=8
Поставщик
Потребитель
В1
В2
В3
В4
В5
U
55
90
40
30
20
А1
80
С
11
=10
Х
11
=0
С
12
=12 •
Х
12
=80
С
13
=14
Х
13
=
0
С
14
=18
Х
14
=0
С
15
=19
Х
15
=0
U
1
=0
А2
75
С
21
=11 •
Х
21
=55
С
22
=16 •
Х
22
=10
5
-
ﾯ
С
23
=18
Х
23
=0
С
24
=20
Х
24
=0
С
25
=21 •
Х
25
=10
5
+
U
2
=4
А3
45
С
31
=13
Х
31
=0
С
32
=14
5
+
Х
32
=0
С
33
=15 •
Х
33
=40
С
34
=16
Х
34
=0
С
35
=20 •
Х
35
=5
5
-
ﾭ
U
3
=3
А4
35
С
41
=18
Х
41
=0
С
42
=19
Х
42
=0
С
43
=20
Х
43
=0
С
44
=10 •
Х
44
=30
С
45
=15 •
Х
45
=5
U
4
=
-
2
V
V
1
=
7
V
2
=12
V
3
=12
V
4
=12
V
5
=17
Находим значение целевой функции для н
ового опорного плана
.
3010
5
15
5
20
10
21
30
10
40
15
10
16
80
12
55
11
3
4
<
@C
X
C
W
mn
ij
ij
ij
￥
ￗ
=
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
=
ￗ
=
По сравнению с начальным опорным планом, где целевая функция
2
W
составила 3175 руб·м
³,
новый опорный план более дешевый. Теперь
необходимо проверить его на оптимальность. Составляем систему
линейных
уравнений опорного плана.
￯
￯
￯
￯
￯
￮
￯
￯
￯
￯
￯
￭
￬
-
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
2
15
3
20
17
21
12
10
12
15
4
16
7
11
12
12
4
45
4
5
3
35
3
5
5
25
2
5
4
44
4
4
3
33
3
3
2
22
2
2
1
21
2
1
2
12
1
2
U
C
U
V
U
C
U
V
V
C
U
V
V
C
U
V
V
C
U
V
U
C
U
V
V
C
U
V
V
C
U
V

12
Производим проверку на оптимальность:
0
2
19
0
17
0
1
16
3
12
0
4
20
4
12
0
6
18
0
12
0
10
20
2
12
0
2
18
4
12
0
2
14
0
12
0
9
19
2
12
0
1
14
3
12
0
13
18
2
7
0
3
13
3
7
0
3
10
0
7
15
1
5
34
3
4
24
2
4
14
1
4
43
4
3
23
2
3
13
1
3
42
4
2
32
3
2
41
4
1
31
3
1
11
1
1
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
-
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
-
=
-
+
>
=
-
+
=
-
+
<
-
=
-
-
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
Проверка показала, что существует только одна свободная клетка матрицы с
положительной разностью, эта клет
ка со стоимостью
C
32
. В эту клетку
необходимо перераспределить перевозки, для чего строим новый цикл,
содержащий 4 вершины. В свободную клетку матрицы с положительной
разностью перемещаем поставку, равную минимальной поставке
отрицате
льной вершины цикла (табл. 6).
Составляем новый опорный план
перевозок (табл. 7).
Таблица 7
m
+
n
-
1=9
-
1=8
Поставщик
Потребитель
В1
В2
В3
В4
В5
U
55
90
40
30
20
А1
80
С
11
=10
Х
11
=0
С
12
=12 •
Х
12
=80
С
13
=14
Х
13
=0
С
14
=18
Х
14
=0
С
15
=19
Х
15
=0
U
1
=0
А2
75
С
21
=11 •
Х
21
=55
С
22
=16 •
Х
22
=5
С
23
=18
Х
23
=0
С
24
=20
Х
24
=0
С
25
=21 •
Х
25
=15
U
2
=4
А3
45
С
31
=13
Х
31
=0
С
32
=14 •
Х
32
=5
С
33
=15 •
Х
33
=40
С
34
=16
Х
34
=0
С
35
=20
Х
35
=0
U
3
=
2
А4
35
С
41
=18
Х
41
=0
С
42
=19
Х
42
=0
С
43
=20
Х
43
=0
С
44
=10 •
Х
44
=30
С
45
=15 •
Х
45
=5
U
4
=
-
2
V
V
1
=
7
V
2
=12
V
3
=1
3
V
4
=12
V
5
=17
Составляем систему линейных уравнений опорного плана:

13
￯
￯
￯
￯
￯
￮
￯
￯
￯
￯
￯
￭
￬
-
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
=
=
=
+
2
15
15
15
17
21
12
10
2
14
4
16
7
11
12
12
4
45
4
5
3
33
3
3
5
25
2
5
4
44
4
4
3
32
3
2
2
22
2
2
1
21
2
1
2
12
1
2
U
C
U
V
V
C
U
V
V
C
U
V
V
C
U
V
U
C
U
V
U
C
U
V
V
C
U
V
V
C
U
V
Производим проверку на оптимальность:
0
1
20
2
17
0
2
19
0
17
0
2
16
2
12
0
4
20
4
12
0
6
18
0
12
0
9
20
2
13
0
1
18
4
13
0
1
14
0
13
0
9
19
2
12
0
13
18
2
7
0
4
13
2
7
0
3
10
0
7
35
3
5
15
1
5
34
3
4
24
2
4
14
1
4
43
4
3
23
2
3
13
1
3
42
4
2
41
4
1
31
3
1
11
1
1
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
-
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
-
=
-
+
<
-
=
-
-
=
-
+
<
-
=
-
+
=
-
+
<
-
=
-
+
=
-
+
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
C
U
V
Проверка на оптимальность выполняется, значения всех разностей меньше
либо равны нулю. Данный опорный план является оптимальным. Находим
значение целевой функции для оптимального плана перевозок (табл.7):
.
3005
5
15
15
21
30
10
40
15
5
14
5
16
80
12
55
11
3
5
<
@C
X
C
W
mn
ij
ij
ij
￥
ￗ
=
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
+
ￗ
=
ￗ
=
Найденное значение целев
ой функции является минимальным из всех
возможных допустимых планов перевозок.
Согласно шифру зачетной книжки, студент выбирает вариант матрицы
распределения перевозок (прил. 1, прил. 2). После чего необходимо произвести
составление опорного (базисного) п
лана перевозок методами: северо
-
западного
угла, наименьшего элемента в строке или столбце и наименьшего элемента в
матрице. Принимая в качестве начального план с минимальной целевой
функцией, необходимо произвести его проверку на оптимальность с помощью
ме
тода «потенциалов». В случае если план оказался неоптимальным, привести
его к оптимальному и найти значение целевой функции оптимального плана
перевозок.
БИБЛИОГРАФИЧЕСКИЙ СПИСОК

14
1.
Бим
-
Бад М.И.
Материально
-
техническое снабжение в дорожном
стро
и
тельстве:
учеб. пособие / М.И. Бим
-
Бад. М., 1983.
2.
Бирман И.Я.
Оптимальное программирование / И.Я. Бирман. М., 1968.
3.
Вентцель Е.С.
Исследование операций: задачи, принципы, методология / Е.С.
Вентцель. М., 1980.
4.
Замков О.О.
Математические методы в экономике: у
чебн. / О.О. Замков, А.В.
Толстопятенко, Ю.Н. Черемных. М., 1998.
5.
Золотарь И.А.
Экономико
-
математические методы в дорожном
стро
и
тельстве / И.А. Золотарь. М., 1974.
6.
Кремер Н.Ш.
Высшая математика для экономистов: учебн. для вуз. / Н.Ш.
Кремер, Б.А. Пру
тко, И.М. Тришин, М.Н. Фридман. М., 1998.
7.
Пазюк К.Т.
Математические методы и модели в экономике: учеб. пособие /
К.Т. Пазюк. Хабаровск, 2002.
8.
Юдин Д.Б.
Линейное программирование / Д.Б. Юдин, Е.Г. Гольштейн. М.,
1967.
Прил
ожение 1

15
Вариант задания согласно предпоследней и последней цифре зачетной книжки
Последняя
цифра
шифра
Предпоследняя цифра шифра зачетной книжки
0
1
2
3
4
5
6
7
8
9
Вариант задания
0
1
2
3
4
5
6
7
8
9
10
1
11
12
13
14
15
16
17
18
19
20
2
21
22
23
24
25
26
27
20
1
2
3
3
4
5
6
7
8
9
10
11
12
4
13
14
15
16
17
18
19
20
21
22
5
23
24
25
26
27
23
1
2
3
4
6
5
6
7
8
9
10
11
12
13
14
7
15
16
17
18
19
20
21
22
23
24
8
25
26
27
21
1
2
3
4
5
6
9
7
8
9
10
11
12
13
14
15
16
Приложение 2
Постав
щик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
= 15
X
11
=
C
12
= 12
X
12
=
C
13
= 14
X
13
=
C
14
= 18
X
14
=
C
15
= 19
X
15
=
A
2
75
C
21
= 11
X
21
=
C
22
= 13
X
22
=
C
23
= 18
X
23
=
C
24
= 20
X
24
=
C
25
= 21
X
25
=
A
3
4
5
C
31
= 14
X
31
=
C
32
= 16
X
32
=
C
33
= 15
X
33
=
C
34
=16
X
34
=
C
35
= 20
X
35
=
A
4
35
C
41
= 18
X
41
=
C
42
= 19
X
42
=
C
43
=20
X
43
=
C
44
= 10
X
44
=
C
45
=
1
5
X
45
=
Вариант 1
Вариант 2

16
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
= 8
X
11
=
C
12
= 7
X
12
=
C
13
= 1
X
13
=
C
14
= 2
X
14
=
C
15
= 6
X
15
=
A
2
75
C
21
= 1
X
21
=
C
22
= 12
X
22
=
C
23
= 9
X
23
=
C
24
= 21
X
24
=
C
25
= 3
X
25
=
A
3
45
C
31
= 4
X
31
=
C
32
= 14
X
32
=
C
33
= 15
X
33
=
C
34
=17
X
34
=
C
35
= 18
X
35
=
A
4
35
C
41
= 10
X
41
=
C
42
= 4
X
42
=
C
43
=5
X
43
=
C
44
= 11
X
44
=
C
45
= 14
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
= 8
X
11
=
C
12
= 10
X
12
=
C
13
=
1
1
X
13
=
C
14
= 2
X
14
=
C
15
= 6
X
15
=
A
2
75
C
21
= 7
X
21
=
C
22
= 15
X
22
=
C
23
= 2
X
23
=
C
24
= 4
X
24
=
C
25
= 7
X
25
=
A
3
45
C
31
= 9
X
31
=
C
32
= 12
X
32
=
C
33
= 11
X
33
=
C
34
= 12
X
34
=
C
35
= 6
X
35
=
A
4
35
C
41
= 14
X
41
=
C
42
= 2
X
42
=
C
43
= 8
X
43
=
C
44
= 7
X
44
=
C
45
= 5
X
45
=
Вариант 3
Вариант 4

17
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=8
X
11
=
C
12
=3
X
12
=
C
13
=2
X
13
=
C
14
=9
X
14
=
C
15
=10
X
15
=
A
2
75
C
21
=
11
X
21
=
C
22
=14
X
22
=
C
23
=14
X
23
=
C
24
=7
X
24
=
C
25
= 4
X
25
=
A
3
45
C
31
=19
X
31
=
C
32
=20
X
32
=
C
33
=24
X
33
=
C
34
=8
X
34
=
C
35
=6
X
35
=
A
4
35
C
41
=4
X
41
=
C
42
=6
X
42
=
C
43
=7
X
43
=
C
44
=12
X
44
=
C
45
=13
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=10
X
11
=
C
12
=11
X
12
=
C
13
=13
X
13
=
C
14
=14
X
14
=
C
15
=15
X
15
=
A
2
75
C
21
=19
X
21
=
C
22
=18
X
22
=
C
23
=5
X
23
=
C
24
=1
0
X
24
=
C
25
=13
X
25
=
A
3
45
C
31
=8
X
31
=
C
32
=15
X
32
=
C
33
=12
X
33
=
C
34
=14
X
34
=
C
35
=8
X
35
=
A
4
35
C
41
=14
X
41
=
C
42
=11
X
42
=
C
43
=18
X
43
=
C
44
=19
X
44
=
C
45
=20
X
45
=
Вариант 5
Вариант 6

18
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=2
X
11
=
C
12
=1
X
12
=
C
13
=3
X
13
=
C
14
=5
X
14
=
C
15
=8
X
15
=
A
2
75
C
21
=1
X
21
=
C
22
=3
X
22
=
C
23
=7
X
23
=
C
24
=9
X
24
=
C
25
=10
X
25
=
A
3
45
C
31
=4
X
31
=
C
32
=2
X
32
=
C
33
=1
X
33
=
C
34
=5
X
34
=
C
35
=8
X
35
=
A
4
35
C
41
=2
X
41
=
C
42
=6
X
42
=
C
43
=10
X
43
=
C
44
=11
X
44
=
C
45
=4
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=8
X
11
=
C
12
=3
X
12
=
C
13
=1
0
X
13
=
C
14
=9
X
14
=
C
15
=10
X
15
=
A
2
75
C
21
=12
X
21
=
C
22
=14
X
22
=
C
23
=4
X
23
=
C
24
=7
X
24
=
C
25
=14
X
25
=
A
3
45
C
31
=19
X
31
=
C
32
=20
X
32
=
C
33
=14
X
33
=
C
34
=8
X
34
=
C
35
=6
X
35
=
A
4
35
C
41
=14
X
41
=
C
42
=6
X
42
=
C
43
=7
X
43
=
C
44
=12
X
44
=
C
45
=13
X
45
=
Вариант 7
Вариант 8

19
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=5
X
11
=
C
12
=10
X
12
=
C
13
=20
X
13
=
C
14
=13
X
14
=
C
15
=15
X
15
=
A
2
75
C
21
=8
X
21
=
C
22
=7
X
22
=
C
23
=
1
4
X
23
=
C
24
=12
X
24
=
C
25
=14
X
25
=
A
3
45
C
31
=11
X
31
=
C
32
=16
X
32
=
C
33
=18
X
33
=
C
34
=22
X
34
=
C
35
=19
X
35
=
A
4
35
C
41
=21
X
41
=
C
42
=23
X
42
=
C
43
=19
X
43
=
C
44
=10
X
44
=
C
45
=21
X
45
=
Поставщик
Потребит
ель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=8
X
11
=
C
12
=5
X
12
=
C
13
=7
X
13
=
C
14
=4
X
14
=
C
15
=2
X
15
=
A
2
75
C
21
=5
X
21
=
C
22
=6
X
22
=
C
23
=10
X
23
=
C
24
=12
X
24
=
C
25
=3
X
25
=
A
3
45
C
31
=14
X
31
=
C
32
=6
X
32
=
C
33
=4
X
33
=
C
34
=7
X
34
=
C
35
=8
X
35
=
A
4
35
C
41
=5
X
41
=
C
42
=11
X
42
=
C
43
=9
X
43
=
C
44
=10
X
44
=
C
45
=12
X
45
=
Вариант 9
Вариант 10

20
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=8
X
11
=
C
12
=5
X
12
=
C
13
=3
X
13
=
C
14
=4
X
14
=
C
15
=6
X
15
=
A
2
75
C
21
=9
X
21
=
C
22
=9
X
22
=
C
23
=4
X
23
=
C
24
=3
X
24
=
C
25
=10
X
25
=
A
3
45
C
31
=11
X
31
=
C
32
=5
X
32
=
C
33
=6
X
33
=
C
34
=7
X
34
=
C
35
=9
X
35
=
A
4
35
C
41
=12
X
41
=
C
42
=9
X
42
=
C
43
=2
X
43
=
C
44
=3
X
44
=
C
45
=4
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=12
X
11
=
C
12
=14
X
12
=
C
13
=19
X
13
=
C
14
=20
X
14
=
C
15
=9
X
15
=
A
2
75
C
21
=11
X
21
=
C
22
=15
X
22
=
C
23
=16
X
23
=
C
24
=18
X
24
=
C
25
=12
X
25
=
A
3
45
C
31
=21
X
31
=
C
32
=14
X
32
=
C
33
=13
X
33
=
C
34
=15
X
34
=
C
35
=16
X
35
=
A
4
35
C
41
=23
X
41
=
C
42
=15
X
42
=
C
43
=18
X
43
=
C
44
=23
X
44
=
C
45
=10
X
45
=
Вариант 11
Вариант 12

21
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=2
X
11
=
C
12
=3
X
12
=
C
13
=6
X
13
=
C
14
=7
X
14
=
C
15
=1
0
X
15
=
A
2
75
C
21
=5
X
21
=
C
22
=4
X
22
=
C
23
=9
X
23
=
C
24
=8
X
24
=
C
25
=5
X
25
=
A
3
45
C
31
=6
X
31
=
C
32
=10
X
32
=
C
33
=3
X
33
=
C
34
=7
X
34
=
C
35
=12
X
35
=
A
4
35
C
41
=11
X
41
=
C
42
=6
X
42
=
C
43
=8
X
43
=
C
44
=6
X
44
=
C
45
=9
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=10
X
11
=
C
12
=12
X
12
=
C
13
=17
X
13
=
C
14
=13
X
14
=
C
15
=9
X
15
=
A
2
75
C
21
=7
X
21
=
C
22
=14
X
22
=
C
23
=13
X
23
=
C
24
=18
X
24
=
C
25
=20
X
25
=
A
3
45
C
31
=14
X
31
=
C
32
=8
X
32
=
C
33
=15
X
33
=
C
34
=16
X
34
=
C
35
=17
X
35
=
A
4
35
C
41
=6
X
41
=
C
42
=8
X
42
=
C
43
=12
X
43
=
C
44
=13
X
44
=
C
45
=14
X
45
=
Вариант 13
Вариант 14

22
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=1
X
11
=
C
12
=5
X
12
=
C
13
=2
X
13
=
C
14
=4
X
14
=
C
15
=8
X
15
=
A
2
75
C
21
=3
X
21
=
C
22
=6
X
22
=
C
23
=7
X
23
=
C
24
=9
X
24
=
C
25
=4
X
25
=
A
3
45
C
31
=8
X
31
=
C
32
=2
X
32
=
C
33
=5
X
33
=
C
34
=6
X
34
=
C
35
=6
X
35
=
A
4
35
C
41
=1
X
41
=
C
42
=4
X
42
=
C
43
=9
X
43
=
C
44
=7
X
44
=
C
45
=8
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=25
X
11
=
C
12
=22
X
12
=
C
13
=21
X
13
=
C
14
=23
X
14
=
C
15
=24
X
15
=
A
2
75
C
21
=32
X
21
=
C
22
=27
X
22
=
C
23
=28
X
23
=
C
24
=24
X
24
=
C
25
=29
X
25
=
A
3
45
C
31
=26
X
31
=
C
32
=20
X
32
=
C
33
=21
X
33
=
C
34
=30
X
34
=
C
35
=27
X
35
=
A
4
35
C
41
=32
X
41
=
C
42
=33
X
42
=
C
43
=29
X
43
=
C
44
=24
X
44
=
C
45
=28
X
45
=
Вариант 15
Вариант 16

23
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=4
X
11
=
C
12
=5
X
12
=
C
13
=7
X
13
=
C
14
=9
X
14
=
C
15
=3
X
15
=
A
2
75
C
21
=6
X
21
=
C
22
=7
X
22
=
C
23
=8
X
23
=
C
24
=1
1
X
24
=
C
25
=2
X
25
=
A
3
45
C
31
=5
X
31
=
C
32
=9
X
32
=
C
33
=7
X
33
=
C
34
=4
X
34
=
C
35
=3
X
35
=
A
4
35
C
41
=5
X
41
=
C
42
=3
X
42
=
C
43
=8
X
43
=
C
44
=10
X
44
=
C
45
=6
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=3
X
11
=
C
12
=6
X
12
=
C
13
=3
X
13
=
C
14
=8
X
14
=
C
15
=4
X
15
=
A
2
75
C
21
=1
X
21
=
C
22
=2
X
22
=
C
23
=9
X
23
=
C
24
=7
X
24
=
C
25
=8
X
25
=
A
3
45
C
31
=4
X
31
=
C
32
=5
X
32
=
C
33
=6
X
33
=
C
34
=9
X
34
=
C
35
=5
X
35
=
A
4
35
C
41
=3
X
41
=
C
42
=7
X
42
=
C
43
=4
X
43
=
C
44
=2
X
44
=
C
45
=7
X
45
=
Вариант 17
Вариант 18

24
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=10
X
11
=
C
12
=12
X
12
=
C
13
=11
X
13
=
C
14
=17
X
14
=
C
15
=15
X
15
=
A
2
75
C
21
=13
X
21
=
C
22
=
18
X
22
=
C
23
=12
X
23
=
C
24
=10
X
24
=
C
25
=17
X
25
=
A
3
45
C
31
=10
X
31
=
C
32
=13
X
32
=
C
33
=18
X
33
=
C
34
=17
X
34
=
C
35
=16
X
35
=
A
4
35
C
41
=15
X
41
=
C
42
=11
X
42
=
C
43
=12
X
43
=
C
44
=18
X
44
=
C
45
=19
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=23
X
11
=
C
12
=25
X
12
=
C
13
=20
X
13
=
C
14
=19
X
14
=
C
15
=25
X
15
=
A
2
75
C
21
=27
X
21
=
C
22
=28
X
22
=
C
23
=24
X
23
=
C
24
=29
X
24
=
C
25
=26
X
25
=
A
3
45
C
31
=20
X
31
=
C
32
=17
X
32
=
C
33
=18
X
33
=
C
34
=21
X
34
=
C
35
=23
X
35
=
A
4
35
C
41
=24
X
41
=
C
42
=22
X
42
=
C
43
=21
X
43
=
C
44
=23
X
44
=
C
45
=27
X
45
=
Вариант 19
Вариант 20

25
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=7
X
11
=
C
12
=4
X
12
=
C
13
=5
X
13
=
C
14
=6
X
14
=
C
15
=1
0
X
15
=
A
2
75
C
21
=8
X
21
=
C
22
=9
X
22
=
C
23
=7
X
23
=
C
24
=1
1
X
24
=
C
25
=2
0
X
25
=
A
3
45
C
31
=7
X
31
=
C
32
=6
X
32
=
C
33
=2
X
33
=
C
34
=10
X
34
=
C
35
=9
X
35
=
A
4
35
C
41
=5
X
41
=
C
42
=8
X
42
=
C
43
=7
X
43
=
C
44
=14
X
44
=
C
45
=13
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=7
X
11
=
C
12
=14
X
12
=
C
13
=5
X
13
=
C
14
=9
X
14
=
C
15
=1
2
X
15
=
A
2
75
C
21
=10
X
21
=
C
22
=12
X
22
=
C
23
=6
X
23
=
C
24
=4
X
24
=
C
25
=
1
3
X
25
=
A
3
45
C
31
=6
X
31
=
C
32
=8
X
32
=
C
33
=6
X
33
=
C
34
=5
X
34
=
C
35
=11
X
35
=
A
4
35
C
41
=12
X
41
=
C
42
=13
X
42
=
C
43
=8
X
43
=
C
44
=9
X
44
=
C
45
=15
X
45
=
Вариант 21
Ва
риант 22

26
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=12
X
11
=
C
12
=13
X
12
=
C
13
=15
X
13
=
C
14
=19
X
14
=
C
15
=16
X
15
=
A
2
75
C
21
=11
X
21
=
C
22
=10
X
22
=
C
23
=17
X
23
=
C
24
=18
X
24
=
C
25
=16
X
25
=
A
3
45
C
31
=13
X
31
=
C
32
=21
X
32
=
C
33
=20
X
33
=
C
34
=23
X
34
=
C
35
=25
X
35
=
A
4
35
C
41
=16
X
41
=
C
42
=19
X
42
=
C
43
=17
X
43
=
C
44
=14
X
44
=
C
45
=18
X
45
=
Поставщ
ик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=19
X
11
=
C
12
=13
X
12
=
C
13
=14
X
13
=
C
14
=12
X
14
=
C
15
=20
X
15
=
A
2
75
C
21
=21
X
21
=
C
22
=23
X
22
=
C
23
=25
X
23
=
C
24
=13
X
24
=
C
25
=18
X
25
=
A
3
45
C
31
=19
X
31
=
C
32
=9
X
32
=
C
33
=23
X
33
=
C
34
=24
X
34
=
C
35
=29
X
35
=
A
4
35
C
41
=25
X
41
=
C
42
=28
X
42
=
C
43
=27
X
43
=
C
44
=21
X
44
=
C
45
=20
X
45
=
Вариант 23
Вариант 24

27
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=10
X
11
=
C
12
=12
X
12
=
C
13
=17
X
13
=
C
14
=14
X
14
=
C
15
=13
X
15
=
A
2
75
C
21
=18
X
21
=
C
22
=11
X
22
=
C
23
=19
X
23
=
C
24
=12
X
24
=
C
25
=13
X
25
=
A
3
45
C
31
=17
X
31
=
C
32
=15
X
32
=
C
33
=18
X
33
=
C
34
=13
X
34
=
C
35
=11
X
35
=
A
4
35
C
41
=10
X
41
=
C
42
=15
X
42
=
C
43
=12
X
43
=
C
44
=14
X
44
=
C
45
=13
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=11
X
11
=
C
12
=13
X
12
=
C
13
=16
X
13
=
C
14
=13
X
14
=
C
15
=16
X
15
=
A
2
75
C
21
=14
X
21
=
C
22
=15
X
22
=
C
23
=17
X
23
=
C
24
=18
X
24
=
C
25
=16
X
25
=
A
3
45
C
31
=13
X
31
=
C
32
=21
X
32
=
C
33
=2
0
X
33
=
C
34
=20
X
34
=
C
35
=15
X
35
=
A
4
35
C
41
=16
X
41
=
C
42
=19
X
42
=
C
43
=17
X
43
=
C
44
=14
X
44
=
C
45
=18
X
45
=
Вариант 25
Вариант 26

28
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=9
X
11
=
C
12
=13
X
12
=
C
13
=14
X
13
=
C
14
=12
X
14
=
C
15
=10
X
15
=
A
2
75
C
21
=11
X
21
=
C
22
=18
X
22
=
C
23
=20
X
23
=
C
24
=13
X
24
=
C
25
=18
X
25
=
A
3
45
C
31
=19
X
31
=
C
32
=9
X
32
=
C
33
=23
X
33
=
C
34
=24
X
34
=
C
35
=19
X
35
=
A
4
35
C
41
=15
X
41
=
C
42
=18
X
42
=
C
43
=17
X
43
=
C
44
=11
X
44
=
C
45
=12
X
45
=
Поставщик
Потребитель
B
1
B
2
B
3
B
4
B
5
55
90
40
30
20
A
1
80
C
11
=11
X
11
=
C
12
=12
X
12
=
C
13
=15
X
13
=
C
14
=14
X
14
=
C
15
=13
X
15
=
A
2
75
C
21
=18
X
21
=
C
22
=11
X
22
=
C
23
=19
X
23
=
C
24
=12
X
24
=
C
25
=15
X
25
=
A
3
45
C
31
=17
X
31
=
C
32
=16
X
32
=
C
33
=18
X
33
=
C
34
=13
X
34
=
C
35
=11
X
35
=
A
4
35
C
41
=10
X
41
=
C
42
=15
X
42
=
C
43
=12
X
43
=
C
44
=14
X
44
=
C
45
=13
X
45
=
ОГЛАВЛЕНИЕ
Вариант 27

29
Цель контрольной раб
о
ты………………………………………………….
3
Задачи………………………………………………………………………..
3
1.
Основные определ
е
ния……………………………………………………..
3
2.
Методика выполнения контрольной работ
ы ……………………………
4
Библиографический сп
и
сок………………………………………………...
14
Приложение 1……………………………………………………………….
15
Приложение 2……………………………………………………………….
15
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ ПРИ МИНИМИЗАЦИИ ЗАТРАТ РЕСУРСОВ
ДОРОЖНОГ
О СТРОИТЕЛЬСТВА
Метод
и
ческие указания и задание к контрольной работе по дисциплине
«Экономико
-
математические методы в проектировании транспортных
сооружений» для студентов специальности 291000
“Автомобильные дороги и аэродромы ”
Владимир Аполенарьевич
Ярмолинский
Главный редактор
Л. А. Суевалова
Редактор
Л. А. Суевалова
Подписано в печать 20.01.06. Формат 60х84 1/16.
Бумага писчая. Гарнитура «Таймс». Печать офсетная.
Усл. печ. л.1,68 Тираж 200 экз. Заказ
Издательство Т
ихоокеанского государственного
университета. 680035, Хабаровск, ул. Тихоокеанская, 136.
Отдел оперативной полиграфии издательства Тихоокеанского
государственн
о
го университета.
680035, Хабаровск, ул. Тих
о
океанская, 136.
Федеральное агентство по образов
анию

30
Государственное образовательное учреждение
высшего професси
о
нального образования
«Тихоокеанский государственный университет»
Утверждаю в печать
Ректор университета
С. Н. Ива
н
ченко ____________________
« » ___________2005 г.
РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ ПРИ МИНИМИЗАЦИИ ЗАТРАТ
РЕСУРСОВ
ДОРОЖНОГО СТРОИТЕЛЬСТВА
Методические указания к практическим занятиям для студентов
специал
ь
ностей 291000 «Автомобильные дороги и аэродромы»
Составитель:
В. А. Ярмолинский
Рассмотрено и рекомендовано
к изданию кафедрой
«Автомобильные д
орог»
Завкафедрой А. Е. Казаринов
« » ___________2005 г.
Рассмотрено и рекомендовано
к изданию советом ДВАДИ
Председатель совета
А. И. Ярмоли
н
ский
« » ___________2005 г.
Хабаровск
Издательство ТОГУ
2005