Компьютерная реализация задачи линейного программирования средствами MS Excel 2007

Большое число экономических задач сводится к линейным математическим моделям. Традиционно оптимизационные линейные математические модели называются моделями линейного программирования. Этот термин появился в конце 30-х годов, когда программирование на компьютере еще не было развито, и соответствует не очень удачному переводу английского "programmation". Под линейным программированием понимается линейное планирование, т.е. получение оптимального плана—решения в задачах с линейной структурой.

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

Максимизировать (минимизировать) функцию:

, (1)

При ограничениях:

(2)

Где - управляющие переменные, образующие решение задачи;

– параметры задачи;

– целевая функция.

Решить задачу линейного программирования значит найти значения управляющих переменных, удовлетворяющих ограничениям (2), при которых целевая функция (1) принимает максимальное (минимальное) значение.

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

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

Второй случай обычно означает, что ЭММ разработана некорректно, и некоторые существенные ограничения в ней отсутствуют.