Линейное программирование. Транспортная задача

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ 

УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ 

СТАВРОПОЛЬСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ТРАНСПОРТНАЯ ЗАДАЧА

Учебное пособие

г. Ставрополь

2017

УДК 51 (075.8)
ББК 22.1я73

Литвин, Д.Б.
Линейное программирование. Транспортная задача: Учебное пособие / Д.Б.
Литвин, С.В. Мелешко, И.И. Мамаев. – Ставрополь : Сервисшкола, 2017. – 84с.

Пособие предназначено для студентов направления Экономика - 38.03.01 оч
ной и заочной форм обучения. 

Содержание материала в целом соответствует первой части дисциплины

«Методы оптимальных решений».

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ ........................................................................................................................................4

1.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ..................................................................................5

1.1.
Общая задача линейного программирования...................................................................5

1.2.
Геометрический смысл системы неравенств....................................................................6

1.3.
Геометрический метод решения ЗЛП с n=2 .....................................................................8

1.3.1.
План решения ЗЛП геометрическим методом ..........................................................8

1.3.2.
Пример решения ЗЛП на плоскости (с n=2)............................................................10

1.4.
Анализ моделей на чувствительность.............................................................................16

1.4.1.
Анализ изменений запасов ресурсов........................................................................16

1.4.2.
Определение наиболее выгодного ресурса .............................................................19

1.4.3.
Определение пределов изменения коэффициентов целевой функции.................20

1.5.
Геометрическое решение ЗЛП с n>2 ...............................................................................27

1.6.
Введение в симплекс-метод решения ЗЛП.....................................................................29

1.7.
Геометрическая интерпретация симплекс-метода.........................................................31

1.8.
Критерий оптимальности симплекс - метода.................................................................33

1.9.
Алгоритм решения ЗЛП симплекс-методом...................................................................33

1.9.1.
Выбор исключаемой базовой переменной ..............................................................33

1.9.2.
Алгоритм решения ЗЛП симплекс-методом ...........................................................35

1.10.
Метод искусственного базиса (M - метод)..................................................................41

1.11.
Двойственность в задачах линейного программирования ........................................47

1.12.
Экономические приложения двойственных оценок ..................................................53

2.
ТРАНСПОРТНАЯ ЗАДАЧА...................................................................................................59

2.1.
Общая постановка задачи.................................................................................................59

2.2.
Методы построения первоначального опорного плана.................................................61

2.2.1.
Метод северо-западного угла ...................................................................................61

2.2.2.
Метод минимального элемента ................................................................................64

2.2.3.
Метод аппроксимации Фогеля .................................................................................65

2.3.
Формулировка критерия оптимальности решения ТЗ...................................................68

2.4.
Алгоритм решения ТЗ методом потенциалов ................................................................71

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА №1 ................................................................................80

РАСЧЕТНО-ГРАФИЧЕСКАЯ РАБОТА №2 ................................................................................82

ЛИТЕРАТУРА..................................................................................................................................84

ВВЕДЕНИЕ

Данное издание призвано помочь освоить студентам экономических спе
циальностей использование методов линейного программирования в организационно-экономических и производственных системах.

Оптимизационные модели позволяют найти из множества возможных 

(альтернативных) вариантов наилучший план производства, распределения капиталовложений или составления какой-либо смеси и пр. При этом запас ресурсов будет использован наиболее эффективным образом для достижения поставленной цели. 

Целью изучения данного раздела математики является знакомство с зада
чами организационно-экономического управления и освоение математических 
методов как инструмента их решения. 

В процессе изучения у студентов должны быть сформированы теоретиче
ские знания, необходимые для моделирования экономических систем и решения поставленных математических задач, а также практические навыки такого 
решения и анализа полученных результатов. 

1.
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

1.1. Общая задача линейного программирования

Пусть задана система m линейных уравнений и неравенств с n перемен
ными:

21 1
22
2
2
2

1 1
2
2

1,2

...

...

0

n
n

m
m
mn
n
m

n

