Многомерная минимизация при наличии ограничений.

7.1. Линейное программирование.

Задачами линейного программирования называются оптимизационные задачи, в которых ограничения представляются в виде равенств или неравенств, целевая функция линейна, все переменные х_j удовлетворяют условию не отрицательности х_j ³0. Линейное программирование представляет собой наиболее часто используемый метод оптимизации ( 74% от общего числа применяемых оптимизационных методов ).

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

Задача минимизации функции n переменных ¦(x)=(x₁,…, x_n) на некотором множестве Х Еⁿ не совпадающая со всем пространством Еⁿ и заданном с помощью ограничений (равенств и неравенств ) на координаты х_j (j=1:n) точки хÎEⁿ называется задачей математического программирования. При этом функцию ¦(х) называют целевой функцией, а множество Х- допустимым множеством.

Вначале дадим определение математического программирования. Математическое программирование-это область математики, разрабатывающая теорию и численные методы решения многомерных задач с ограничениями, т.е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Одной из таких задач является задача линейного программирования, состоящая в минимизации линейной целевой функции ¦(х)=¦(х₁,…, х_n)=c_j x_j на множестве ХÌEⁿ заданном системой линейных ограничений (равенств или неравенств ) на координаты x_j ( j=1:n).

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

Среди точек х=(х₁,…,х_n)ÎEⁿ, удовлетворяющихограничениям:

а_ij x_j =b_i,i=1:l; (7.1)

а_ijx_j£ b_i , i=(l+1):m; (7.2)

x_j³0 (7.3)

найти те, в которых функция

¦(х)=c_j x_j

принимает минимальное значение, и определить это значение. Это общая или произвольная форма записи.

Отметим, что в условии задачи линейного программирования могут содержаться неравенства и противоположного, чем в (7.2), знака, однако такие неравенства легко сводятся к виду (7.2) умножением на -1.

Если в условии задачи линейного программирования не содержаться ограничения- равенства (7.1), то эта форма записи называется симметричной или стандартной.

Если в условии задачи линейного программирования не содержаться ограничения-неравенства (7.20), то есть в (7.1) l=m, то она называется задачей линейного программирования в каноническом (основном) виде.

Ограничения – неравенства

преобразуются в ограничения-равенства путем прибавления (вычитания) к левым частям дополнительных (балансовых) переменных х_n+i ≥0, i=(l+1):m. Ограничения-неравенства (7.2) можно записать в виде равенств:

Таким образом, любая задача линейного программирования может быть записана в каноническом виде:

f(x)= (7.4)

а_ij x_j =b_{i ,} i=1:m, (7.5)

x_j ≥0. (7.6)

Если переменная х_n не подчинена условию неотрицательности, то ее следует заменить двумя неотрицательными переменными и , приняв х_n=-, ≥0, ≥0.

Часто используется векторная записьзадачи (7.3)…(7.5):

f(x)=(c,x)min,

Ax=b, (7.7)

х≥0,

где х=(х₁,…, х_n)^т– векторнезависимых переменных, с=(с₁,…, с_n)^т – вектор коэффициентов целевой функции из (7.3), А=( а_ij) - прямоугольная матрица размера m´n, b=(b₁,…,b_m)^т- вектор правых частей (ограничений) системы (7.4), а х³0-краткая запись условий неотрицательности (7.3).

Ограничения вида х_j ≥0 или х_j£0, или d_j£x_j£p_j (двусторонние ограничения) для всех или некоторых j (j=1,2,...,n) называют прямыми ограничениями на переменные. Методы решения задач линейного программирования построены, как правело, с учетом вида прямых ограничений.

Задача линейного программирования, которая имеет допустимые решения (т.е. система ограничений совместна) называется допустимой; задача с несовместной системой ограничений – недопустимой.

Совокупность чисел х=(х₁,…,х_n) удовлетворяющих ограничениям задачи (7.1)…(7.2) называется допустимым решением (или планом).

План х*=(х₁*,…,х_n*), при котором целевая функция задачи (7.3) принимает свое минимальное (максимальное) значение называется оптимальным.

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

Чтобы имело смысл говорить об отыскании оптимального плана задачи система (7.1)…(7.3) должна быть совместна и иметь не единственное неотрицательное решение. Это возможно в случае, если ранг r системы (число линейно независимых уравнений) меньше числа неизвестных n(r<n), при r=n – система допускает единственное решение, и вопрос о выборе оптимального решения отпадает. Случай r>n вообще невозможен.

Пример 7.1. Привести к канонической форме следующие задачи линейного программирования:

а) f(x)=6х₁+5х₂ min

Решение. Заменяем функцию f(x) на . Из левых частей ограничений типа ≥ вычитаем неотрицательные переменные х₃, х₄, _,х₅, к левым частям ограничений типа ≤ прибавляем неотрицательные переменные х₆, х_7. Получаем модель задачи в канонической форме:

б) f(x)=2х₁-3х₂ +5х₃-х₄ max

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

f(x)=2х₁-3() +5х₃ - max