Учебно-методическое пособие для студентов специальности 1-36 20 02 «Упаковочное производство»

7. МЕТОД ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 
 
Линейное программирование — математическая дисциплина, 
посвященная теории и методам решения экстремальных задач на 
множествах n-мерного векторного пространства, задаваемых систе-
мами линейных уравнений и неравенств [5]. 
Линейное программирование является частным случаем выпук-
лого программирования, которое, в свою очередь, является частным 
случаем математического. Одновременно оно — основа нескольких 
методов решения задач целочисленного и нелинейного программи-
рования. Одним из обобщений линейного программирования явля-
ется дробно-линейное программирование. 
Многие свойства задач линейного программирования можно ин-
терпретировать также как свойства многогранников и таким обра-
зом геометрически формулировать и доказывать их. 
7.1. Математическая формулировка 
Нужно определить максимум линейной целевой функции (ли-
нейной формы) 
1 1
2 2
1
( )
...
n
j j
n n
j
f x
c x
c x
c x
c x




 

при условиях 
1
n
ij j
i
j
a x
b



при i = 1, 2, ..., m. 
Иногда на x
i
также накладывается некоторый набор ограничений 
в виде равенств, но от них можно избавиться, последовательно вы-
ражая одну переменную через другие и подставляя ее во всех 
остальных равенствах и неравенствах (а также в функции f). 
Такую задачу называют «основной» или «стандартной» в линей-
ном программировании. 

---

32 
7.2. Примеры задач о максимальном парасочетании