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

Лекция: Дискретное программирование

Предмет дискретного программирования. Постановка задачи линейного программирования. Геометрическая интерпретация задачи линейного программирования. Общий путь нахождения оптимального плана. Вычислительные методы линейного программирования. Пример математической модели дискретного программирования (транспортная задача). Метод северо-западного угла.

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

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

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

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

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

Линейное программирование является составной частью более общего метода — математического программирования. Математическое программирование позволяет находить наилучшие планы распределения ограниченных ресурсов для достижения требуемой цели – решения задачи. Линейное программирование может быть использовано как один из методов оптимизации решения. Наилучший результат здесь достигается не за счет выделения дополнительных сил и средств или иных ресурсов, а за счет их рационального распределения.

Решение, наилучшим образом соответствующее целевой установке и удовлетворяющее условиям задачи, называется оптимальным планом.

Линейное программирование от других видов математического программирования отличается тем, что математическая модель, соответствующая целевой установке задачи, может быть записана с помощью линейных соотношений вида:

(6.1)

где — - — известные коэффициенты;

- - — неизвестные переменные .

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

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

(6.2)

где

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

Целевая функция задается в виде такой линейной формы:

(6.3)

где — постоянные коэффициенты, которые обычно называют коэффициентами стоимости .

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