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

4. МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

Математическим программированием принято называть совокупность методов поиска значений аргументов x1 ,x2 ,…,xn , обеспечивающих достижение экстремума некоторого показателя качества W(A,x1 ,x2 ,…,xn ), где A – вектор параметров задачи. Название сложилось исторически и не вполне соответствует современному понятию «программирование». Тем не менее, его принято использовать как в общем смысле, так и для ряда частных методов: линейное программирование, нелинейное программирование, динамическое программирование и др.

Следует отметить, что рассмотренные в разд. 2 и 3 методы также могут быть отнесены к числу методов математического программирования.

4.1.Линейное программирование: постановка задачи, основные понятия, графическая интерпретация

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

n
q(x1, x2 ,...xn )= c0 + ∑ci xi → extr	(37)

i=1

и удовлетворяющие системе ограничений:

n
∑a ji xi ≤ bj ; j=1,2,…m; xi ≥ 0	; i=1,2,…n. (38)

i=1

Отметим некоторые особенности такой задачи:

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

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

59

–искомый абсолютный экстремум следует искать на границах допустимой области, определяемой ограничениями (38);

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

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

n

Любое неравенство вида ∑a ji xi ≤ bj может быть сведено к ра-

i=1

n

венству за счет введения новой переменной ∑a ji xi − xn+ j = bj ,

i=1

причем для сохранения знака неравенства такая переменная должна отвечать требованию, соответствующему (38), xn+ j ≥ 0 .

Следовательно, задача линейного программирования с k ограничениями в форме равенств и l ограничениями в форме неравенств может быть сведена к задаче c k+l ограничениями только в форме равенств. При этом количество аргументов задачи увеличивается до n+l.

Возможность применения такого приема позволяет рассматривать более удобную для решения общую постановку задачи линейного программирования, называемую основной задачей линейного программирования (ОЗЛП): требуется определить значения переменных состояния системы (аргументов) x1 ,x2 ,…,xn , доставляющие экстремум критерию оптимальности (целевой функции)

		n
вида	q(x1, x2 ,...xn )= c0 + ∑ci xi → extr		и удовлетворяющие сис-
теме ограничений:		i=1
	n
	∑a ji xi	= bj ; j=1,2,…m; xi ≥ 0 ; i=1,2,…n.		(39)

i=1

Корректна только задача, в которой m<n. Тогда будет иметь место бесчисленное множество решений системы уравнений (39), и среди них возможен поиск такого решения, которое доставит экстремум целевой функции. Одно из возможных решений может быть получено, если для n-m переменных задать некоторые значения, например, нулевые. В результате будет получена система m

60

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

Базисом называется любой набор из m переменных, таких что определитель, составленный из коэффициентов при этих переменных, не равен нулю. Входящие в базис переменные называют базисными, остальные n–m переменные – свободными. Решение, получаемое при нулевых значениях свободных переменных называется базисным решением. Если все элементы базисного решения (значения базисных переменных) неотрицательны, такое базисное решение в соответствии с (39) является допустимым. Если хотя бы один элемент базисного решения оказывается отрицательным, то все базисное решение является недопустимым.

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

Пример 27. Определить значения переменных состояния сис-

темы x1		, x2 ,…,x5 , доставляющие максимум целевой функции
q=x1 –x2		с учетом ограничений:
–	2x1 +x2 +x3 =2,x1 –2x2 +x4 =2, x1 +x2 +x5 =5;		(40)

xi ≥ 0 ; i=1,2,…5.

Размерность задачи n=5, количество базисных переменных m=3, количество свободных переменных n–m=2.

Выберем в качестве базисных переменных x3 ,x4 ,x5 . Свободные переменные x1 ,x2 используем в качестве координат на плоскости (рис. 20).

Рис. 20

61

Решим уравнения (40) относительно базисных переменных:

x3 =2+2x1 –x2 , x4 =2–x1 +2x2 , x5 =5–x1 –x2 . (41)

Полученные выражения вместе с условием неотрицательности всех переменных определяют границы допустимой области на плоскости x1 0x2 :

x1 ≥ 0 , x2 ≥ 0 ,

2+2x1 –x2 ≥ 0 , 2–x1 +2x2 ≥ 0 , 5–x1 –x2 ≥ 0 .

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

–каждой точке на плоскости x1 0x2 соответствует конкретное сочетание значений всех переменных задачи x1 ,x2 ,…,x5 ;

–на прямой, являющейся границей допустимой области, переменная с соответствующим порядковым номером равна нулю;

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

Количество базисных решений определяется размерностью задачи n и количеством базисных переменных m (число сочетаний

	из n элементов по m): Сnm =	n!		и в рассматриваемой задаче
		m!(n −m)!

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

Критерий оптимальности геометрически интерпретируется как прямая, описываемая уравнением x1 –x2 =q. При плоскопараллельном смещении ее вниз q увеличивается, вверх – уменьшению. Таким образом, максимум (минимум) критерия q достигается, когда эта прямая проходит через одну из вершин многоугольника, ограничивающего допустимую область, т. е. решение задачи ли-

нейного программирования лежит среди допустимых базисных решений.

На рис. 20 показано положение прямой, дающее решение задачи. Оптимальные значения x1 =4 и x2 =1 теперь могут быть полу-

62