a x
a x
a x
b

a x
a
x
a x
b

x
















или
m n
n
m
A
x
B


(1)

и линейная функция 

1 1
2
2
...
T

n
n
z
c x
c x
c x
c x





(2)

Необходимо найти такое решение системы 



*

1
2
;
;...;

T

n
x
x x
x

, при кото
ром линейная функция z принимает оптимальное (max или min) значение.

Систему (1) называют системой ограничений, а функцию z - линейной це
левой функцией, или функцией цели.

Оптимальным решением или оптимальным планом ЗЛП называется та
кое решение 



*

1
2
;
;...;

T

n
x
x x
x

системы ограничений, при котором линейная 

функция z принимает оптимальное значение.

Если система ограничений (1) состоит из одних неравенств, то считается, 

что ЗЛП задана в стандартном виде; если же из одних уравнений, то - в каноническом виде; если же есть уравнения и неравенства - то в общем виде.

Чтобы перейти от стандартного задания к каноническому виду, вводят 

дополнительные неотрицательные переменные:

со знаком «+», если функция 
b

,

со знаком «-», если функция 
b

.

Пример: Пусть задана общая система ограничений:

1
2
1
2

1
2
1
2

1
2
3
1
2

1
2
4
1
2

1
2
5
1
2

1,2
1,2,3,4,5

2
3
5
2
3
5

0
0

2
3
2
2
3
2

5
3
5
3

2
2

0
0

общая задача
каноническая задача

x
x
x
x

x
x
x
x

x
x
x
x
x

x
x
x
x
x

x
x
x
x
x

х
х

























































1.2.
Геометрический смысл системы неравенств

Пусть дана система линейных неравенств с двумя переменными:

11 1
12
2
1

21 1
22
2
2

1 1
2
2
m
m
m

a x
a x
b

a x
a x
b

a x
a
x
b














(3)

Геометрический смысл неравенства 
11 1
12
2
1
a x
a x
b


- полуплоскость, 

все точки которой ему удовлетворяют. Уравнение
11 1
12
2
1
a x
a x
b


определя
ет на плоскости 
1
2
ОХ Х прямую, которая называется граничной.

В том случае, если система неравенств (3) совместна, область ее допусти
мых решений (ОДР) есть множество точек, принадлежащих всем указанным 
полуплоскостям. 

Множество называется выпуклым, если оно вместе со своими любыми 

двумя точками содержит весь отрезок, соединяющий эти точки. Или для любых 
двух точек 
1x и 
2x , принадлежащих множеству Х, ему принадлежат также все 

точки х, для которых справедливо равенство



1
2
1
x
x
x





,     0
1


 .

Рисунок 1 - К определению выпуклого множества

Область допустимых решений D может быть замкнутой (ограниченной), 

открытой (неограниченной) и пустым множеством (система ограничений противоречива) , как показано на рисунке 2 для плоскости.

Рисунок 2 - Виды областей допустимых решений (ОДР)

Доказывается, что ОДР ЗЛП - всегда выпуклое множество точек.

Область допустимых решений задается с помощью системы неравенств (3).

D

выпуклое
невыпуклое

D

Ø

D

замкнутая
(ограниченная)

D

открытая
(неограниченная)

Пример 1. Построить множество (область) ДР для системы неравенств:

1
2

1
2

1
2

2

1,2

5
4
20

2
3
24

3
3

6

0

x
x

x
x

x
x

x

x



















Уравнения линий:

1
1
2
:
5
4
20
x
x



1x
0 -4

2x
5 0

2
1
2
: 2
3
24
x
x



1x
0 12

2x
8 0

3
1
2
:
3
3
x
x



1x
0
3

2x
-1 0

4
2
:
6
x  ;

5
1
:
0
x  ;        
6
2
:
0
x 
.

Рисунок 3 - Область допустимых решений (ОДР)

Для определения полуплоскости, которая удовлетворяет соответствую
щему неравенству, удобно использовать координаты точки О (0;0). Если при их 
подстановке в неравенство, оно является истинным, то это неравенство определяет всю полуплоскость, содержащую начало координат.



