Линейное программирование

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

А.С. ШЕВЧЕНКО

Москва
ИНФРА-М
2024

УЧЕБНОЕ ПОСОБИЕ

УДК 004.4(075.32)
ББК 32.973я723
 
Ш37

Шевченко А.С.
Ш37  
Линейное программирование  : учебное пособие / А.С. Шевченко. — 
Москва : ИНФРА-М, 2024. — 253 с. — (Среднее профессио нальное образование). — DOI 10.12737/1899098.

ISBN 978-5-16-017949-0 (print)
ISBN 978-5-16-110959-5 (online)

Учебное пособие содержит практические задания и теоретические сведения, необходимые для изучения раздела «Линейное программирование». 
Изложение сопровождается примерами решения типовых задач. Также пособие содержит примеры решения типовых задач линейного программирования с помощью системы автоматизированного проектирования Mathcad 
Prime и системы компьютерной алгебры Maple.
Соответствует требованиям федеральных государственных образовательных стандартов среднего профессио нального образования последнего 
поколения.
Предназначено для студентов, обучающихся по специальности 09.02.07 
«Информационные системы и программирование».

УДК 004.4(075.32)
ББК 32.973я723

Р е ц е н з е н т :
О.В. Самарина, кандидат физико-математических наук, доцент, руководитель Инженерной школы цифровых технологий Югорского государственного университета

ISBN 978-5-16-017949-0 (print)
ISBN 978-5-16-110959-5 (online)
© Шевченко А.С., 2023

Данная книга доступна в цветном  исполнении 
в электронно-библиотечной системе Znanium

Предисловие

Одной из ключевых компетенций будущего специалиста 
как экономического, так и технического профилей является 
способность применения математических методов в сочетании с информационными технологиями. Способность достижения значимых результатов в профессио нальной деятельности часто напрямую связана с осведомленностью 
о методах и способах решения математических задач с использованием специального программного обеспечения. Владение 
хотя бы одной из систем компьютерной математики (Maple, 
Mathematica, MathCAD, MatLab, Maxima и др.) позволяет будущему специалисту, не владеющему в полной мере техникой 
математических преобразований, самостоятельно выполнять 
громоздкие вычисления, решать сложные прикладные задачи.
В учебном пособии излагаются основы линейного программирования, включая теорию двойственности. Содержатся 
практические задания и теоретические сведения по указанным 
разделам, примеры решения типовых задач, а также рассматриваются решения типовых задач линейного программирования с помощью системы автоматизированного проектирования Mathcad Prime, системы компьютерной алгебры (СКА) 
Maple.
Решение каждого типа задач сопровождается подробным 
пошаговым описанием.
В результате успешного изучения материала по линейному 
программированию студент будет:
знать
 
• основные понятия теории линейного программирования 
(ЛП);
 
• постановку задач ЛП, примеры экономических задач;
 
• методы ЛП, применяемые для решения прикладных задач;
 
• понятие двойственности в ЛП, теоремы двойственности;

Предисловие

 
• алгоритмы решения транспортных задач (ТЗ) и задач о назначениях;
 
• алгоритм решения задачи целочисленного программирования (алгоритм Гомори);
уметь
 
• решать типовые оптимизационные задачи и производить 
оценку качества полученных решений;
 
• решать задачи ЛП графическим и симплексным методами;
 
• решать ТЗ методом потенциалов;
 
• решать задачи о назначениях венгерским методом;
 
• решать целочисленные задачи ЛП методом Гомори;
 
• осуществлять переход от одной формы записи задачи ЛП 
к другой;
владеть навыками
 
• системного анализа содержания математического материала на основе изученной теории;
 
• поиска информации, необходимой для ответа на поставленные вопросы;
 
• практической работы по решению оптимизационных задач;
 
• решения задач линейного программирования с использованием САПР Mathcad Prime, СКА Maple.

Глава 1. 
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКИХ 
МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО 
ПРОГРАММИРОВАНИЯ

1.1. ОБЩАЯ СХЕМА ПОСТРОЕНИЯ МАТЕМАТИЧЕСКИХ 
МОДЕЛЕЙ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Моделью является система, которая способна заменить 
оригинал исходной системы таким образом, чтобы при изучении ее можно было получить информацию об оригинале. 
С помощью модели есть возможность частично или полностью воспроизвести структуру и функции моделируемой 
системы. Таким образом, моделированием является процесс 
построения и исследования модели, способный заменить реальную систему и дать о ней необходимую информацию.
Математическая модель представляет собой систему 
математических и логических соотношений, описывающих 
структуру и функции реальной системы.
Для построения математической модели задачи линейного 
программирования (ЗЛП) необходимо:
1) ввести переменные;
2) сформировать целевую функцию;
3) сформировать систему ограничений;
4) наложить условия неотрицательности переменных 
(или указать интервалы изменения введенных переменных).

