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

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

Задачи линейного программирования относятся к категории оптимизационных. Они находят широкое применение в различных областях практической деятельности: при организации работы транспортных систем, в управлении промышленными предприятиями, при составлении проектов сложных систем. Многие распространенные классы задач системного анализа, в частности, задачи оптимального планирования, распределения различных ресурсов, управления запасами, календарного планирования, межотраслевого баланса укладываются в рамки моделей линейного программирования. Несмотря на различные области приложения, данные задачи имеют единую постановку: найти значения переменных x₁, …, x_n, доставляющие оптимум заданной линейной формы z=c₁x₁ + c₂x₂+… + c_nx_n при выполнении системы ограничений, представляющих собой также линейные формы.

Родоначальником линейного программирования считают д-ра физ.-мат. наук, лауреата Государственной и Нобелевской премий Л.В. Канторовича, который в 30-е годы XX века предложил метод решения экономических задач (в частности, задачи раскроя фанеры). Л.В. Канторович разработал метод разрешающих множителей для решения задачи линейного программирования.

В последующем, в 50-е гг. XX в. независимо от Канторовича метод решения задачи линейного программирования (так называемый симплекс-метод) был развит американским математиком Дж. Данцигом, который в 1951 г. и ввел термин «линейное программирование».

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

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

Предположим, что в трех цехах (Ц₁, Ц₂, Ц_З) изготавливается два вида изделий И₁ и И₂. Известна загрузка каждого цеха а_i (оцениваемая в данном случае в процентах) при изготовлении каждого из изделий и прибыль (или цена, объем реализуемой продукции в рублях) с_i от реализации изделий. Требуется определить, сколько изделий каждого вида следует производить при возможно более полной загрузке цехов, чтобы получить за рассматриваемый плановый период максимальную прибыль или максимальный объем реализуемой продукции.

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

(1)

и ряд ограничений (в данном случае диктуемых возможностями цехов, т.е. их предельной 100%-ной загрузкой)

5 х₁ + 4х₂ ≤ 100;

1.6 х₁+ 17.4 х₂ ≤ 100; (2)

2.9 х₁ + 5.8 х₂ ≤ 100.

Изделие	Цех (участок)	Цена
	Ц1	Ц2	ЦЗ	Изделия
И1	5%	1.6%	2.9%	240 руб.
И2	4%	17.4%	5.8%	320 руб.
Максимальная загрузка	100%	100%	100%

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

Графическое решение задачи приведено на рисунке 8.1.

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

Существует два крайних положения линии уровня, когда она «касается» допустимого множества. Этим двум положениям в данном случае соответствуют две точки «касания» -начало координат (0, 0) и точка (9, 13). Первая из этих точек - точка минимума, а вторая - максимума данной функции F вида (1) на допустимом множестве (2).

Рис. 8.1. Графическое решение ЗЛП

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

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

Имеется множество переменных X = (x₁, х₂,..., х_n). Целевая функция линейно зависит от управляемых параметров:

(8.1)

Имеются ограничения, которые представляют собой линейные формы

где . (8.2)

Задача линейного программирования формулируется так:

Определить максимум линейной формы

F(x₁,…,x_n )=max(c₁x₁+…+c_nx_n) (8.3)

при условии, что точка (х₁, х₂,..., х_n) принадлежит некоторому множеству D, которое определяется системой линейных неравенств

(8.4)

Любое множество значений (х₁*, х₂*,..., х_n*), которое удовлетворяет системе неравенств (8.4) задачи линейного программирования, является допустимым решением данной задачи. Если при этом выполняется неравенство

c₁х₁^o+ c₂ х₂^o+..+ c_n х_n^o ≥ c₁х₁+ c₂ х₂+..+ c_n х_n

для всего множества значений x₁, х₂,..., х_n, то значение х₁^o..х_n^o является оптимальным решением задачи линейного программирования.

Задачу линейного программирования удобно представлять в векторной форме, тогда она будет выглядеть следующим образом: найти max F(x) = max (c ^Tx) при условии А Х ≤ Ро; Х≥0,

где с = (с₁,с₂,..., с_n) представляет собой n -мерный вектор, составленный из коэффициентов целевой функции, причем с ^T-транспонированная вектор-строка; х = (х₁, х₂,..., х_п) - п-мерный вектор переменных решений;

- m -мерный вектор свободных членов ограничений;

Матрица А размером (m×n) - матрица, составленная из коэффициентов всех линейных ограничений:

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

Каноническая задача линейного программирования заключается в минимизации (максимизации) линейной целевой функции

F(x) = c_lx₁+c₂x₂+... + c_nx_n при ограничениях

a₁₁х₁ +а₁₂х₂ +...+а_1пх_n=b₁

а₂₁х₁ +а₂₂х₂ +...+а_2пх_n=b_1…

…

а_m1х₁ +а_m2х₂ +...+а_mпх_n=b₁

x_t,x₂,...,x_n>0.

где с_[,с₂,...,с_п - коэффициенты целевой функции, a_tJ, i = \, 2,...,n,j = 1, 2,...,m -коэффициенты системы ограничений, а b₁,b_г,...,b_n - свободные члены, которые считаются неотрицательными.

Вектор X = (xi, х₂,..., xj, удовлетворяющий ограничениям задачи ЛП, называется допустимым решением или планом. Допустимый план X* =(xl,x'₂,...,x'_n), при котором целевая функция задачи ЛП принимает максимальное (минимальное) значение, на­зывается оптимальным планом.

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

В задаче линейного программирования общего вида вместо некоторых (всех) равенств в ограничениях записаны нестрогие неравенства в ту или другую сторону; при этом усло­вие неотрицательности переменных может отсутствовать для части или же для всех переменных. Известно, что решение любой задачи линейного программирования может быть сведено к решению канонической задачи, представляемой в форме (1) или (4).

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

Наиболее простым и распространенным методом решения канонической задачи линейного программирования до сих пор является симплекс-метод, предложенный в 40-е годы прошлого века Дж. Данцигом. Геометрически идею симплекс-метода в упрощенной форме можно выразить следующим образом. Допустимым множеством в задаче линейного программирования является некоторое многогранное множество и-мерного векторного пространства (в частном случае n = 2 - это выпуклый и не обязательно ограниченный многоугольник). Работа симплекс-метода начинается с некоторой начальной вершины (начального опорного плана) многогранного множества. Специальным образом выясняется, нет ли среди соседних вершин такой, в которой значение целевой функции лучше? Если такая вершина находится, то она и принимается за следующее приближение. После этого вновь исследуются соседние вершины для полученного приближения и т. д. до тех пор, пока не будет получена вершина, среди соседних вершин которой не существует вершины с лучшим значением целевой функции. Такая вершина является оптимальной. Она соответствует оптимальной точке (оптимальному решению) задачи линейного программирования.

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

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

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

Дата добавления: 2017-02-01