Задача линейного программированияЛинейное программирование – математическая дисциплина, посвящённая теории и методам решения экстремальных задач на множествах Линейное программирование является частным случаем выпуклого программирования, которое в свою очередь является частным случаем математического программирования. Одновременно оно — основа нескольких методов решения задач целочисленного и нелинейного программирования. Одним из обобщений линейного программирования является дробно-линейное программирование. Многие свойства задач линейного программирования можно интерпретировать также как свойства многогранников и таким образом геометрически формулировать и доказывать их. Основной (стандартной) задачей линейного программирования называется задача нахождения минимума линейной целевой функции (линейной формы) вида:
при условиях
Задача линейного программирования будет иметь канонический вид, если в основной задаче вместо первой системы неравенств имеет место система уравнений:
Основную задачу можно свести к канонической путём введения дополнительных переменных. Задачи линейного программирования наиболее общего вида (задачи со смешанными ограничениями: равенствами и неравенствами, наличием переменных, свободных от ограничений) могут быть приведены к эквивалентным (имеющим то же множество решений) заменами переменных и заменой равенств на пару неравенств. Легко заметить, что задачу нахождения максимума можно заменить задачей нахождения минимума, взяв коэффициенты
|
-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
,
.
,
с обратным знаком.