1.2. ЗАДАЧА ОБ ОПТИМАЛЬНОМ ИСПОЛЬЗОВАНИИ 
РЕСУРСОВ (ЗАДАЧА ПЛАНИРОВАНИЯ ПРОИЗВОДСТВА)

Рассмотрим важнейшую задачу линейного программирования. Это задача об оптимальном использовании ресурсов. 

Глава 1.  Построение математических моделей задач линейного...

Пусть на предприятии выпускается n разных видов изделий 

1
2
 
,
,...,
n
P P
P . Для изготовления этих изделий требуется m разных 
типов ресурсов 
1
2
,
,...,
m
S
S
S . В качестве ресурсов могут выступать людские ресурсы, различные виды материалов и сырья, 
электроэнергия, запасы машинного времени и т.д. Более того, 
объем каждого типа ресурсов является ограниченным и составляет соответственно 1
2
,
,...,
m
b b
b  условных единиц.
Известными данными также считаются технологические 
коэффициенты 
,
ij
a  которые показывают, сколько единиц каждого i-го ресурса 
iS  требуется для производства единицы j-го 
вида изделия 
(
1,
;
1, )
j
P i
m
j
n
=
=
. Кроме того, известна и прибыль 
jc , которая получается от реализации единицы изделия 

j
P , 
1,
j
n
=
.
Все показатели bi, aij и cj в планируемый период предполагаются постоянными величинами. Необходимо определить 
оптимальный план по выпуску продукции, чтобы прибыль 
от реализации продукции была максимальной.
Все необходимые данные задачи представлены в табл. 1.1.

Таблица 1.1
Исходные данные задачи

Виды ресурсов
Виды изделия
Запасы 
ресурсов
P1
P2
…
Pj
…
Pn
S1
a11
a12
…
a1j
…
a1n
b1

S2
a21
a22
…
a2j
…
a2n
b2

…
…
…
Si
ai1
ai2
…
aij
…
ain
bi

…
…
…
Sm
am1 am2
…
amj
…
amn
bm

Прибыль от реализации 
единицы изделия
c1
c2
…
cj
…
cn
—

1.2. Задача об оптимальном использовании ресурсов...

Составим математическую модель задачи. Для этого введем 
необходимые обозначения:

1
x  — количество производимых изделий вида 1
P;

2
x  — количество производимых изделий вида 2
P ;
…

n
x  — количество производимых изделий вида n
P .
Для производства всех изделий вида 1
P потребуется использовать ресурс вида 
1
S  в количестве 
11 1
a x  условных единиц. 
Общее количество ресурса 1
S , используемого при выпуске всех 
видов изделий, определяется выражением 
11 1
12
2
...
+
+
+
a x
a x

+ a1nxn. Количество ресурса 
1
S  ограничено величиной 1b . Поскольку расход ресурса 
1
S  не может превосходить его запаса, 
должно выполняться неравенство 
11 1
12
2
1
1
...
n
n
a x
a x
a x
b
+
+
+
≤
. 
В общем виде расход i-го ресурса не должен быть больше ib , 
по это му соответствующее неравенство имеет вид ai1x1 +

2
2
...
+
+
+
≤
i
in
n
i
a x
a x
b . Для всех используемых видов ресурсов 
должны выполняться такие ограничения (это ограничения 
по объему соответствующего ресурса). Другими словами, 
при производстве по заданному плану можно использовать 
либо весь запас этого ресурса, либо его часть.
Более того, введенные обозначения должны быть больше 
нуля или равны нулю, 
1
2
,
,...,
0
n
x
x
x ≥ , поскольку количество 
выпускаемых изделий не может быть меньше нуля.
Доход от реализации всех изделий вида 
1
P  равен 1 1
с x  денежных единиц. Общая прибыль, которая получается 
от реализации (продажи) всей продукции 1
2
 
,  
,...,
n
P
P
P , производимой соответственно в количестве 
1
2
,
,...,
n
x
x
x  единиц, записывается в виде линейной функции 
1 1
2
2
(
)
...
Z X
c x
c x
=
+
+
+

+ cnxn.
Требуется составить такой оптимальный план объема выпускаемой продукции 
1
2
(
,
,...,
)
n
X
x
x
x
=
, при котором прибыль 

(
)
Z X  будет наибольшей. Функция (
)
Z X  определяет цель производства — получение наибольшей прибыли. (
)
Z X  — целевая 
функция, или функция цели.

Глава 1.  Построение математических моделей задач линейного...

Таким образом, математическая модель задачи использования ресурсов в общей постановке формулируется следующим образом: требуется определить оптимальный план 
по объему выпускаемой продукции 
1
2
(
,
,...,
)
n
X
x
x
x
=
, который 
удовлетворяет ограничениям

 

