Глава 3 построение моделей систем 53

3.1.Понятие модели системы 53

3.2.Способы описания систем Модель черного ящика 54

3.3.Анализ и синтез - методы исследования систем 60

Глава 4 ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ - МЕТОД ПРОВЕДЕНИЯ СИСТЕМНЫХ ИССЛЕДОВАНИЙ 67

Глава 5 75

ТЕОРИЯ ПОДОБИЯ - МЕТОДОЛОГИЯ ОБОСНОВАНИЯ ПРИМЕНЕНИЯ МОДЕЛЕЙ 75

[р,:і=ша'[лр'[м]\ 80

[c]=[Mf[Lfm\ 80

7С, = : : 81

7С, = 81

р. 85

шр = J Ч(к^к 85

°р = J K2Zp(K)^K-Wp2, 85

ZprCO= JJ /, (*,)/2 (f2Vfc1A1 = 86

Глава 6 92

ЭКСПЕРИМЕНТ - СРЕДСТВО ПОСТРОЕНИЯ МОДЕЛИ 92

Глава 7 110

ПАРАМЕТРИЧЕСКИЕ МЕТОДЫ ОБРАБОТКИ ЭКСПЕРИМЕНТАЛЬНОЙ ИНФОРМАЦИИ 110

1Lt, 128

Ь, = (в, Ґ 138

мм>.го>=П[ j*-JШГ 152

^,B)= ртам, 170

J p*~m+I(l-p)mdp 175

J pk-m(l-p)mdp 175

т{т'у>’шга«~кг‘щцтг- 210

241

AJ 241

=0=8= - A 283

8^==8 •■• ^8 - *8= •■ 287

если г, Z = 1, 2,..., т.

Выясним условия, при которых новое базисное решение будет до­пустимым, т.е. а^<к₀^+>) > 0 для всех /. По предположению, а_ю > 0, тогда

а^(к)

(t+i) ₌£ш_>о ¹⁰

^{1 0} К ¹K

,^{0 1}K ~Уъ

Теперь можно записать базисное решение

х, = I; х₂ = I; х_} = 0; X₄ = 0, а также соответствующее общее решение

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

Преобразование Гаусса называется симплексным преобразовани­ем, когда направляющий элемент определяют по следующим правилам:

• направляющий столбец выбирают из условия, что в нем имеется хотя бы один положительный элемент;

• направляющую строку выбирают так, чтобы отношение — было

минимальным при условии, что а.> 0. ⁴

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

Пусть имеются линейная форма

Ki*i + ^_m2X₂ +... + O_imX_n +Ojt_ntl +...+1х_п+т=а_т0. Ha следующем шаге составим таблицу (табл. 10.1).

Таблица 10.1

Нижняя строка элементов <*_ок,к = 0, т+п называется индексной. Элементы индексной строки вычисляются следующим образом:

т

^аои ⁼ S^ait^cn+i ~^ск> * = 1» и означает номер соответствующей строки.

і=і

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

Элемент Oi₀₀ равен значению целевой функции, которое вычисляет-

т

ся по формуле а_м = Jc_n+ia_i0 , к - номер базисной переменной (индек­сация идет по строкам таблицы).

В столбце B_x записываются базисные переменные, на первом шаге

в качестве базисных выбирают фиктивные переменные {Jt_ntt },jt = 1, т. В дальнейшем фиктивные переменные необходимо вывести из базиса.

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

Для перехода от базиса фиктивных переменных к базису реальных переменных применяют следующие правила:

• в качестве направляющего столбца выбирают столбец A_j, для ко­торого выполняется условие а_0у = min{a₀₍}, 1 = 1, п+т при а_ое <0, т.е. выбирается минимальный элемент, при условии, что этот элемент от­рицательный;

• выбирают направляющую строку, для чего каждый элемент стол­бца свободных членов делится на соответствующий элемент направ­ляющего столбца, элемент столбца свободных членов находится в од­ной строке с элементом направляющего столбца —. Из всех возмож­но

ных соотношений выбирается минимальное — = mini — I при условии,

^аи KJ

что а_г> 0, 1 < г < т.

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

Переменная, которая соответствует направляющему столбцу, вво­дится в базис, а переменная, соответствующая направляющей строке, выводится из базиса. При этом для переменной, вводимой в базис, из-

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

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

1. Для всех элементов направляющей строки

(*)

„(*+1)_^uU

и ^— Ikl '

4 Jt₁ +Зх₂ +Ox₃ +Ox₄ +Ox₅ —»шах;

Ix₁ +Ox₂ +Ix₃ +Ox₄ +Ox₅ =4000;

Ox₁ +Ix₂ +Ox₃ +Ix₄ +Ox₅ = 6000;

2

Ix₁ + ” X₂ +Ox₃ +Ox₄ +Ix₅ = 6000. Составим исходную симплекс-таблицу (табл. 10.2).

Таблица 10.2

где к - номер шага (к = 1, 2,...); і - номер направляющей строки; j -

номер направляющего столбца; £ = 0, т+п, т.е. все элементы направ­ляющей строки делим на направляющий элемент, в итоге направляю­щий элемент стал равным единице; а<*⁺¹⁾ = 1.

2. В направляющем столбце необходимо получить а‘*⁺¹⁾ = 0, для всех

г = I, т, гїі, при а J^t+1) = 1, т.е. в направляющем столбце должны быть все нули кроме направляющего элемента, который равен единице.

Для всех остальных элементов, включая индексную строку, произ­водим вычисления

a^(t)a^{(t) a}H

Симплексные преобразования повторяют до тех пор, пока не реа­лизуется один из двух возможных исходов:

а) все а₀₁ > 0- это условие оптимальности базиса последней таб­лицы;

б) найдется такой элемент a_Q. < 0, при котором все элементы стол­бца а^< 0, - это признак неограниченности целевой функции на множе­стве допустимых решений.

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

найти максимум линейной формы Ax_x + Зх₂ при ограничениях

х_х < 4000, X₁ <6000, х_х ⁺~^^х2 - 6000, Jc₁, Jc₂ >0.

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

Поскольку —4 < —3 < 0, то в качестве направляющего выбираем пер­

вый столбец. Составив отношение вида -j — к определяем направляю­щи J

щую строку. Для этого находим минимальное отношение

. Г4000 6000 6000] _Лппп „ mmj—j—, —в , —j— > = 4000. Следовательно, направляющая строка -

первая, направляющий элемент -O₁₁=I. Применив первый шаг симп­лексного преобразования, получим новую таблицу (табл. 10.3).

Таблица 10.3

второй, направляющая строка - третья, т.к. ²⁰⁰⁰ < ⁶⁰⁰⁰ < ⁴⁰⁰⁰ . При-

2/3 I О

меним следующий шаг симплексного преобразования. В результате по­лучим табл. 10.4

Таблица 10.4

Так как а_дз = —^ < 0, то направляющий столбец A_v направляющая

3

строка - вторая, направляющий элемент O₂₃ = -. Выполним очередной шаг преобразования, получим еще одну таблицу (табл. 10.5).

Таблица 10.5

Поскольку в индексной строке все элементы положительны, это означает, что найдено оптимальное решение X₁₀= 2000, X₂₀ = 6000, х₃₀ = 2000. Искомое значение целевой функции равно 4 X₁ + Зх₂= 26000.

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

Структура и свойства двойственной задачи. Почти всякую ЗЛП можно рассматривать как экономическую задачу о распределении ре­сурсов b_l,b₂,...,b_m между различными потребителями, например, меж­ду некоторыми технологическими процессами A₁, A₂,...,А_в. Любое до­пустимое решение ЗЛП X₁, х₂,..., х_п дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть ис­пользована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Завод производит три вида продукции х₍, х₂, х₃, каждый из которых требует затрат времени на обработку на токар­ном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограниченно. Пусть с₍, с₂, с₃ - прибыль от реа­лизации единицы соответствующего вида продукции. Требуется опре­делить, каше количество каждого вида продукции необходимо произ­водить в течение заданного интервала времени, чтобы получить мак­симальную прибыль.

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

max (с,х, +C₂X₂ +с₃х₃)

Jt₁ г* j

при ограничениях

'O₁₁X₁+O₁₂X₂+O_uX₃Zb_l-,

• O₂₁X₁+O₂₂X₂+ а₂₃х₃ ^b₂;

O_3iX,+ а₃₂х₂+ а₃₃х₃ <Ь₃,

где O_lj, O₂., а_3у - время, необходимое для обработки единицы j-то вида продукции соответственно на токарном, фрезерном и сверлильном стан­ках Q = 1,2, 3); b_v b₂, Ь₃ - ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков. Сформулированная задача является прямой ЗЛП.

