Судовые микропроцессорные системы управления

Задача управления производством и запасами

Задача о замене.

Задача оптимального распределения ресурсов.

Полученные рекуррентные соотношения называют функциональными уравнениями Беллмана.

При этом согласно определению z_n(x₀) = F*.

а) Постановка задачи.

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

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

Пусть на реконструкцию и модернизацию 4-х своих филиалов фирма имеет возможность выделить 200 млн. руб. Ожидаемый прирост прибыли зависит как от финансируемого филиала, так и от объема этого финансирования. Однако, прирост прибыли в отдельно взятом филиале не зависит от вложенных средств в другие филиалы, а общая прибыль фирмы равна сумме всех приростов по филиалам. Следует определить оптимальное распределение капиталовложений между филиалами, максимизирующее общий прирост прибыли фирмы.

В данном случае речь идет об однократном распределении средств, и поэтому задача сама по себе не является динамической. Однако, ее можно наиболее просто решить как ‌«многошаговую», если объекты капиталовложений (филиалы) включать в рассмотрение последовательно, т.е. на каждом шаге к рассмотренным добавлять следующий.

При таком подходе можно использовать функциональные уравнения Беллмана. Для их решения в табулированном виде общий объем капиталовложений разбивается на N интервалов с шагом (для нашей задачи положим N = 4, тогда = 200/4=50 млн. руб.). Т.е. значения функций, входящих в уравнения Беллмана, будут определяться только в точках, кратных (в нашем примере в точках 0, 50, 100, 150, 200).

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

Кап. Вложения	Прирост прибыли по филиалам

С =200 – общий объем распределяемых средств;

х - объем средств, выделяемых филиалам (на каждом шаге), 0≤ х ≤C.

F_i(x_i) – ожидаемый прирост i-той фирмы при выделении ей х_i средств. Тогда целевая функция

F = F₁(x₁) + F₂(x₂) + F₃(x₃) + F₄(x₄) → max

при ограничении x₁ + x₂ + x₃ + x₄ = C, x_i ≥ 0, i = .

б) Схема решения.

1. Введем последовательность функций:

z₁(x) – max прибыль фирмы, если x средств выделить одному 1-му филиалу;

z₂(x) – max прибыль фирмы, если x средств распределить между 1-м и 2-м филиалами;

z₃(x) – max прибыль фирмы, если х средств распределить между 3-м и двумя первыми

филиалами;

z₄(x) – max прибыль фирмы, при распределении x средств между всеми 4-мя

филиалами.

Очевидно, что z₄(C) = max F = F*, a z_i(0) = 0.

2. «Обратный ход».

Рассмотрим финансирование только 1-го филиала, тогда по определению

z₁(x) = F₁(x). (1)

Пусть теперь средства в объеме x распределяются между 1-м и 2-м филиалами: 2-му в объеме x₂, тогда х – х₂ = х₁ выделяется 1-му. Общая прибыль двух филиалов

z₂(x) = (F₂(x₂) + z₁(x – x₂)). (2)

Теперь включим в рассмотрение дополнительно 3-й филиал: из общей суммы х выделим 3-му филиалу х₃, тогда остальная часть х – х₃ оптимальным образом распределяется между двумя первыми

z₃(x) = (F₃(x₃) + z₂(x – x₃)). (3)

Наконец, по аналогии находим

z₄(x) = (F₄(x₄) + z₃(x – x₄)). (4)

3. «Прямой ход».

Функциональные уравнения Беллмана (1) – (4) позволяют рассчитать значения z_i и F_i для всех возможных х. Среди них находим z₄(C) = F* и оптимальное x₄* такое, что

F₄(x₄*) = F₄*, после чего результаты вычислений просматриваются в обратном порядке. Зная x₄*, находим С–х₄* - объем финансирования остальных трех филиалов, а следовательно, и F₃* и х₃*, и т.д. до нахождения х₁* и F₁* = F₁(x₁*).

в) Расчет.

….

а) Постановка задачи.