11 1
12
2
1
1

21 1
22
2
2
2

1 1
2
2

,
,
                       

n
n

n
n

m
m
mn
n
m

a x
a x
a x
b
a x
a
x
a
x
b

a
x
a
x
a
x
b

+
+
+
≤
⎧
⎪
+
+
+
≤
⎪⎨
⎪
⎪
+
+
+
≤
⎩

…
…
…
…

 

и условиям неотрицательности

 
1
2
0,
0,...,
0
≥
≥
≥
n
x
x
x
, 

при котором полученная целевая функция достигнет максимального значения:

 
( )
1 1
2
2
...
max
n
n
Z X
c x
c x
c x
=
+
+
+
→
. 

Пример 1.1
Прибыль, полученная от реализации продукции 1
P, составляет 40 руб., а от единицы продукции 
2
P , — 50 руб. Данные 
о запасах и количестве ресурсов представлены в табл. 1.2.

Таблица 1.2
Данные для примера 1.1

Виды ресурсов
Запасы 
ресурсов

Число единиц ресурса, которое затрачивается на изготовление единицы соответствующей продукции
P1
P2
S1
41
2
3
S2
38
3
6
S3
26
—
3
S4
34
6
—

1.3. Задача составления рациона (задача о диете, задача о смесях)

Определите оптимальный план по производству продукции, который обеспечивал бы получение наибольшей прибыли от реализации изготавливаемой продукции.
Математическая модель данной задачи будет иметь следующий вид:

 
(
)
1
2
1
2
,
40
50
max,
Z x
x
x
x
=
+
→
 

 

1
2

1
2

2

1

1
2

2
3
41,
3
6
38,
          3
26,

          6
34,

0,
0.

x
x
x
x
x

x

x
x

+
≤
⎧
⎪
+
≤
⎪⎪
≤
⎨
⎪
≤
⎪
≥
≥
⎪⎩

 

1.3. ЗАДАЧА СОСТАВЛЕНИЯ РАЦИОНА 
(ЗАДАЧА О ДИЕТЕ, ЗАДАЧА О СМЕСЯХ)

Другой классической задачей линейного программирования является задача определения оптимального набора пищевых продуктов для составления рациона диеты.
Задача имеет следующую постановку. Дневная диета содержит m видов различных питательных веществ 
1
2
,
,
,
m
S S
S
…
, 
которых, соответственно, не менее 
1
2
,
,
,
m
b b
b
…
 условных 
единиц. Имеется n различных видов продуктов 
1
2
 
,
,
,
n
P P
P
…
, 
каждый из которых содержит m различных питательных веществ (жиры, белки, углеводы и т.д.). Пусть 
ij
a  — количество 
единиц i-го питательного вещества в единице веса j-го продукта; jc  (
1, )
j
n
=
 — стоимость единицы веса продукта с j-м номером. Необходимо определить состав и количество продуктов, которые нужно включить в диету. При этом суточные 
потребности должны быть удовлетворены с минимальными 
денежными затратами. Исходные данные задачи представлены в табл. 1.3.

Глава 1.  Построение математических моделей задач линейного...

Составим математическую модель задачи. Для этого введем 
необходимые обозначения:

1
x  — количество потребления продукта вида 1
P;

2
x  — количество потребления продукта вида 2
P ;
…

n
x  — количество потребления продукта вида n
P  в сутки.

Таблица 1.3
Исходные данные задачи

Виды питательных веществ

Виды продуктов
Минимальная суточная потребность 
в питательном веществе, усл. ед.
P1
P2
…
Pj
…
Pn

S1
a11
a12
…
a1j
…
a1n
b1
S2
a21
a22
…
a2j
…
a2n
b2
…
…
…
Si
ai1
ai2
…
aij
…
ain
bi

…
…
…
Sm
am1
am2
…
amj
…
amn
bm
Стоимость единицы веса продукта

c1
c2
…
cj
…
cn
—

В результате потребления 
1
x  единиц продукта вида 1
P  содержание питательного вещества 1
S  в суточной норме потребления составит 
11 1
a x  условных единиц. Общее содержание 
питательного вещества 
1
S  в рационе определяется выражением 
11 1
12
2
1n
n
а х
а х
а x
+
+
+
…
. Поскольку содержание питательного вещества 1
S  в рационе не может быть меньше минимальной суточной потребности организма, т.е. величины 1b , 
то должно выполняться неравенство 11 1
12
2
1
+
+
+
n
n
а х
а х
а x
…
 ≥ 
≥ b1. В общем виде содержание i-го питательного вещества 
в рационе не должно быть меньше 
ib , по это му необходимо 
выполнение неравенства 
1 1
2
2
i
i
in
n
i
а х
а х
а x
b
+
+
+
≥
…
. Выпол