Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Математическое программирование

Покупка
Основная коллекция
Артикул: 875908.01.99
Доступ онлайн
500 ₽
В корзину
Учебное пособие составлено на основе курса лекций, который читается автором для студентов IV курса факультета бизнеса Новосибирского государственного технического университета. В нем излагаются такие разделы математического программирования, как линейное программирование, целочисленное линейное программирование и динамическое программирование. Пособие может быть полезно студентам других специальностей, изучающим методы оптимизации, а также специалистам, которые занимаются решением прикладных оптимизационных задач на основе математического моделирования.
Гусев, С. А. Математическое программирование : учебное пособие / С. А. Гусев. - Новосибирск : Изд-во НГТУ, 2023. - 134 с. - ISBN 978-5-7782-4996-7. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2246192 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство науки и высшего образования Российской Федерации 
НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ 
 
 
 
 
 
 
С. А. ГУСЕВ 
 
 
 
 
 
МАТЕМАТИЧЕСКОЕ  
ПРОГРАММИРОВАНИЕ 
 
 
Утверждено Редакционно-издательским советом университета 
в качестве учебного пособия 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
НОВОСИБИРСК 
2023 
 


УДК 519.85(075.8) 
         Г962 
 
 
Рецензенты: 
канд. экон. наук, науч. сотр. ИВМ и МГ СО РАН О. А. Ляхов 
канд. техн. наук, доцент Г. Ы. Токтошов 
 
 
 
Работа подготовлена кафедрой экономической информатики  
для студентов, обучающихся по направлению 38.03.05  
«Бизнес-информатика» 
 
Гусев С. А. 
Г962   
Математическое программирование: учебное пособие /  
С. А. Гусев. – Новосибирск: Изд-во НГТУ, 2023. – 134 c. 
 
ISBN 978-5-7782-4996-7 
 
Учебное пособие составлено на основе курса лекций, который читается автором для студентов IV курса факультета бизнеса Новосибирского государственного технического университета. В нем излагаются 
такие разделы математического программирования, как линейное программирование, целочисленное линейное программирование и динамическое программирование. Пособие может быть полезно студентам 
других специальностей, изучающим методы оптимизации, а также специалистам, которые занимаются решением прикладных оптимизационных задач на основе математического моделирования. 
 
 
УДК 519.85(075.8) 
 
 
 
ISBN 978-5-7782-4996-7  
 
 
 
 
 
 
© Гусев С. А., 2023 
© Новосибирский государственный 
    технический университет, 2023 
 


 
 
 
 
 
 
ÂÂÅÄÅÍÈÅ 
Значительное число задач, возникающих в экономике, представляют 
собой оптимизационные задачи планирования производства, т. е. задачи, в которых при заданных условиях производства требуется определить параметры, обеспечивающие минимальные или максимальные 
значения некоторых показателей производственной деятельности. 
Как правило, оптимизационные задачи для нахождения оптимальных 
производственных планов ‒ это задачи минимизации затрат или максимизации прибыли. Для их решения математическими методами требуется сформулировать экономическую постановку на языке математики, 
т. е. построить математическую модель. В результате получаются задачи нахождения минимальных или максимальных значений некоторых 
функций при заданных ограничениях на переменные. Задачи такого 
типа относят к условно-экстремальным задачам. 
При определении оптимального производственного плана даже одного небольшого предприятия бывает необходимо учитывать и объединять в одно целое большое количество связей и числовых значений всевозможных характеристик. Соответственно при этом возникают довольно сложные математические задачи, решение которых аналитически возможно лишь в исключительных случаях, но может быть успешным в результате построения математических моделей и применения 
специально разработанных численных методов. 
Теория и численные методы решения многомерных экстремальных 
задач есть предмет изучения такой области математики, которая называется математическим программированием. Термин «программирование» связан с тем, что большинство решаемых задач определяет план 
(программу) функционирования экономической системы (ЭС). 
Большинство оптимизационных задач, решаемых методами математического программирования, есть задачи нахождения максимума 


(минимума) некоторой заданной целевой функции 
(
,
,
)
n
f x
x

, на переменные которой наложены ограничения вида 
1
1
1
1
(
,
,
)
,
(
,
,
)
,
n
m
n
m
g
x
x
b
g
x
x
b





 
где 
1,
,
n
g
g

 – некоторые заданные функции. 