Оборудование со временем изнашивается и стареет морально, падает его производительность, растут издержки на ремонт. Поэтому на каком-то этапе его эксплуатация становится менее выгодной, чем замена на новое. Возникает задача определения оптимальной стратегии замены оборудования в рассматриваемый временной промежуток – плановый период (п/п) с тем, чтобы суммарная прибыль за этот период была оптимальной.

Введем обозначения.

r(t) – стоимость продукции, производимой за год на оборудовании возраста t;

s(t) – остаточная стоимость оборудования возраста t;

u(t) – эксплуатационные издержки за год оборудования возраста t;

p – цена нового оборудования, которым можно заменить устаревшее:

n – число лет в рассматриваемом п/п.

Для дискретности решения задачи возраст оборудования t будем отсчитывать с интервалом 1 год. Управление составляют два возможных решения на каждом этапе (в начале каждого года): «сохранение» – продолжение эксплуатации имеющегося оборудования; «замена» – реализация старого оборудования по остаточной стоимости и приобретение нового по цене p. Целевая функция – суммарная прибыль за п/п F→max. Ограничения определяются критерием замены оборудования: прибыль при дальнейшей эксплуатации старого меньше прибыли после его замены с учетом всех издержек. Если прибыль от нового оборудования равна прибыли при старом, то старое сохраняется еще на год, т.к. оно уже досконально изучено.

б) Схема решения.

Задача решается методом ДП на основе принципа оптимальности Беллмана. В процессе «обратного хода» рассматриваются этапы – временные шаги от конца п/п к его началу.

Введем последовательность функций: z_i(t), i = – максимальная прибыль за последние i лет п/п. Очевидно, что z_n(t₀) = max F = F*, где t₀ – возраст оборудования в начале п/п. Итак, сначала рассматриваем только последний n-ый год п/п, i = 1. Пусть в начале этого года, когда оборудование имеет возраст t лет, выбирается одно из управлений: 1) сохранение оборудования на n-ый год, тогда прибыль за оставшийся год п/п составит r(t) – u(t); 2) замена новым, продажа старого по остаточной стоимости, тогда прибыль составит s(t) – p + r(0) – u(0), где r(0) – стоимость продукции, на новом оборудовании за 1-й год его эксплуатации, u(0) – эксплуатационные издержки нового оборудования за 1-й год. Определяем оптимальное управление, исходя из критерия замены:

- если s(t) – p + r(0) – u(0) ≤ r(t) – u (t), то «сохранить»,

- если s(t) – p + r(0) – u(0) > r(t) – u(t), то «заменить».

z₁(t) = max

Теперь включаем в рассмотрение предпоследний шаг, (n – 1)-й год, i = 2 и установим прибыль за два последних года z₂ (t).

Пусть в начале (n – 1)-го года возраст оборудования t, и было принято решение о его сохранении. Тогда прибыль к концу года зависит r (t) – u (t). При этом на начало n-го года оборудование уже будет иметь возраст t+1, следовательно, в последнем году оно даст прибыль z₁(t+1), а общая прибыль за два последних года составит r (t) – u (t) + z₁(t+1).

Если же в начале (n-1)-го года выбрано управление ”замена”, то прибыль за два последних года составит s (t) – p + r (0) – u (0) + z₁(1), следовательно,

z₂(t) = max

Аналогично для i последних лет:

z_i(t) = max

Дойдя до последнего шага (i = n), попадаем в начало п/п, где t известно: t = t₀, и, следовательно, можно начать ”прямой ход”.

Задавая t₀ и длительность п/п, находим F* = z_n(t₀) и строим последовательность оптимальных управлений, начиная с первого года и заканчивая последним.

в) Расчет.

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

1. Определить φ (t) = r(t) – u(t), m₁ = S(t) – p + φ(0):

- если m₁ = const, то справа к таблице прибавляется дополнительный столбец m_i;

- если m₁ = m₁(t), то над каждой строкой z_i(t) вводится дополнительная строка m_i = m_i(t)

(или m_i(t) вписывается в клетки значений z_i(t) как тарифы транспортной задачи).

2. Заполнить строку z₁(t), переписав из таблицы данных соответствующие значения

φ(t) ≥ m₁, все значения φ(t) < m₁ заменить на m₁.

