Общие понятия

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

Математическим программированием называется раздел математики, в котором изучаются методы нахождения максимума или минимума целевой функции конечного числа переменных , при условии, что переменные удовлетворяют конечному числу дополнительных условий (ограничений), имеющих вид уравнений и/или неравенств. Накладывается также условие неотрицательности переменных .

Если целевая функция и ограничения линейны, то имеем задачу линейного программирования (ЗЛП). Если или целевая функция и/или ограничения являются нелинейными, то это задача нелинейного программирования (ЗНП).

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

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

Системой ограничений задачи называется совокупность уравнений и/или неравенств, которым удовлетворяют переменные задачи и которые следуют из ограниченности ресурсов или других экономических условий, например условия положительности переменных. В общем случае они имеют вид:

.

В случае ЗЛП ограничения имеют вид

Целевой функцией называют функцию от переменных задачи, которая характеризует качество осуществления задачи и экстремум которой (максимум или минимум) требуется найти. Для задачи линейного программирования целевая функция имеет вид:

Допустимым решением (планом) ЗЛП называется любой n-мерный вектор , удовлетворяющий системе ограничений и условиям неотрицательности . Множество допустимых решений образуют область допустимых планов или решений. Область допустимых планов, если она не является пустым множеством, ограничена выпуклым многогранником (при n=2- выпуклым многоугольником), вершины которого называются опорными планами.

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