Рассмотрим далее задачу в несколько иной постановке. Обозначим через U, U₂, U₃ цену единицы времени работы на токарном, фрезер­ном и сверлильном станках соответственно, тогда a_nU+a_2lU₂+a_3lU₃ можно трактовать как расходы на изготовление единицы продукции первого вида, a_l2U+a₂₂U₂+a₃₂U₃ - расходы на изготовление единицы продукции второго вида, a_l3U_x+a₂₃U₂+a₃₃U₃ - расходы на изготовление единицы продукции третьего вида.

Для величин расходов выполняются следующие соотношения:

0. ^+а31^3 — ^С\’

■ Ci_l2X_l+a₂₂U₂ +a₃₂U₃ >с₂; (10.7)

Ci_liU_i + Ci₂₃U₂ + я₃₃*₃ ^с₃.

Учитывая, что Ь_х, Ь₂, Ь_ъ - использованный ресурс машинного вре­мени для каждого из станков, тоща b_iU+b₂U₂+b_iU_i - суммарные рас­ходы на производство.

Требуется найти такие U₁, U₂, U_j, удовлетворяющие условиям (10.7), при которых минимизируются суммарные расходы на производство. Таким образом, целевую функцию можно записать в виде

min g(U) = b_iU_l+b₂U₂+b₃U₃, (10.8)