3. Начиная с индекса i = 2, расчет по строкам производится в следующей последовательности:

а) вычислить m_i = m₁ + z_i-1(1), где z_i-1(1) берется из уже заполненной строки;

б) вычислить z_i(t) = z₁(t) + z_i-1(t+1), где сумма и слагаемые образуют треугольник, у

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

последней заполненной строке следующего столбца. Получаемые значения z_i(t) ≥ m_i

вносить в соответствующие клетки строки; начиная с первого z_i(t) < m_i, оставшиеся

клетки заполнить значением m_i;

в) клетки с первым значением z_i(t) < m_i в процессе заполнения таблицы отделить от

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

г) если таблица не заполнена до последней строки, перейти к п. а) и выполнить расчет

для следующего значения индекса i.

Замечания:

1. Для задачи об оптимальном распределении капиталовложений по полученной расчетной таблице можно получить стратегию вложения средств, например, только в первые 3 филиала, исключив из рассмотрения 4-й, или, например, для суммы в 150 млн. руб. (а не 200) между 4-мя филиалами, или только 3-мя первыми и т.д.

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

Это так называемый «принцип погружения» метода динамического программирования.

2. Решенную задачу о замене оборудования можно усложнить, например, допуская замену не новым оборудованием, а уже проработавшим некоторое время. При этом имеется три возможных управления: сохранить старое, купить новое, купить не новое.

Предприятие производит партиями некоторые изделия. Оно получило заказы на n месяцев. Необходимо составить план производства на указанные n месяцев с учетом затрат на производство и хранение. Обозначим:

1) x_j – число изделий, производимых в j-м месяце;

2) y_j - величина запаса к началу j-го месяца (Это число не содержит изделий,

производимых в j-й месяц, величина запаса к началу 1-го месяца (y₁) и к концу

последнего (y_n+1) заданы);

3) d_j – число изделий, которые должны быть отгружены в j-й месяц;

4) - функция затрат на производство x_j изделий в j-м месяце (может

иметь и другой вид);

5) h_j – затраты на хранение единицы запаса, переходящей из месяца j в месяц (j+1);

6) - функция затрат на производство и хранение в j-м месяце.

Задача состоит в определении плана производства (х₁,х₂,…,х_n), компоненты которого удовлетворяют условиям материального баланса

x_j +y_j –d_j = y_j+1

и минимизируют суммарные затраты за весь период

.

По смыслу , ,. Заметим, что:

1) для любого месяца j величина запаса к концу месяца должна удовлетворять ограничениям

,

то есть объем производимой продукции x_j в j-м месяце может быть настолько

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

имеет смысла иметь y_j+1 больше суммарного спроса всех последующих месяцев;

2) из балансового уравнения получим .

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

Составим функциональные уравнения. Пусть F_k(y_k+1) - минимальные затраты за

первые k месяцев.

Для k = 1:

при и . На начальном этапе при фиксированном значении y₁ исходного запаса каждому значению y₂ отвечает только одно значение x₁.

Для k 2:

при , и .

Применив процедуру динамического программирования, на последнем шаге k = n определяется значение x_n* оптимального решения, а остальные компоненты определяются в результате прямого хода по формуле

.

оглавление

Лекция 1. Принципы построения и функционирования микроэвм

Лекция 2. Память микроэвм. Средства реального времени

Лекция 3. организация процесса обработки данных в микропроцессоре и микроэвм

Лекция 4. Структура МПСУ. Адаптеры датчиков и исполнительных механизмов

Лекция 5. Принципы реализации на микроэвм функций регулятора

Лекция 6. Стандартные интерфейсы периферийных устройств микроэвм

Лекция 7. Микропроцессорные системы централизованного контроля. Блок SAU 8800

Лекция 8. Принципы построения судовых МПСУ

Лекция 9. Судовая МПСУ " Data chief-7 "

Лекция 10. Судовая МПСУ " Data chief-C 20"

Лекция 11. Микропроцессорная система управления двигателей серии МЕ фирмы MAN B&W

Лекция 12. Принципы построения систем питания

Лекция 13. Основы технического обслуживания микропроцессорных систем

Дата добавления: 2014-01-06