ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

Если среди базисных переменных нет равных нулю, то опорная точка x(0)

называется невырожденной, в противном случае – вырожденной опорной точкой. Соответственно, если среди опорных точек ЗЛП нет вырожденных, то она называется невырожденной, в противном случае – вырожденной зада-

чей линейного программирования.

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

Ут в е р ж д е н и е 3.1. Если ограничения имеют допустимое решение, то они имеют и базисное решение.

Геометрически это утверждение означает, что если допустимое множество X непусто, то у него существует хотя бы одна угловая точка.

Следующее утверждение называют основным свойством задач линейно-

го программирования или основной теоремой линейного программирования.

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

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

Симплекс-метод

Полный перебор базисных допустимых решений для реальных многомерных задач крайне не эффективен даже при условии использования мощной вычислительной техники, ибо при больших n и m он требует огромной вычислительной работы. Но он естественным образом подводит к основ-

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

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

Пусть задача (3.6), (3.7), (3.8) невырожденна и столбцы A1, A2, …, Am матрицы А образуют базис некоторой угловой точки x(0), а переменные x1, x2 , …, xm являются базисными переменными. Решая систему уравнений

(3.7) относительно переменных x1, x2 , …, xm и исключая базисные перемен-

ные из целевой функции, приходим к следующей ЗЛП, эквивалентной первоначальной задаче: минимизировать функцию

z1(x) = z(x(0) ) + em+1xm+1 + … + en xn

Моделирование процессов и объектов в металлургии. Лаб. практикум

-43-

x jr ,

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

при условиях

x	+ d	x	+ … + d x	= x(0)	,
1	1,m+1	m+1	1,n n	1
.	. . . . . . .	. . .	. . . . . . . . . . . .	. . . . .	(3.10)
xm + dm,m+1 xm+1			+ … + dm,n xn = xm(0) ,

xi ≥ 0, i = 1, 2, ..., n.

Правые части (3.10) дают координаты опорной точки (базисного решения) x(0) = (x1(0) , x2(0) , ..., xm(0) , 0, ..., 0). Так как x(0) – невырожденная опорная

точка, то xk(0) > 0, k = 1, 2, ..., m. Функция z1(x) называется приведенным (к неба-

зисным переменным) выражением для целевой функции z(x), а коэффициенты ek − оценками соответствующих свободных переменных xk , k = m + 1, …, n.

Дальнейшая стратегия определяется основной теоремой симплексметода.

Т е о р е м а. Если после выполнения очередной итерации в опорной

точке x(0):	все оценки окажутся неотрицательными, т.	е. ek ≥ 0	для всех
1)
k = m + 1, …, n, то x(0) – решение задачи (3.6), (3.7), (3.8);
2)	существует номер jr, m + 1 ≤ r ≤ n, такой,	что e j	< 0 и все
		r

dijr ≤ 0, i = 1, 2, …, m, то целевая функция z(x) неограниченно убывает на

допустимом множестве (3.7), (3.8), т.е. задача (3.6), (3.7), (3.8) не имеет решения;

3) найдется номер jr, m + 1 ≤ r ≤ n, такой, что e j		r	< 0 , но среди ко-
эффициентов di jr	есть положительные числа di j , …, di j , то можно пе-
	1 r	s r

рейти к другой опорной точке x(1), в которой f(x(1)) ≤ f(x(0)).

Третий случай означает, что решение ещё не достигнуто и необходимо выполнить следующую итерацию, которая включает в себя переход от х(0) к новой опорной точке х(1) и проверку последней на оптимальность. Для такого перехода мы вводим в список базисных переменных в точке х(0) новую базисную переменную m + 1 ≤ r ≤ n, выбирая ее из тех свободных пере-

менных, которые входят в приведенное выражение z1(x) с отрицательным ко-

эффициентом, и выводим из списка переменную x j ,

определяя номер jl с по-

di

j ,

l

при x j

мощью

положительных коэффициентов

…, di j

в системе

1 r

s r

r

(3.10).

А именно, выбираем номер jl из условия

x(0)

x(0)

x(0)

i

i

j

1

s

l

α =

min

, …,

=

.

(3.11)

di

j

di

j

d j

j

1

r

s

r

l

r

Моделирование процессов и объектов в металлургии. Лаб. практикум

-44-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

	По условию рассматриваемая задача невырожденная, поэтому усло-
вие	(3.11) определяет единственное число jl. Переменные		x1, …, xj					,
xj	, …, xm , xj	будут новыми базисными переменными. Элемент d j				l−1
				l	j	r	на-
l+1	r

зывают разрешающим элементом, а jl-e уравнение системы (3.10) − разрешающим уравнением.

Вообще говоря, индекс jr в третьей части теоремы определяется неоднозначно, приведённое выражение (3.9) для функции f(x) может содержать несколько отрицательных оценок ejk. На практике обычно выбирают наименьшую из них.

