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

Подождите немного. Документ загружается.

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

АЧ

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



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

-41-

11212111

bxaxaxa

…

22222121

bxaxaxa

…

………………………………….. (3.7)

2211 mnmnmm

bxaxaxa

…

≥ 0, x

≥ 0, …, x

≥ 0. (3.8)

Эти ограничения можно записать в матричной форме:

Ax =

b , x ≥ 0 ,

где A − матрица ранга m, m < n;

b − вектор правых частей; x − вектор пере-

менных;

⎟

⎠

⎞

⎜

⎝

⎛

mnmm

aaa

…

…………………

…

⎛⎞

⎜⎟

⎝⎠



⎟

⎠

⎞

⎜

⎝

⎛

x 

При приведении задачи к канонической форме используют следую-

щие правила.

1. Максимизация целевой функции z равносильна минимизации целе-

вой функции −z.

2. Ограничение в виде неравенства преобразуется в равенство добав-

лением новой неотрицательной переменной к левой части неравенства. Новая

переменная x

неотрицательна.

3. Если переменная

x может принимать значения любого знака, то

она заменяется разностью двух неотрицательных переменных:

kkk

xx=− ,

где '0,"0.

xx≥≥

Таким образом, приведение задачи к канонической форме может по-

требовать увеличения размерности задачи (количества переменных).

Допустимое множество Х общей ЗЛП образует так называемое много-

гранное множество. Каждое из равенств (3.4)

, (3.5) задает гиперплоскость в R

а каждое из неравенств определяет полупространство в

, ограниченное

соответствующей гиперплоскостью. Если множество X непусто, то оно вы-

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

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

АЧ

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



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

-42-

Другими словами, из того, что х ∈ X и у ∈ X, следует, что λ

х + (1 − λ)х ∈ X

для любого λ, 0 ≤ λ ≤ 1.

Ограниченное многогранное множество называют многогранником.

Точка х

выпуклого многогранного множества М называется его угловой

точкой (базисным допустимым решением), если она не лежит ни на каком

отрезке, соединяющем какие-либо две точки множества М, отличные от нее.

Угловые точки многогранника называются его вершинами.

В рассмотренном примере допустимое множество задачи линейного

программирования представлялось в виде некоторого многогранного выпук-

лого множеств

а на плоскости. Такое представление в литературе получило

название

первой геометрической интерпретации задачи линейного про-

граммирования.

Обозначая через

, …,

столбцы матрицы А, т.е.

,1,2,,,

⎛⎞

⎜⎟

⎝⎠

…



систему (3.7)

можно записать в виде

+ … +

= b . (3.9)

В дальнейшем без ограничения общности можно полагать, что число

уравнений задающих множество Х меньше или равно числу переменных задачи

(m ≤ n). Действительно, если это не так, то либо система уравнений Ах =

b не-

совместна (и, значит, множество Х пусто), либо содержит избыточные (ли-

нейно зависимые) уравнения. Соотношение (3.9)

является разложением век-

тора

b по векторам

, i = 1, 2, …, n, а x

– коэффициентами этого разложе-

ния. Такое разложение получило название

второй геометрической интер-

претации

ЗЛП.

Точка x

(0)

= (x

(0)

, …, x

(0)

) называется опорной точкой допустимого

множества Х (базисным решением), если существуют номера j

, …, j

, 1 ≤ j

≤ n, такие, что система векторов

, …,

линейно независима и

(0) (0) (0)

jj j

xAx Axb

++ =…

(0)

≥ 0, k = 1, 2, …, m, x

(0)

= 0, если s ≠ j

