Блинов Е.А. Методическое пособие - Моделирование, алгоритмизация и оптимизация элементов и систем в теплоэнергетике - файл n1.doc

Блинов Е.А. Методическое пособие - Моделирование, алгоритмизация и оптимизация элементов и систем в теплоэнергетике
скачать (1080.6 kb.)
Доступные файлы (4):
n1.doc3173kb.17.03.2009 14:57скачать
n2.ppt1598kb.10.03.2009 13:58скачать
n3.ppt821kb.12.03.2009 13:37скачать
n4.pptx127kb.26.03.2009 17:03скачать

n1.doc

1   2   3   4   5   6

Таблица № 7

Запасы на складах, т

Потребности потребителей, т


Кол-во а/м, N

КТГ

а1

а2

b1

b2

b3

b4

b5

b6


800

850

310

380

320

330

220

240

66

0,75


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

Постановка транспортной задачи.

Имеется n складов A1, A2, ..., An с однородными материальными средствами в количествах а1, а2, . . ., an; имеется m потребителей B1, B2, ..., Bm данных материальных средств, потребности которых равны соответственно b1, b2,..., bm; известны транспортные издержки cij, связанные с доставкой единицы (например, тонны) материальных средств со склада Ai потребителю Bj (i = 1, 2, ..., n; j = 1, 2, ..., m). Графическая постановка – рис. 7.


A2

B1


A1



B2





Bm

Аn

Рис. 7
Требуется определить такой план доставки МС со складов потребителям, при котором суммарные транспортные издержки были бы минимальными.

Математическая модель транспортной задачи.

Неизвестными (управляемыми факторами) в задаче являются величины xij - объем подвоза однородных материальных средств со склада Ai потребителю Bj (i = 1, 2, ..., n; j = 1, 2, ..., m).

Условия, которым должны подчиняться неизвестные:

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

запланированный суммарный объем выдаваемых со склада материальных средств не может превосходить наличия их на складе;

объем подвоза по любому маршруту должен быть неотрицательным.

С учетом сказанного получаем математическую модель:

целевая функция: n m

  cij xij  min,

i=1 j=1

ограничения: n m

xij  bj, j = 1, 2, ..., m,  xij  ai, i = 1, 2, ..., n;

i=1 j=1

условия, накладываемые на неизвестные:

хij 0 i, j.

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

целевая функция:

25x11+35x12+24x13+33x14+27x15+28x16+34x21+25x22+27x23+38x24+28x25+33x26min

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

x11 + x12 + x13 + x14 + x15 + x16 800;

x21 + x22 + x23 + x24 + x25 + x26 850;

x11 + x21  310;

x12 + x22  380;

x13 + x23  320;

x14 + x24  330;

x15 + x25  220;

x16 + x26  240;

условия, накладываемые на неизвестные:

x11  0; x12  0; x13  0; x14  0; x15  0; x16  0;

x21  0; x22  0; x23  0; x24  0; x25  0; x26  0.

Формируем массив исходных данных для решения в виде таблицы 8.

Таблица 8

Склады


Потребители

Запасы, т


В1

В2

В3

В4

В5

В6

А1

25

35

24

33

27

28

800

А2

34

25

27

38

28

33

850

Потреб-ность, т

310

380

320

330

220

240





Результаты решения задачи отображаем на схеме (рис. 8).

На третьем этапе осуществляется постановка задачи динамического программирования, формулируется теорема Беллмана и готовится массив исходных данных.








310 70 250 380


А1

А2




90 330 220


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

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

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

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

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

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

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

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

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

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

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

Требуется спланировать распределение автомобилей по маршрутам вывоза запасов МС со складов потребителям так, чтобы время вывоза было минимальным.

Условием успешного окончания всего комплекса работ по доставке МС потребителям является выделение на каждый маршрут не менее одного автомобиля.

Время доставки запасов (tдост) одним автомобилем составляет:

tдост = tпогр + tвыгр + 2 l Куд / Vср,

где tпогрвремя погрузки МС на складах, ч;

tвыгрвремя выгрузки МС на складе потребителя, ч;

lдлительность маршрута, км;

Кудкоэффициент условий движения на маршруте;

Vсрсредняя скорость движения на маршруте, км/ч.

Тогда полное время доставки запасов МС одному потребителю составляет:

Tдост = tдост m,

где m = Q / (q Nвыд) – необходимое количество рейсов для вывоза запасов МС со склада одному потребителю; округляется в большую сторону;

Qколичество МС, вывозимых для данного потребителя со склада, т;

qсредняя грузоподъемность одного автомобиля, т;

Nвыдвыделенное количество автомобилей на данный маршрут.

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

max {Tдост i }  min.

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

Рассматривается семь маршрутов вывоза запасов с реальными объемами МС – результат решения транспортной задачи линейного программирования – рис. 8. С этой целью введем обозначения используемых маршрутов: маршрут А1 – В1 определим как маршрут № 1 для задачи динамического программирования, А1 – В3 - № 2, А2 – В3 - № 3, А2 – В2 - № 4, А1 – В6 - № 5, А1 – В4 - № 6, А2 – В5 - № 7.

В качестве неизвестных величин будет распределение исправных автомобилей по маршрутам вывоза запасов:

{N1; N2; N3; N4; N5; N6; N7},

где Niвыделенное количество автомобилей на i-й маршрут, i = 1 7.

При этом должно выполняться естественное условие:

7

Ni = N*,

i=1

где N* - количество распределяемых автомобилей.

Время вывоза МС со складов для каждого маршрута, в соответствии с исходными данными, определяется:

T1 = [1,4 + 1,3 + 2 * 25 * 1,2 / 35] * [310 / (5,5 * N1)];

T2 = [1,1 + 1,3 + 2 * 24 * 1,2 / 35] * [70 / (5,5 * N2)];

T3 = [1,3 + 1,3 + 2 * 27 * 1,2 / 35] * [250 / (5,5 * N3)];

T4 = [1,4 + 1,3 + 2 * 25 * 1,2 / 35] * [380 / (5,5 * N4)];

T5 = [1,1 + 1,3 + 2 * 28 * 1,2 / 35] * [90 / (5,5 * N5)];

T6 = [1,4 + 1,3 + 2 * 33 * 1,4 / 35] * [330 / (5,5 * N6)];

T7 = [1,3 + 1,3 + 2 * 28 * 1,2 / 35] * [220 / (5,5 * N7)].

Тогда целевая функция примет вид

max {T1, Т2, Т3, Т4, Т5, Т6, Т7}  min,

а ограничениями будут

T1 + Т2 + Т3 + Т4 + Т5 + Т6 + Т7 = N*;

T1 1; Т2 1; Т3 1; Т4 1; Т5 1; Т6 1; Т7 1;

Данные для решения задачи динамического программирования сведем в таблицу 9.

Таблица 9


Марш-руты

Протяжен-ность, км

Ку.д.

Время разгрузки МС на складе потребителя, ч

Количество МС, перевозимых по данному маршруту, т

1

25

1,2

1,4

310

2

24

1,2

1,1

70

3

27

1,2

1,3

250

4

25

1,2

1,4

380

5

28

1,2

1,1

90

6

33

1,4

1,4

330

7

28

1,2

1,3

220
1   2   3   4   5   6


Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации