1.1. Задачи математического и линейного программирования

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

1) выбор переменных задачи;

2) составление системы ограничений;

3) выбор целевой функции.

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

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

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

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

(1.1.1)

при системе ограничений на переменные

(1.1.2)

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

Математическое программирование включает в себя такие разделы как линейное, нелинейное и динамическое программирование. Если целевая функция (1.1.1) и система ограничений (1.1.2) линейны, то задача математического программирования называется задачей линейного программирования (ЛП).

Математическое программирование возникло в 30-е годы XXвека. Линейное программирование началось с работы (1938 г.) ленинградского математика Л. В. Канторовича, в которой содержались постановка и метод решения задачи о выборе наилучшей производственной программы. Независимо линейное программирование начало развиваться и в США. В 1947 году американский учёный Дж. Данциг описал один из основных методов решения задач ЛП, получивший название «симплексный».

В общем случае задача ЛП может быть записана в виде:

, (1.1.3)

(1.1.4)

, , (1.1.5)

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