Основы линейного программирования

Основы линейного 
программирования
Учебное пособие

УДК 519.8
ББК 22.18
       О-75
Издание доступно в электронном виде на портале ebooks.bmstu.ru
по адресу: http://ebooks.bmstu.ru/catalog/193/book1755.html
Факультет «Информатика и системы управления»
Кафедра «Системы обработки информации и управления»
Рекомендовано Редакционно-издательским советом
МГТУ им. Н.Э. Баумана в качестве учебного пособия
Авторы:
В.В. Чистов, М.В. Аксенова, Н.В. Аксенов,
И.Г. Булатова, А.Д. Правдина
Рецензент Т.Н. Захарова
О-75
Основы линейного программирования : учебное пособие / 
 
[В. В. Чистов и др.]. — Москва : Издательство МГТУ им. Н. Э. Баумана, 2017. — 64, [4] с. : ил.
ISBN 978-5-7038-4628-5
Изложены методы решения задач линейного программирования 
симплекс-методом. Рассмотрены задачи планирования производства, 
принятия решений в условиях неопределенности, задачи теории игр и 
транспортные задачи.
Для студентов, изучающих курс «Исследование операций». Пособие 
может быть использовано при изучении других курсов, посвященных 
разработке программного и математического обеспечения.
УДК 519.8
ББК 22.18
©	МГТУ им. Н.Э. Баумана, 2017
©	Оформление. Издательство 
	
МГТУ им. Н.Э.Баумана, 2017
ISBN 978-5-7038-4628-5 

ПРЕДИСЛОВИЕ
В учебном пособии изложены принципы и примеры решения 
задач линейного программирования (ЗЛП). Цель пособия — научить 
студентов формулировать и решать подобные задачи. 
В первой главе пособия рассмотрен симплекс-метод решения 
ЗЛП, описан алгоритм решения, включающий поиск опорного 
и оптимального планов, введено понятие двойственности ЗЛП, 
а также приведены примеры решения с помощью табличного 
симплекс-метода.
Во второй главе представлены задачи и критерии принятия 
решений в условиях неопределенности, а также элементы теории 
игр. Изложение подкреплено рассмотрением конкретного примера решения ЗЛП.
В третьей главе дано определение транспортной задачи как 
разновидности ЗЛП, указаны ее особенности, предложены два 
способа решения указанной задачи. Рассмотрен распределительный метод решения транспортной задачи, уделено внимание 
практическому применению метода «северо-западного угла».
В приложении приведены курсовые задания.
Учебное пособие предназначено для студентов, изучающих курс 
«Исследование операций», а также курсы, связанные с разработкой 
математического обеспечения. Приведенные в учебном пособии 
материалы позволят студентам освоить навыки и приемы, необходимые для выполнения и защиты курсового задания.

1. АНАЛИТИЧЕСКИЙ МЕТОД РЕШЕНИЯ 
ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Задача линейного программирования (ЗЛП) формулируется 
следующим образом: найти экстремальное значение целевой 
функции 
n
F
a
a
x
j
j
=
+
⋅
j
=
∑
00
1
0


 ,
удовлетворяющее системе ограничений Ω:
n
ij
j
i
a
x
b
j
1
, 
 




 


 


∀
∈
…
{
}
i i
m
:
, ,
,
.
1 2
=
∑
⋅
≤
1.1. Симплекс-метод
Схема общего алгоритма решения ЗЛП представлена на рис 1.1.
Рассмотрим подробнее требования (A, B, C, D) и операторы (K, 
L, M, N, P), которые позволяют найти решение ЗЛП.
Требование А
Найти наибольшее значение целевой функции — [max]F. Если 
речь идет о минимизации функции F, то достаточно записать, что 
необходимо максимизировать (–F ), а именно:
min F = max (–F ) (оператор М).
Требование В
Любое ограничение из множества ограничений Ω имеет знак 
«≤», т. е. 
n
ij
j
i
a
x
b
j
1

, 
 




 

∀
∈
…
{
}
i i
m
:
, ,
,
.
1 2
=
∑
⋅
≤
4

Рис 1.1. Общий алгоритм решения ЗЛП:
A, B, C, D — требования; K, L, M, N, P — операторы
Если существует ограничение вида
n
ij
j
i
a
x
b
j
1
,
=
∑
⋅
≥
то достаточно умножить его на (–1), чтобы требование В выполнялось (оператор N).
Требование C
Должны быть неотрицательными значения переменных 
x
j
n
j ≥
∀∈
…
{
}
0
1 2
,
, ,
,
.

 
 



 Если существуют переменные, принимающие отрицательные значения, то достаточно произвести замену: 
x j  = 
 ′ −′′
x
x
j
j,  где 
 
 


 