0
0
20
верно


;   


0
0
24
верно


;    


0
0
3
верно


.

Точки О, А, В, С, Д, Е - вершины области решений или угловые точки.
Геометрический смысл системы неравенств на плоскости – это вы
пуклая область (многоугольник), каждая точка которой является допустимым 
решением ЗЛП.

По аналогии заключаем, что ОДР в пространстве, определяемая систе
мой неравенств с 3-мя переменными, может представлять выпуклый многогранник.

С

Д

Е

А

В

1

0
3
1


6

12

2x

4


3


2

4

1x

8

5

Если систему ограничений (3) привести к каноническому виду добавле
нием новых переменных
3
4
2
,
,...,
m
x x
x  , например для рассматриваемой задачи 

1
2

1
2

1
2

2

1,2

5
4
20

2
3
24

3
3

6

0

x
x

x
x

x
x

x

x




















1
2
3

1
2
4

1
2
5

2
6

1,2

5
4
20

2
3
24

3
3

6

0

x
x
x

x
x
x

x
x
x

x
x

x























,

то подстановкой координат точек можно убедиться, что области ДР будут 

соответствовать только неотрицательные значения дополнительных переменных. При этом в угловых точках ОДР дополнительные переменные, соответствующие пересекающимся линиям, равны нулю. Например, в точке Д (см. рисунок 3), где пересекаются линии 
1 и 
3, нулю равны переменные 
3x и 
5x .

1.3.
Геометрический метод решения ЗЛП с n=2

Геометрический способ решения ЗЛП целесообразно использовать для:
 решения задач с двумя переменными, когда ограничения выражены 

неравенствами;

 решения задач со многими переменными при условии, что в их кано
нической записи содержится не более двух свободных переменных.

Рассмотрим ЗЛП в стандартной форме с двумя переменными:

11 1
12
2
1

21 1
22
2
2

1 1
2
2
m
m
m

a x
a x
b

a x
a x
b

a x
a
x
b














(4)



1 1
2
2
max min
z
c x
c x



(5)

Целевая функция (5) определяет на плоскости семейство параллельных 

прямых, каждой из которых соответствует определенное значение Z.

1.3.1. План решения ЗЛП геометрическим методом

1. Строится ОДР X. Если X  , то задача не имеет решения.
2. Строим вектор градиента целевой функции

 


1
2

1
2

;
;
z
z
N
grad z
c c
x
x















- нормальный вектор, он указывает направление возрастания целевой 

функции z.

Прямая, перпендикулярная вектору 


1
2
;
N c c
, определяет множество 

равных значений целевой функции




1

1 1
2
2
1
2

2

x
z
c x
c x
c
c
const
x












3. Строим прямую равных значений 
0 , проходящую через начало коор
динат

1 1
2
2
0
z
c x
c x



.

В каждой точке этой прямой целевая функция равна нулю.

4. Мысленно перемещаем прямую
0 в направлении вектора 


1
2
;
N c c
, 

тогда:

ближайшая угловая точка встречи 
0 с областью X является точкой min z, 

а самая дальняя угловая точка встречи, является точкой max z.

Рисунок 4 - Геометрический метод решения ЗЛП

На втором рисунке задача на max решений не имеет, т.е. Z не ограничена 

сверху (аналогично может быть не ограничен min).

Замечание. Если прямая 
0 при перемещении совпадает с отрезком об
ласти X, то все точки этого отрезка являются решениями задачи. В этом случае 
оптимальных решений бесчисленное множество.

Поскольку, ОДР ЗЛП на плоскости представляет собой выпуклый много
угольник, то оптимальное решение ЗЛП находится, по крайней мере, в одной из угловых точек ОДР.

 
  max

min





C
Z

E
Z

В

Е

С
А

Д

0
0


N

1x

2x

 

Ø
max

min




A
Z

0

2x

1x

А
С

0


N

В