Система векторов {

, …,

} называется базисом опорной точки (х

(0)

а переменные x

, …, x

– базисными переменными. Переменные, которые не

входят в список базисных переменных, называются небазисными или свобод-

ными.

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

АЧ

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



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

-43-

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

(0)

называется невырожденной, в противном случае – вырожденной опорной

точкой. Соответственно, если среди опорных точек ЗЛП нет вырожденных,

то она называется невырожденной, в противном случае – вырожденной зада-

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

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

следующие свойства этих задач.

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

шение, то они имеют и базисное решение.

Геометрически это утверждение означает, что если допустимое мно-

жество X непусто, то у него существует хотя бы одна угловая точка.

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

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

У т в е р ж д е н и е 3.2. Если целевая функция достигает конечного

минимума, то, по крайней мере, одно оптимальное решение является базис-

ным. Другими словами, множество решений задачи линейного программиро-

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

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

что при поиске оптимального решения можно ограничиться перебором ба-

зисных допустимых решений.

Полный перебор базисных допустимых решений для реальных мно-

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

мощной вычислительной техники, ибо при больших n и m он требует огром-

ной вычислительной работы. Но он естественным образом подводит к основ-

ной идее симплекс-метода: полный перебор заменяется упорядоченным, при

котором осуществляется п

ереход от текущей опорной точки (базисного

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

целевой функции меньше, чем в текущей. Несмотря на то, что при таком пе-

реборе возврат к однажды просмотренным опорным точкам уже невозможен,

теоретически не исключается (и такие примеры существуют), что в процессе

решения будут пройдены все опорные точки допустимого множества Х. Од-

нако большой практический опыт пок

азал, что для подавляющего числа ка-

нонических ЗЛП количество итераций находится в пределах от m до 2m.

Пусть задача (3.6), (3.7), (3.8) невырожденна и столбцы A

, A

, …, A

матрицы А образуют базис некоторой угловой точки x

(0)

, а переменные

,, ,

xx…

являются базисными переменными. Решая систему уравнений

(3.7)

относительно переменных

,, ,

xx… и исключая базисные перемен-

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

начальной задаче: минимизировать функцию

(0)

111

() ( )+

mm nn

zx zx e x ex

=++…

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

АЧ

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



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

-44-

при условиях

(0)

11,11 1, 1

mm nn

dx dxx

+++=…

. . . . . . . . . . . . . . . . . . . . . . . . . . . . (3.10)

(0)

,11, mnnmmmmm

xxdxdx =+++

…

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

Правые части (3.10)

дают координаты опорной точки (базисного ре-

шения)

(0) (0) (0) (0)

( , , ..., , 0, ..., 0).

xxx x= Так как x

(0)

– невырожденная опорная

точка, то ,0

(0)

x k = 1, 2, ..., m. Функция z

(x) называется приведенным (к неба-

зисным переменным) выражением для целевой функции z(x), а коэффициенты

e − оценками соответствующих свободных переменных

, k = m + 1, …, n.

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

метода.

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

точке x

(0)

1) все оценки окажутся неотрицательными, т. е. 0≥

e для всех

k = m + 1, …, n, то x

(0)

– решение задачи (3.6), (3.7), (3.8);

2) существует номер j

, m + 1 ≤ r ≤ n, такой, что 0

e и все

,0≤

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

допустимом множестве (3.7)

, (3.8), т.е. задача (3.6), (3.7), (3.8) не имеет

решения;

3) найдется номер j

, m + 1 ≤ r ≤ n, такой, что 0<

e , но среди ко-

эффициентов

есть положительные числа

,, ,

rsr

ij ij

dd… то можно пе-

рейти к другой опорной точке x

(1)

, в которой f(x

(1)

) ≤ f(x

(0)

Третий случай означает, что решение ещё не достигнуто и необходи-

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

(0)

к новой опорной точке х

(1)

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

кого перехода мы вводим в список базисных переменных в точке х

(0)

новую

базисную переменную

, m + 1 ≤ r ≤ n, выбирая ее из тех свободных пере-

менных, которые входят в приведенное выражение z

(x) с отрицательным ко-

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

, определяя номер j

с по-

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

rsr

ij ij

dd… при

x в системе

(3.10)

. А именно, выбираем номер j

из условия

(0) (0)

(0)

min , , .

rsrlr

ij ij jj

ddd

⎧⎫

⎪⎪

α= =

⎨⎬

⎪⎪

⎩⎭

… (3.11)

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

АЧ

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



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

-45-

По условию рассматриваемая задача невырожденная, поэтому усло-

вие (3.11)

определяет единственное число j

. Переменные

, , ,

−

…

, , ,

jmj

… будут новыми базисными переменными. Элемент

d на-

зывают

разрешающим элементом, а j

-e уравнение системы (3.10) − разре-

шающим уравнением.

Вообще говоря, индекс j

в третьей части теоремы определяется неод-

нозначно, приведённое выражение (3.9)

для функции f(x) может содержать

несколько отрицательных оценок

. На практике обычно выбирают наи-

меньшую из них.

В условии (3.11)

возможны два случая: α = 0 или α > 0. При α = 0

имеем

(0)

= х

(1)

, т.е. происходит лишь замена одного базиса точки х

(0)

другим.

При

α > 0 заведомо х

(0)

≠ х

(1)

и f(х

(1)

) < f(х

(0)

). Если точка х

(0)

невырожденная,

то обязательно

α > 0.

Термин «разработка» означает построение моделей ЛП практических

задач. Она включает следующие основные этапы: 1) определение перемен-