В математическом программировании выделяют следующие основные разделы в зависимости от вида целевой функции и ограничений. 
Линейное программирование – целевая функция линейна, а множество, на котором ищется экстремум, задается системой линейных равенств и неравенств. 
Целочисленное программирование – на переменные накладывается условие целочисленности. 
Нелинейное программирование – целевая функция и ограничения 
нелинейные. 
К нелинейному программированию относятся следующие разделы. 
Выпуклое программирование – целевая функция выпукла, если 
решается задача минимизации, и вогнута, если решается задача максимизации, а множество, на котором ищется экстремум функции, – выпукло. 
Квадратичное программирование – целевая функция представляет собой квадратичную форму, а ограничения – линейные равенства 
и неравенства. 
Стохастическое программирование – задачи оптимизации, которые содержат случайные параметры в функциях, задающих ограничения. 
Приведем примеры некоторых задач, которые решаются методами 
математического программирования. 
1. Задача о рационе. По заданному ассортименту продуктов при известном содержании в них питательных веществ и известной стоимости 
продуктов составить рацион, удовлетворяющий необходимым потребностям с минимальными затратами на покупку продуктов. 
Пусть имеется n  продуктов и m питательных веществ. Пусть 
ij
a  – 
содержание j -го питательного вещества в единице веса i-го продукта; 


через 
jb  обозначим минимальную суточную потребность в j -м питательном веществе, а 
ic  ‒ стоимость единицы веса i-го продукта. Обозначим 
ix  – суточное потребление i-го продукта, которое нужно определить. 
Величина 
1
n
ij
j
i
a x

 есть общее содержание j -го питательного вещества в рационе, которое не должно быть меньше минимальной потребности 
jb : 
1
n
ij i
j
i
a x
b



,    
1,
,
j
m

. 
Таким образом, задача выбора рациона состоит в минимизации линейной функции при ограничениях на переменные в виде неравенств. 
Найти 
1
min
n
i i
i
c x

 
при условиях: 
1
n
ij i
j
i
a x
b



,     
1,
,
j
m

, 
0
ix 
,     
1,
,
i
n


. 
Приведенная задача является задачей линейного программирования. 
2. Транспортная задача. Общая постановка такой задачи состоит 
в определении оптимального плана перевозок некоторого однородного 
груза из m  пунктов отправления в n  пунктов назначения. При этом 
критерием оптимальности обычно являются минимальные затраты на 
перевозку всего груза. Обозначим ij
c  – затраты на перевозку единицы 
груза из i-го пункта отправления в j -й пункт назначения, 
ia  – запасы 
груза в i-м пункте отправления, 
jb  – потребности в грузе в j -м пункте 
назначения, а 
ij
x  – количество единиц груза, перевозимого из i -го 
пункта отправления в j -й пункт назначения. Тогда математическая 


постановка задачи будет состоять в определении минимального значения функции 
m
n
ij ij
i
j
c x



 
при условиях: 
1
m
ij
j
i
x
b



,     
1,
,
j
n


, 
1
n
ij
i
j
x
a



,     
1,
,
i
m


, 
0
ij
x 
,     
1,
,
i
m


,     
1,
,
j
n


. 
Приведенная задача, так же как и предыдущая, является задачей линейного программирования. 
3. Задача о ранце. Турист готовится к походу. В рюкзаке он может 
нести груз, масса которого не более G  кг. Этот груз может включать 
n видов предметов. Один предмет 
-го
j
 вида имеет массу 
j
g
 кг, 
1,
,
j
n


. Для каждого вида предмета турист определяет его ценность 
jc  во время похода. Обозначим 
jx – количество предметов j -го типа в 
рюкзаке. Задача состоит в таком наполнении рюкзака предметами указанных видов, чтобы общая ценность снаряжения была максимальной. 
Запишем математическую модель задачи: требуется найти 
1
max
n
j
j
j
c x

 
при условиях: 
1
n
j
j
j
g x
G



, 
0
jx 
,     
jx  – целое,     
1,
,
j
n

Данная задача является задачей целочисленного программирования. 


4. Задача распределения капиталовложений. Для увеличения объемов выпуска пользующейся повышенным спросом продукции предприятиям выделены капиталовложения в объеме S тыс. руб. Использование i-м предприятием 
ix  тыс. руб. из указанных средств обеспечивает 
прирост выпуска продукции, определяемый значением нелинейной 
функции 
(
)
i
i
f x . 
Задача состоит в определении способа распределения капиталовложений между предприятиями, обеспечивающего максимальное увеличение выпуска продукции. 
Математическая постановка задачи состоит в определении 
1
max
( )
n
i
i
j
f x

 
при условиях: 
1
n
i
i
x
S



, 
0
ix 
,     
1,
,
i
n

Сформулированная задача является задачей нелинейного программирования. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 


 
 
 
 
 
 
1. ËÈÍÅÉÍÎÅ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈÅ 
1.1. ÇÀÄÀ×È ËÈÍÅÉÍÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß 
Линейное программирование – это область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума линейной функции многих переменных при наличии линейных 
ограничений. 
В зависимости от вида ограничений и от того, какой экстремум линейной функции, минимум или максимум, надо найти, рассматривают 
различные формы задач линейного программирования (ЛП). Рассмотрим эти формы. 
Пусть 
1,
,
n
x
x

 – упорядоченный набор n вещественных чисел. 
Этому набору можно поставить в соответствие n-мерный вектор 
1
)
(
,
,
n
X
x
x


 вещественного линейного пространства 
n
R . 
Определение 1.1. Задачей ЛП в общей форме называется задача 
определения максимального (минимального) значения функции 
 
1
(
)
n
j
j
j
z X
c x


 
(1.1) 
при условиях: 
 
1
1
, 
1,
, ,
,  
1,
,
,
0, 
1,
,  (
).
n
ij
j
i
j
n
ij
j
i
j
j
a x
b
i
k
a x
b
i
k
m
x
j
l l
n






















  


Функция (
)
z X  называется целевой функцией, а условия (1.2) – ограничениями задачи ЛП. 
Определение 1.2. Задача ЛП представлена в симметричной форме, 
если она имеет следующий вид: 
 
1
(
)
max
n
j
j
j
z X
c x




 
(1.3) 
при условиях: 
 
1
, 
1,
,
,
0,
 
1,
, .
n
ij
j
i
j
j
a x
b
i
m
x
j
n













 
(1.4) 
В формуле (1.3) и далее символы «
max»

 у целевой функции означают, что рассматривается задача максимизации целевой функции. 
Определение 1.3. Канонической формой задачи ЛП называют следующее ее представление: 
 
1
(
)
max
n
j
j
j
z X
c x




 
(1.5) 
при условиях: 
 
1
, 
1,
,
,
0, 
1,
, .
n
ij
j
i
j
j
a x
b
i
m
x
j
n













 
(1.6) 
Приведенные три формы задач ЛП эквивалентны в том смысле, что 
от одной из указанных форм можно перейти к любой другой с помощью 
несложных преобразований. 
Задачу нахождения минимума функции 
1
(
)
n
j
j
j
z X
c x


 легко свести 
к задаче нахождения максимума, если рассмотреть функцию  
1
(
)
(
)
(
)
n
j
j
j
z X
z X
c
x








Ограничение-неравенство 
1 1
2 2
i
i
in n
i
a x
a x
a x
b





 можно преобразовать в ограничение-равенство путем добавления новой неотрицательной переменной 
1
n
x  к левой части этого неравенства:  
1 1
2 2
1
i
i
in n
n
i
a x
a x
a x
x
b







. 
Ограничение-неравенство 
1 1
2 2
i
i
in n
i
a x
a x
a x
b





 можно преобразовать в ограничение-равенство путем вычитания новой неотрицательной переменной 
1
n
x  из левой части этого неравенства:  
1 1
2 2
1
i
i
in n
n
i
a x
a x
a x
x
b







. 
Если надо перейти от ограничений-равенств к ограничениям-неравенствам, то каждое ограничение-равенство 
1 1
2 2
i
i
in n
i
a x
a x
a x
b





 
можно представить в виде пары неравенств: 
1 1
2 2
1 1
2 2
,
.
i
i
in n
i
i
i
in n
i
a x
a x
a x
b
a x
a x
a x
b













 
Если на переменную 
kx  не наложено условие неотрицательности, то 
вместо нее можно ввести две неотрицательные переменные 
k
u  и 
kv , полагая 
.
k
k
k
x
u
v


 
1.2. ÂÛÏÓÊËÛÅ ÌÍÎÆÅÑÒÂÀ Â n-ÌÅÐÍÎÌ ÏÐÎÑÒÐÀÍÑÒÂÅ 
Определение 1.4. Множество M  в n-мерном пространстве 
n
R  
называется выпуклым, если с любыми двумя точками ,a b
M

 множеству M  принадлежат также все точки отрезка, соединяющего a  и b , 
т. е. 
[0,1]

 
(1
)
a
b
М



. 
Легко можно проверить, что множества  


1
1
1 1
0
(
,
,
) |
n
n n
M
x
x
a x
a x
a






 
и  


2
1
1 1
0
(
,
,
) |
n
n n
M
x
x
b x
b x
b




 
являются выпуклыми. 


Доступ онлайн
500 ₽
В корзину