′
′′ >
x
x
j
j
,
0  (оператор P).
Требование D
Должны быть неотрицательными значения свободных членов 
в множестве ограничений Ω:
b
i
i
m
i ≥
∀
∈
…
{
}
0
1 2
,
:
, ,
,
.

 
 






 
Если существует отрицательный свободный член, то следует 
выполнить оператор K (поиск опорного решения), в противном 
случае необходимо выполнить оператор L (поиск оптимального 
решения).
	
5

Bведем понятие основной задачи линейного программирования 
(ОЗЛП).
Смысл перехода к ОЗЛП заключается в замене всех неравенств 
в ограничениях множества равенствами с помощью введения новых переменных.
Пусть задана ЗЛП:
[max] F + a00  = a
x
01
1
⋅
 + a
x
02
2
⋅
,
a
x
31
1
⋅
 + a
x
32
2
⋅

  ≤ a30,
a
x
41
1
⋅
 + a
x
42
2
⋅
 ≤ a40.
Необходимо перейти к ОЗЛП.
Решение:
[max] F + a00 = a
x
01
1
⋅
 + a
x
02
2
⋅
+

 



 0 


⋅
+
x3
 0 


⋅x4 ,
a
x
31
1
⋅
 + a
x
x
32
2
3
1
⋅
+ ⋅
+





 0 


⋅x4  = a30,
a
x
41
1
⋅
 + a
x
x
42
2
3
0
⋅
+ ⋅
+





 1 


⋅x4  = a40.
Вновь введенные переменные x j
  (n + 1 ≤ j ≤ n + m), обозначающие разность между левой и правой частями неравенства, 
называют базисными. Остальные переменные xi
  (1 ≤ i ≤ n) называют свободными, а множество индексов, которыми помечены 
базисные переменные, — базисом В = {n + 1, n + 2, …, n + m}.
В нашем примере В = {3, 4}, свободные переменные — x
x
1
2



 

,
,  
базисные переменные — x
x
3
4



 

,
.  Сформируем исходную симплекстаблицу (табл. 1.1). В нулевую строку таблицы заносим коэффициенты целевой функции. Остальные строки таблицы заполняем 
коэффициентами уравнений-ограничений.
                                                       Таблица 1.1
Исходная симплекс-таблица
1
2
3
4
0
0
a01
a02
0
0
a00
3
a31
a32
1
0
a30
4
a41
a42
0
1
a40
Обычно в симплекс-таблицах не записывают столбцы при 
базисных переменных, тогда табл. 1.1 принимает вид табл. 1.2.
6

                                            Таблица 1.2
Симплекс-таблица 
1
2
0
0
a01
a02
a00
3
a31
a32
a30
4
a41
a42
a40
Далее перейдем к рассмотрению операторов L и K, которые 
позволяют найти решение любой ОЗЛП.
Оператор L (поиск оптимального решения)
Пусть ОЗЛП ([max] F, Ω) имеет решение R = (
,
x1
  x2
,  …, xn m
+

 ). 
Предположим, что найден такой оператор L, который позволит 
записать эту задачу в виде ([max] F ′, Ω′), т. е. L([max] F, Ω) = 
= ([max] F ′, Ω′), где все коэффициенты при свободных переменных 
в F ′ отрицательны, а свободные члены в уравнениях-ограничениях положительны.
Тогда по внешнему виду этой задачи можно будет легко определить ее решение, и это решение будет оптимальным, так как 
улучшить его по причине отрицательности коэффициентов при 
свободных переменных нельзя. 
Действительно, все коэффициенты при свободных переменных 
в функции F ′ отрицательны. Учитывая, что xi
 
 ≥ 0, увеличивая xi
, 
мы не можем увеличить F ′. Cледовательно, при xi
  = 0 (xi
  — свободные переменные ) получаем максимальное значение целевой 
функции F ′ = a00
,  и тогда решением будет следующее:
R: { xi
  = 0, ∀
∈
…
{
}
i
i
n



 


:
, ,
,
1 2
 (xi
  — свободные переменные),
x j
  = aj
j
0,
:

 
 


∀
 j ∈ B (x j
  — базисные переменные)}.
Оператор L позволяет записать задачу ([max] F, Ω) в виде 
([max] F ′, Ω′) за несколько итераций. Итерация возможна в том 
случае, когда существует положительный коэффициент при свободной переменной в целевой функции. Тогда действие оператора 
L на каждой итерации сводится к эквивалентному преобразованию, 
заключающемуся во введении свободной переменной, у которой 
коэффициент в целевой функции положительный, в базис и исключении другой переменной из базиса, что делает ее свободной. 
Указанные эквивалентные преобразования удобно проводить 
	
7