В условии (3.11) возможны два случая: α = 0 или α > 0. При α = 0 имеем х(0) = х(1), т.е. происходит лишь замена одного базиса точки х(0) другим. При α > 0 заведомо х(0) ≠ х(1) и f(х(1)) < f(х(0)). Если точка х(0) невырожденная, то обязательно α > 0.

Разработкамоделейлинейногопрограммирования

Термин «разработка» означает построение моделей ЛП практических задач. Она включает следующие основные этапы: 1) определение переменных задачи, представление ее ограничений в виде линейных уравнений или неравенств; 2) задание линейной целевой функции, подлежащей минимизации или максимизации. В качестве примера, иллюстрирующего основные этапы разработки модели ЛП, рассмотрим простейшую задачу производст-

венного планирования.

Пусть имеется некоторый экономический объект (предприятие, цех, артель и т.п.), который может производить некоторую продукцию п видов. В процессе производства допустимо использование т видов ресурсов (сырья, рабочего времени и пр.). Применяемые технологии характеризуются нормами затрат единиц сырья на единицу производимого продукта. Обозначим через ai,j количество i-го ресурса (i = 1, …, m), которое тратится на производство единицы j-го продукта (j = 1, …, n).

Если j-й продукт производится в количестве xj, то в рамках описанных выше технологий мы должны потратить a1,j xj первого ресурса, a2,j xj – второго, и так далее, am,j xj – m-го. Сводный план производства по всем продуктам может быть представлен в виде п-мерного вектора-строки х = (x1, x2, …, xj, …, xn). Тогда общие затраты i-го ресурса на производство всех продуктов можно выразить в виде суммы

n

∑ai, j x j . j=1

Очевидно, что всякая реальная производственная система имеет ограничения на ресурсы, которые она тратит в процессе производства. В рам-

Моделирование процессов и объектов в металлургии. Лаб. практикум

-45-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

ках излагаемой модели эти ограничения порождаются т-мерным вектором

b = (b1, b2, …, bm), где bi – максимальное количество i-го продукта, которое можно потратить в производственном процессе. В математической форме данные ограничения представляются в виде системы т неравенств:

a1,1 x1 + a1,2 x2 + … + a1,n xn ≤ b1,

a2,1 x1 + a2,2 x2 + … + a2,n xn ≤ b2,

……………………………………. (3.12) am,1 x1 + am,2 x2 + … + am,n xn ≤ bm.

Следует иметь в виду, что к ресурсам относятся также производственные мощности. В этом случае соответствующие ограничения в системе (3.12) могут иметь вид, например,

xi ≤ bi.

К системе (3.12) также должны быть добавлены естественные ограничения на неотрицательность компонентов плана производства:

х1 ≥ 0, …, хj ≥ 0, …, xn ≥ 0.

(3.13)

Обозначив через cj цену единицы j-го продукта, получим выражение суммарного дохода от выполнения плана производства, задаваемого вектором х:

z(x) = c1 x1 + c2 x2 + … + cn xn.

(3.14)

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

z(x) → max, x X,	(3.15)
где допустимое множество Х определяется ограничениями	(3.12), (3.13),
(3.14).

Моделирование процессов и объектов в металлургии. Лаб. практикум

-46-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

К модели (3.12), (3.13), (3.14) сводятся и другие задачи планирования. Например, если сj означает общие расходы на производство единицы j-го продукта, то суммарные затраты на выполнение всего плана х выражаются также функцией (3.14). Однако в этом случае наиболее естественной задачей для модели (3.12), (3.13), (3.14) будет задача поиска такого плана производства х, удовлетворяющего ограничениям (3.12), (3.13), при котором значение суммарных затрат, т.е. функции z(x), будет наименьшим:

z(x) → min, x X.

(3.16)

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

Анализоптимальногорешения

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

Послеоптимизационный анализ включает анализ внутренней структуры и параметрирование исходных данных модели.

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

Параметрирование исходных данных модели осуществляется путем постановки и решения задачи параметрического программирования.

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

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

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

Моделирование процессов и объектов в металлургии. Лаб. практикум

-47-

ЛАБ. Р. 3. ПРИМЕНЕНИЕ МЕТОДОВ ЛИНЕЙНОГО ПРОГР-Я ДЛЯ МОДЕЛИРОВАНИЯ И РЕШ-Я ПРОИЗВОДСТВЕННЫХ ЗАДАЧ

Краткие теоретические сведения

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

Нулевое значение дополнительной переменной в оптимальном плане означает неполное использование соответствующего ресурса.

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

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

1.Каждому ограничению прямой задачи соответствует переменная двойственной задачи.

2.Каждой переменной прямой задачи соответствует ограничение двойственной задачи.

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

4.Направление оптимизации меняется на обратное, а знак ограничения определяется по правилу: прямая задача на максимум – ограничения в двойственной задаче вида «≥» и наоборот.

5.Двойственные переменные не ограничены в знаке, поэтому при подготовке двойственной задачи необходима их замена на две неотрицательные переменные.

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

Моделирование процессов и объектов в металлургии. Лаб. практикум

-48-