ных задачи, представление ее ограничений в виде линейных уравнений или

неравенств; 2) задание линейной целевой функции, подлежащей минимиза-

ции или максимизации. В качестве примера, иллюстрирующего основные

этапы разработки модели ЛП, рассмотрим

простейшую задачу производст-

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

Пусть имеется некоторый экономический объект (предприятие, цех,

артель и т.п.), который может производить некоторую продукцию

п видов.

В процессе производства допустимо использование

т видов ресурсов (сырья,

рабочего времени и пр.). Применяемые технологии характеризуются норма-

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

i,j

количество i-го ресурса (i = 1, …, m), которое тратится на производство

единицы

j-го продукта (j = 1, …, n).

Если

j-й продукт производится в количестве x

, то в рамках описанных

выше технологий мы должны потратить

1,j

первого ресурса, a

2,j

– второ-

го, и так далее,

m,j

– m-го. Сводный план производства по всем продуктам

может быть представлен в виде

п-мерного вектора-строки х = (x

, x

, …, x

, …,

). Тогда общие затраты i-го ресурса на производство всех продуктов можно

выразить в виде суммы

∑

jji

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

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

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

АЧ

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



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

-46-

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

b = (b

, b

, …, b

), где b

– максимальное количество i-го продукта, которое

можно потратить в производственном процессе. В математической форме

данные ограничения представляются в виде системы

т неравенств:

1,1

+ a

1,2

+ … + a

1,n

≤ b

2,1

+ a

2,2

+ … + a

2,n

≤ b

……………………………………. (3.12)

m,1

+ a

m,2

+ … + a

m,n

≤ b

Следует иметь в виду, что к ресурсам относятся также производствен-

ные мощности. В этом случае соответствующие ограничения в системе (3.12)

могут иметь вид, например,

≤ b

К системе (3.12)

также должны быть добавлены естественные ограни-

чения на неотрицательность компонентов плана производства:

≥ 0, …, х

≥ 0, …, x

≥ 0. (3.13)

Обозначив через

цену единицы j-го продукта, получим выражение

суммарного дохода от выполнения плана производства, задаваемого векто-

ром

х:

z(x) = c

+ c

+ … + c

. (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)

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

АЧ

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



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

-47-

К модели (3.12), (3.13), (3.14) сводятся и другие задачи планирования.

Например, если

означает общие расходы на производство единицы 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) мо-

гут быть сведены очень многие проблемы различного характера.

Любые изменения коэффициентов в исходной модели могут привести

к изменению статически найденного оптимального решения задачи. Анализ

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

ного решения в результате изменений в исходной модели: коэффициентов

целевой функции, матрицы коэффициентов, правых частей уравнений – ог-

раничений. Причиной

недопустимости решения может стать изменение ре-

сурсов (правых частей ограничений) или добавление новых ограничений. К

неоптимальности решения приводит изменение коэффициентов целевой

функции или некоторых коэффициентов левых частей ограничений.

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

ры и параметрирование исходных данных модели.

Для

анализа внутренней структуры используются данные из сим-

плекс-таблицы, соответствующей оптимальному решению, а также двойст-

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

Параметрирование исходных данных модели осуществляется путем

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

При анализе внутренней структуры выявляется дефицитность ресур-

сов, составляющих ограничения задачи, ценность ресурсов, устойчивость оп-

тимального решения к изменению запасов ресурсов, к вариациям коэффици-

ентов целевой функции, интенсивности потребления ресурсов.

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

гарантированного оптимального плана при наихудшем стечении обстоя-

тельств, вызванных неуправляемыми внешними воздейств

иями.

Оценка дефицитности ресурсов осуществляется непосредственно из

оптимального плана по числовым значениям дополнительных переменных,

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

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

АЧ

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



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

-48-

ляет значение целевой функции при оптимальном плане, если дополнитель-