U₁,U_2tU₃

причем U₁, U₂, U₁ > 0.

Задачу (10.8) с ограничениями (10.7) называют двойственной зада­чей по отношению к прямой, сформулированной ранее.

Соотношение прямой и двойственной задач. Между прямой и двойственной задачами имеет место взаимно однозначное отношение. Имея прямую задачу, всеща можно перейти к двойственной и наобо­рот. Данное отношение находит выражение в виде следующих правил:

1. если прямая задача является задачей максимизации, то двой­ственная будет задачей минимизации и наоборот;

2. коэффициенты целевой функции прямой задачи C₁, с₂,..., с_и стано­вятся свободными членами ограничений двойственной задачи;

3. свободные члены ограничений прямой задачи b_i,b₂,...,b_m стано­вятся коэффициентами целевой функции двойственной задачи;”

4. матрицу ограничений двойственной задачи получают транспони­рованием матрицы ограничений прямой задачи;

5. знаки неравенств в ограничениях изменяются на обратные;

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

Переменные U_i, U₂,..., U_m двойственной задачи называют «тене­выми ценами». Двойственную задачу выгоднее решать, чем исходную прямую, если в прямой задаче при малом количестве переменных (т > п) имеется большое количество ограничений.

Запишем обе задачи в матричном виде.

Прямая задача. Найти max/(X) = тахС^тХ при AX < A₀; X > 0.

Двойственная задача. Найти ming(t7) = A₀^tC/ при A^tU > С; U > 0.

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

Теорема 1. Если Х₀и U₀ - допустимые решения прямой и двой­ственной задач, т.е. если AX < A₀ и A^tU > С, то C^tX₀ < A₀U₀, т.е. зна­чения целевой функции прямой задачи никоща не превышают значений целевой функции двойственной задачи.

Теорема 2. Если X₀ и U₀ - допустимые решения прямой и двой­ственной задач и если C^tX₀ = U^rA₀, то X₀ и U₀ - оптимальные реше­ния этих задач.

Таким образом, получено, что если прямая задача есть задача мак­симизации, то двойственная задача—задача минимизации. Остановимся на особенностях решения задач минимизации. Первое правило гласит, что в задачах минимизации направляющий столбец определяют по наи­большему положительному элементу индексной строки. Правило оста­новки для задачи минимизации формулируется так: все элементы ин­дексной строки должны быть неположительными, т.е. a_QJ< 0. И, нако­нец, главная сложность, возникающая при решении задач минимизации,

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

т.е. ограничения имеют вид A⁷U > С; U >0 ■ При приведении системы ограничений к каноническому виду дополнительные переменные вво­дятся в модель с отрицательными знаками. По этой причине они не могут быть введены в базис. Отметим также, что в общем случае постанов­ки задач линейного программирования допускают в ограничениях зна­ки неравенств как «больше или равно», так и «меньше или равно». Не­равенства, в которых имеет место знак «меньше или равно», приводят­ся к каноническому виду путем добавления в первоначальный базис дополнительной переменной, как это было продемонстрировано при ре­шении задачи максимизации симплекс-методом. Для неравенств, име­ющих знак «больше или равно», дополнительная переменная вводится с отрицательным знаком, и в базис введена быть не может. По этой причине определение начального допустимого базиса в общем случае представляет значительные трудности. Для нахождения допустимых базисных решений разработаны специальные методы. Рассмотрим один из них.