Математическое моделирование процессов резания


Постановка задачи линейного программирования


Рассмотренные нами методы решения задач оптимизации применимы к широкому классу задач, однако являются весьма сложными и требуют проведения значительных объемов вычислений. Между тем, существует ряд задач, являющихся частными случаями общей задачи оптимизации (4.2), для решения которых применимы методы, требующие для реализации более простых алгоритмов и значительно меньших вычислительных мощностей. К числу таких задач относится задача линейного программирования.

Задача линейного программирования сводится к поиску экстремума (максимума или минимума) линейной функции вида

              

Постановка задачи линейного программирования
.          (7.1)

Очевидно, искать экстремум этой функции, не налагая никаких ограничений на область изменения вектора

Постановка задачи линейного программирования
 бессмысленно, так как линейная функция не может иметь экстремума внутри допустимой области. Интерес представляет задача максимизации
Постановка задачи линейного программирования
 при условии, что
Постановка задачи линейного программирования
 принадлежит некоторому допустимому множеству
Постановка задачи линейного программирования

                    

Постановка задачи линейного программирования
,                (7.2)

где

Постановка задачи линейного программирования
 - множество допустимых значений
Постановка задачи линейного программирования
-й переменной,
Постановка задачи линейного программирования
 - множество индексов переменных
Постановка задачи линейного программирования
={1,2...
Постановка задачи линейного программирования
}.

Те из соответствующих задач, в которых область изменения вектора

Постановка задачи линейного программирования
 (допустимая область
Постановка задачи линейного программирования
) -
Постановка задачи линейного программирования
-мерный многогранник, составляют предмет линейного программирования.

Определение 7.1

Линейным программированием называется комплекс методов оптимизации линейных функций в допустимой области, определяемой системой линейных уравнений и неравенств.

В общем случае задача линейного программирования при оптимизации функции

Постановка задачи линейного программирования
 переменных в условиях
Постановка задачи линейного программирования
 ограничений формулируется следующим образом:

     

Постановка задачи линейного программирования
 или
Постановка задачи линейного программирования
. (7.3)

Представление задачи в форме (7.4) называется стандартной постановкой задачи линейного программирования

                

Постановка задачи линейного программирования
.             (7.4)

Переход от формы (7.3) к форме (7.4) осуществляется с помощью приема элиминации нетривиальных неравенств.



Содержание раздела