ная переменная, имеющая единичный коэффициент в строке данного ресурса

матрицы ограничений, является свободной переменной (имеет нулевое значе-

ние).

Нулевое значение дополнительной переменной в оптимальном плане

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

Ценность ресурса определяется его двойственной оценкой. Под цен-

ностью ресурса понимается величина, показывающая улучшение оптималь-

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

Двойственные оценки ресурсов – это коэффициенты при дополнительных

переменных в строке целевой функции сиплекс-таблицы оптимального ре-

шения. Для получения двойственных оценок используются решения двойст-

венной задачи, в которой значени

я основных переменных являются двойст-

венными оценками прямой задачи.

Двойственная задача ЛП симметрична прямой (исходной) задаче:

целевая функция имеет то же самое оптимальное значение, матрица коэффи-

циентов левых частей ограничений является транспонированной, а вектор

ограничений и вектор коэффициентов целевой функции меняются местами.

Двойственную задачу получаем путем симметричного структурного преобра-

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

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

ет переменная

двойственной задачи.

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

двойственной задачи.

3. Коэффициенты при некоторой переменной в матрице ограничений

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

щего ограничения двойственной задачи, а коэффициент при той же перемен-

ной в выражении для целевой функции прямой задачи становится правой ча-

стью (ограничением) строки в матри

це ограничений двойственной задачи.

Таким образом, число ограничений двойственной задачи равно числу перемен-

ных прямой задачи, а число переменных – числу ограничений прямой задачи.

4. Направление оптимизации меняется на обратное, а знак ограниче-

ния определяется по правилу: прямая задача на максимум – ограничения в

двойственной задаче вида «≥» и наоборот.

5. Двойственные переменные не ограничены в знаке, поэтому пр

подготовке двойственной задачи необходима их замена на две неотрицатель-

ные переменные.

Из постановки двойственной задачи следует, что в оптимальном до-

пустимом решении двойственные переменные являются коэффициентами

при величинах ресурсов прямой задачи, входящих в двойственную целевую

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

целевой функции от единичного изменения каждого вида ресурса (ценность

ресурса).

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

АЧ



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

-49-

1. Изучить основные положения теории линейного программирова-

ния.

В соответствии с вариантами заданий построить модель, привести

ее к канонической форме, составить двойственную задачу ЛП (в канониче-

ской форме).

Изучить порядок эксплуатации программных средств решения за-

дачи ЛП с помощью ЭВМ.

Получить разрешение преподавателя на выполнение работы, отве-

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

Ввести данные в ЭВМ и получить решение задачи.

По заданию преподавателя получить с помощью ЭВМ двойствен-

ные оценки задачи.

Оформить отчет, в который включить: краткую формулировку цели

и содержания работы; математическую модель планирования, прямую и

двойственную задачи ЛП в канонической форме; алгоритм симплекс-метода;

исходные данные; результаты расчета на ЭВМ; анализ результатов и техни-

ко-экономическую оценку оптимального плана.

Задание 1

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

Проверить результаты с помощью пакета прикладных программ. Исходные

данные принять по табл. 3.1

Таблица 3.1

Номер варианта Экстремум W = f(x

) Ограничения

1 Max

1243

≤+

2 Max

35,02

834

≤+

3 Max

1023

≤≤

≥+

4 Max

2023

2345

≤−

≤+

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

АЧ

Задания



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

-50-

Продолжение табл. 3.1

Номер варианта Экстремум W = f(x

) Ограничения

5 Max

≤−

≤+−

≤+

6 Max

43 xx

233

≤−

≤+−

≤+

7 Max

2xx

≤−

≤+

8 Min

−

323

232

5,0

≤+

≤−

≥+

≤+

9 Min

2 xx

−

123

124

125

xxx

−

++=

−

+−=

++=

10 Min

−

521

421

321

=++

=+−

xxx

11 Max

221

322

≤−≤

≤+≤

12 Min

321

xxx

−

321

≤+−

≤++

xxx

13 Min

−

552

≤+

14 Min

0,5 0, 2

−

136010

4530

421

321

=−+

=+−

xxx

15 Min

4321

53 xxxx

−

9287

544

4321

=+++

+++

xxxx

16 Max

4321

2 xxxx

−

232

132

4321

=+−−

+−+

xxxx

17 Max

4xx

≤+−

≥+

≤+

≥−