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

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

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

Целесообразно определить суть используемого в приведенных определениях термина “программирование”. Данный термин имеет в своем толковании двоякое значение. С одной стороны, им обозначают составление программ для компьютеров. С другой, - в применении к рассматриваемой дисциплине, этот термин означает, что в процессе решения соответствующих задач последовательно рассматривается ряд вариантов, иначе говоря, планов или программ действий. При таком толковании понятие программирования близко к термину планирование, т.е. здесь программирование понимается как нахождение оптимального пути для достижения поставленных целей.

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

Z = f (x) → max (min) x Î M,

где х = (х₁, …, х_n) – искомые переменные параметры; Z – целевая функция; М – область допустимых значений переменных х₁,.., х_n. Область М представляет некоторую систему математических зависимостей (уравнений, неравенств), описывающих количественные характеристики переменных х_j (j = 1, …, n) и связи между ними. Свободные члены каждого уравнения (неравенства) накладывают ограничения на выбираемые в процессе решения значения переменных. Исходя из этого, рассматриваемую систему зависимостей определяют как систему ограничений.

Дополнительным условием, включаемым в систему ограничений при решении прикладных задач (проектирования, планирования производства, экономических и т.п.), является условие неотрицательности значений искомых переменных, в соответствии с которым все х_j ≥ 0.

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

Математическое программирование включает такие разделы как линейное, нелинейное, целочисленное, стохастическое и другие программирования. Названные математические дисциплины отличаются друг от друга видом целевых функций Z и области М. Например, если f(x) и М – линейны, имеет место задача линейного программирования; в случае нелинейности Z или (и) М – задачи нелинейного программирования; при введении дополнительного условия целочисленности искомых переменных – задача целочисленного программирования. Стохастическое программирование представляет совокупность методов решения задач рассматриваемого класса вероятностного характера, где исходные и искомые параметры являются случайными величинами. Приведенную классификацию можно продолжить, так как, например, в нелинейном программировании выделяют методы выпуклого, квадратичного, параметрического и других видов программирования, в алгоритмах которых учитываются особенности целевых функций и налагаемых ограничений.

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

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

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

(i = 1, 2, …, m₁)

и (или)

(i =m+1, m+2, …, m₂) (2.1)

и (или)

(i =m₂+1, m₂+2, …, m)

Требуется найти такие неотрицательные значения переменных x_j (j=1, 2, …, n), т.е. x_j ≥ 0, которым будет соответствовать максимальное или минимальное, в зависимости от поставленной цели решения, значение линейной целевой функции:

(2.2)

Неотрицательность искомых значений переменных записывается: х_j≥0.

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

Применительно к приведенной в параграфе 1.6 задаче планирования производства, обозначения в рассматриваемой модели таковы: b_i – количество ресурса вида i, m – количество видов этих ресурсов; a_ij – норма расхода ресурса вида i на единицу продукции вида j; x_j – количество продукции вида j, причем таких видов – n; c_j – доход (или другой выигрыш) от реализации единицы этой продукции, а в случае задачи на минимум – затраты на еди6ницу продукции; нумерация ресурсов разделена на три части от 1 до m₁, от m₁ + 1 до m₂ и от m₂ + 1 до m в зависимости от того, какие ставятся ограничения на расходование этих ресурсов: в первом случае – не больше, во втором – столько же, в третьем – не меньше; Z – в случае максимизации, например, объем продукции или дохода, в случае минимизации – себестоимость, расход сырья и т.п.

В том случае, когда все ограничения в математической модели заданы в виде уравнений, форма записи задачи линейного программирования называется канонической, а задача – основной задачей линейного программирования.

При решении задач линейного программирования зачастую предварительно требуется привести систему ограничений к канонической форме записи. Это достигается преобразованием входящих в математическую модель неравенств в уравнения. С этой целью в каждое из неравенств включается по одной дополнительной переменной. Рассмотрим правила выполнения указанной операции в зависимости от вида ограничения.

1. (i = 1, 2, …, m₁)

В этом случае для преобразования неравенства в равенство в его левую часть добавляется неорицательная дополнительная переменная y_i:

(i = 1, 2, …, m₁)

2. (i = 1, 2, …, m₁)

Для перехода к уравнению в этом случае из левой части неравенства вычитается дополнительная переменная y_i:

(i = 1, 2, …, m₁)

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

В заключении заметим, что первооткрывателем линейного программирования является советский ученый, академик, лауреат Нобелевской премии Л.В. Канторович. В 1939 г. он решил математически несколько задач: о наилучшей загрузке машин, о раскрое материалов с наименьшими расходами, о распределении грузов по нескольким видам транспорта, разработав универсальный метод решения этих задач, а также несколько алгоритмов, реализующих его. Позднее, в 1940 – 50 годах, в этой области многое сделали американские ученые – Т. Купманс и Дж. Данциг. Последний, в частности, разработал симплексный метод – наиболее широко используемый универсальный метод решения задач линейного программирования. Ему же принадлежит и сам термин “линейное программирование”.