Все вопросы к тесту (html) Теоретические основы автоматизированного управления

Для определенности считаем, что решается задача на минимум, т.е.

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

…

1) Приводим стандартный вид ограничений к каноническому. Для этого вводим m дополнительных неотрицательных переменных . Получим следующую систему:

…

2) Исходную расширенную систему заносим в симплексную таблицу:

Последняя строка называется оценочной строкой.

3) Выяснить, имеются ли среди элементов оценочной строки положительные числа. Если все эти числа отрицательны, то процесс закончен; базисное решение является оптимальным. Если в оценочной строке имеется хотя бы одно положительное число, перейти к п. 4.

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

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

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

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

Поиск максимума можно свести к поиску минимума, сменив знаки всех коэффициентов в линейной форме на противоположные:

Задачи оптимального программирования в наиболее общем виде классифицируют по следующим признакам.

1. По характеру взаимосвязи между переменными -

а) линейные,

б) нелинейные.

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

2. По характеру изменения переменных -

а) непрерывные,

б) дискретные.

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

3. По учету фактора времени -

а) статические,

б) динамические.

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

4. По наличию информации о переменных -

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

б) задачи в условиях неполной информации,

в) задачи в условиях неопределенности.

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

5. По числу критериев оценки альтернатив -

а) простые, однокритериальные задачи,

б) сложные, многокритериальные задачи.

В задачах а) экономически приемлемо использование одного критерия оптимальности или удается специальными процедурами (например, «взвешиванием приоритетов») свести многокритериальный поиск к однокритериальному.

Сочетание признаков 1—5 позволяет группировать (классифицировать) в самом общем виде задачи и методы оптимального программирования, например: 1а) 2а) За) 4а) 5а) — задачи и методы линейного программирования, 16) 2а) За) 4а) 5а) — задачи и методы нелинейного программирования, 1а) 26) За) 4а) 5а) — задачи и методы целочисленного (дискретного) линейного программирования и т.д.

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

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

В задаче линейного программирования (ЗЛП) требуется найти экстремум (максимум или минимум) линейной целевой функции

при ограничениях (условиях):

…

где - заданные постоянные величины.

Систему ограничений называют функциональными ограничениями ЗЛП, а ограничения - прямыми.

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

План (допустимое решение), который доставляет максимум или минимум целевой функции, называется оптимальным планом (оптимальным решением) ЗЛП.

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

Пример 1 (задача о смесях). Стандартом предусмотрено, что октановое число автомобильного бензина А-76 должно быть не ниже 76, а содержание серы в нем — не более 0,3%. Для изготовления такого бензина на заводе используется смесь из четырех компонентов. Данные о ресурсах смешиваемых компонентов, их себестоимости и октановом числе, а также о содержании серы приведены в таблице.

Требуется определить, сколько тонн каждого компонента следует использовать для получения 1000 т автомобильного бензина А-76, чтобы его себестоимость была минимальной.

Решение. Для решения этой задачи сформулируем ее экономико-математическую модель, т.е. сформулируем задачу математически. Введем необходимые обозначения: пусть - количество в смеси компонента с номером j. С учетом этих обозначений имеем задачу (критерий оптимальности — «минимум себестоимости»):

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

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

Пример 2 (использование ограниченных ресурсов). На участок строящейся дороги необходимо вывезти 20 000 м3 каменных материалов. В районе строительства имеются три карьера с запасами 8000 м3, 9000 м3 и 10 000 м3. Для погрузки материалов используются экскаваторы, имеющие производительность 250 м3 в смену в карьерах 1 и 2 и 500 м3 в смену в карьере 3.

Эти карьеры обеспечивают каменными материалами также ряд других строящихся объектов. На погрузку материалов для рассматриваемого участка выделен для экскаваторов общий лимит 60 машино-смен с правом использования его по усмотрению строителей.

Транспортные затраты на перевозку материалов характеризуются показателями: для перевозки 10 000 м3 материалов из карьера 1 требуется 1000 автомобиле-смен, из карьера 2 — 1350, из карьера 3 — 1700 автомобиле-смен. Требуется найти оптимальный план перевозок, обеспечивающий минимальные транспортные затрат.

Решение. Сформулируем экономико-математическую модель задачи. Примем за единицу измерения количества материалов 10 000 м3.

Обозначим через — в карьере 3. Необходимо минимизировать транспортные затраты:

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

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

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

Пример 3. Для производства продукции типа П1 и П2 предприятие использует два вида сырья: С1 и С2. Данные об условиях приведены в таблице.

Составить план производства по критерию «максимум прибыли».

Решение. Обозначим объем производства продукции П1 через x1, продукции П2 через x2. С учетом этих обозначений математическая модель задачи имеет вид:

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

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

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

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

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

Слова «учитывало бы внутренние возможности и внешние условия производственной деятельности» означают, что на выбор планово-управленческого решения (поведения) накладывается ряд условий, т.е. выбор D эту область называют также областью определения задачи.

Таким образом, реализовать на практике принцип оптимальности в планировании и управлении — это значит решить экстремальную задачу вида:

где — математическая запись критерия оптимальности - целевая функция. Задачу условной оптимизации обычно записывают в виде:

Найти максимум или минимум функции

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

…

Условие необязательно, но его всегда при необходимости можно добиться. Обозначение говорит о том, что в конкретном ограничении возможен один из знаков: . Более компактная запись:

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

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

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

Объект документ электронной таблицы основан на сервисе com.sun.star.sheet.SpreadsheetDocument. Каждый из этих документов может содержать несколько электронных таблиц. Документ на основе таблицы или документ электронная таблица - весь документ, тогда как электронная таблица (или лист) - лист (таблица) в документе.

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

Пример: доступ по номеру (нумерация начинается с 0)

Dim Doc As Object

Dim Sheet As Object

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets(0)

Пример: доступ по имени

Dim Doc As Object

Dim Sheet As Object

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets.getByName("Лист1")

В первом примере, к листу получают доступ по его номеру (счет начинается с 0). Во втором примере, к листу получают доступ по его имени и с использованием метода getByName.

Электронная таблица состоит из двумерного списка, содержащего ячейки. Каждая ячейка определяется ее X и Y-положением относительно верхней левой ячейки, которая имеет положение (0, 0).

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

Пример:

Dim Doc As Object

Dim Sheet As Object

Dim Cell As Object

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets(0)

Cell = Sheet.getCellByPosition(0, 0)

Cell.String = "Тест"

В дополнение к числовым координатам, каждая ячейка в листе имеет имя, например, верхнюю левую ячейку (0, 0) из электронной таблицы называют A1. Буква A для столбца и номер 1 для строки. Важно не перепутать имя и положение ячейки, потому что счет строк в имени начинается с 1, но счет в положении начинается с 0.

В OpenOffice.org, ячейка таблицы может быть пустой или содержать текст, числа, или формулы. Тип ячейки не определяется содержанием, которое сохранено в ячейке, а скорее свойствами объекта, который использовался для ее ввода. Числа могут быть вставлены и получены с использованием свойства Value, текст – свойства String, а формулы – свойства Formula.

Пример:

Dim Doc As Object

Dim Sheet As Object

Dim Cell As Object

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets(0)

Cell = Sheet.getCellByPosition(0, 0)

Cell.Value = 100

Cell = Sheet.getCellByPosition(0, 1)

Cell.String = "Тест"

Cell = Sheet.getCellByPosition(0, 2)

Cell.Formula = "=A1"

Пример вставляет одно число, один текст, и одну формулу в поле с A1 до A3.

OpenOffice.org рассматривает содержимое ячейки, которое введено с использованием свойства String как текст, даже если содержимое – число. Число в ячейке выравнивается по левому краю вместо выравнивания по правому краю. Необходимо отметить различие между текстом и числами при использовании формулы:

Dim Doc As Object

Dim Sheet As Object

Dim Cell As Object

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets(0)

Cell = Sheet.getCellByPosition(0, 0)

Cell.Value = 100

Cell = Sheet.getCellByPosition(0, 1)

Cell.String = 1000

Cell = Sheet.getCellByPosition(0, 2)

Cell.Formula = "=A1+A2"

MsgBox Cell.Value

Хотя ячейка, A1 содержит значение 100, а ячейка A2, содержит значение 1000, формула A1+A2 возвращает значение 100. Это потому, что содержимое ячейки A2 было введено как строка, а не как число.

Чтобы проверять, содержит содержимое ячейки число или строку, используется свойство Type:

Dim Doc As Object

Dim Sheet As Object

Dim Cell As Object

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets(0)

Cell = Sheet.getCellByPosition(1,1)

Cell.Value = 1000

Select Case Cell.Type

Case com.sun.star.table.CellContentType.EMPTY

MsgBox "Содержимое: Пусто"

Case com.sun.star.table.CellContentType.VALUE

MsgBox "Содержимое: Число"

Case com.sun.star.table.CellContentType.TEXT

MsgBox "Содержимое: Текст"

Case com.sun.star.table.CellContentType.FORMULA

MsgBox "Содержимое: Формула"

End Select

Свойство Cell.Type возвращает значение из списка com.sun.star.table.CellContentType, которое идентифицирует тип содержимого ячейки. Возможные значения:

• EMPTY – пусто, нет значения;

• VALUE – число;

• TEXT – строка;

• FORMULA – формула.

Найти:

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

Приводим стандартный вид ограничений к каноническому:

1. Создайте папку MyWork.

2. Запустите OpenOffice.org Calc. Введите исходную симплекс-таблицу:

3. Сохраните таблицу в созданной папке.

4. Выполните команду Сервис – Макросы – Управление макросами – OpenOffice.org Basic.

5. В поле Макрос из выделите свою таблицу, нажмите на значок «+», выберите Standard. Нажмите на кнопку Создать. В появившемся окне Новый модуль нажмите на кнопку OK.

6. Введите текст макроса:

Sub Main

Dim Doc As Object

Dim Sheet As Object

Dim Cell As Object

Dim d(5,9) As Variant

Dim i,j,r,n,k,m As Integer

Dim p,q,t As String

Dim a,b As Double

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets.getByName("Лист1")

For i = 1 To 5

For j = 1 To 9

Cell = Sheet.getCellByPosition(j-1, i+4)

d(i,j)=Cell.Value

Next j

Next i

n=7

r=3

t="далее"

Do While t="далее"

p="да"

q="нет"

For j=3 To n+2

If d(r+2,j) >0 Then

p="нет"

For i=2 To r+1

If d(i,j) > 0 Then

q="да"

m=j

k=i

End If

Next i

End If

Next j

If p="да" Then

Cell = Sheet.getCellByPosition(0, 11)

Cell.String = "Данное решение является оптимальным:"

t = "конец"

End If

If (p="нет" And q="нет") Then

Cell = Sheet.getCellByPosition(0, 11)

Cell.String = "Оптимального решения не существует"

t="конец"

End If

If t="далее" Then

a = d(k,2)/d(k,m)

For i=2 To r+1

If d(i,m) > 0 Then

b = d(i,2)/d(i,m)

If b < a Then

a=b

k=i

End If

End If

Next i

d(k,1) = d(1,m)

a = d(k,m)

For j=2 To n+2

d(k,j) = d(k,j)/a

Next j

For i=2 To r+2

a = d(i,m)

If i <> k Then

For j=2 To n+2

d(i,j) = d(i,j) - a*d(k,j)

Next j

End If

Next i

For i=1 To 5

For j=1 To 9

Cell = Sheet.getCellByPosition(j-1,i+12)

Cell.Value = d(i,j)

Next j

Next i

Cell = Sheet.getCellByPosition(0,13)

Cell.String = "Базис"

Cell = Sheet.getCellByPosition(1,13)

Cell.String = "Св.члены"

Cell = Sheet.getCellByPosition(0,17)

Cell.String = "F"

End If

Loop

End Sub

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

7. Сохраните введенный макрос помощью команды Файл - Сохранить. Перейдите в режим редактирования таблицы с помощью команды Файл – Закрыть.

8. Выполните команду Сервис – Макросы – Управление макросами – OpenOffice.org Basic. Выделите созданный макрос. Нажмите на кнопку Выполнить. Результат работы программы:

В оценочной строке нет положительных элементов, выполнен критерий оптимальности:

Цель:

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

Результаты обучения:

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

Список рекомендуемой литературы:

• Семакин И.Г. Информационные системы и модели. Учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2005.
• Чернов Д., Еременко А. OpenOffice.org для профессионала. – М.: ДМК Пресс, 2008.
• Хахаев И. OpenOffice.org: Теория и практика. – М.: БИНОМ. Лаборатория знаний, 2008.
• Культин Н.Б., Цой Н.Б. OpenOffice.org 3.0 Calc. – М.: BHV, 2009.

Используемые программы:

OpenOffice.org Calc

Табличный процессор OpenOffice.org Calc – программа, предназначенная для обработки числовой и текстовой информации. С ее помощью можно решать экономические, математические, инженерно-расчетные задачи, проводить статистическую обработку данных, а также отображать числовую информацию в виде различных графиков и диаграмм.

1. Создайте папку MyWork.

2. Запустите OpenOffice.org Calc. Введите исходную симплекс-таблицу:

3. Сохраните таблицу в созданной папке.

4. Выполните команду Сервис – Макросы – Управление макросами – OpenOffice.org Basic.

5. В поле Макрос из выделите свою таблицу, нажмите на значок «+», выберите Standard. Нажмите на кнопку Создать. В появившемся окне Новый модуль нажмите на кнопку OK.

6. Введите текст макроса:

Sub Main

Dim Doc As Object

Dim Sheet As Object

Dim Cell As Object

Dim n,nn,m,mm,i,j,k As Integer

Dim c(9,11),d(9,11) As Variant

Dim a,b As Single

Doc = StarDesktop.CurrentComponent

Sheet = Doc.Sheets.getByName("Лист1")

For i = 1 To 9

For j = 1 To 11

Cell = Sheet.getCellByPosition(j-1, i+3)

c(i,j)=Cell.Value

MsgBox c(i,j)

Next j

Next i

n = 5

m = 6

nn = 2 * n - 1

mm = 2 * m – 1

d(1,mm) = 0

d(1,mm-2) = c(1,mm-1)

d(3,mm) = c(2,mm)

For j = 2 To mm-1 Step 2

d(1,j) = ">"

Next j

For i = 2 To nn-1 Step 2

d(i,mm) = "^"

Next i

d(1,mm-2) = c(1,mm-1)

d(3,mm) = c(2,mm)

For j = mm-4 To 1 Step -2

d(1,j) = d(1,j+2) + c(1,j+1)

Next j

For i = 5 To nn Step 2

d(i,mm) = d(i-2,mm) + c(i-1,mm)

Next i

For k = 1 To m-1 Step 1

i = 3

j = mm - 2 * k

Do

a = c(i,j+1) + d(i,j+2)

b = c(i-1,j) + d(i-2,j)

If a < b Then

d(i,j) = a

d(i,j+1) = ">"

Else

d(i,j) = b

d(i-1,j) = "^"

End If

i = i + 2

j = j + 2

Loop While (i <= nn And j <= mm-2)

Next k

For k = 1 To n-2 Step 1

i = 2 * k + 3

j = 1

Do

a = c(i,j+1) + d(i,j + 2)

b = c(i-1,j) + d(i-2,j)

If a < b Then

d(i,j) = a

d(i,j+1) = ">"

Else

d(i,j) = b

d(i-1,j) = "^"

End If

i = i + 2

j = j + 2

Loop While (i <= nn And j <= mm-2)

Next k

For i = 1 To 9

For j = 1 To 11

Cell = Sheet.getCellByPosition(j-1,i+17)

Cell.String = d(i,j)

Next j

Next i

End Sub

Эта программа реализует описанный выше алгоритм.

7. Сохраните введенный макрос помощью команды Файл - Сохранить. Перейдите в режим редактирования таблицы с помощью команды Файл – Закрыть.

8. Выполните команду Сервис – Макросы – Управление макросами – OpenOffice.org Basic. Выделите созданный макрос. Нажмите на кнопку Выполнить. Результат работы программы:

Оптимальный путь: A1-A2-A3-B3-C3___D3-E3-E4-F4-F5.

Стоимость дороги: 77.

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

Задачи оптимального программирования в наиболее общем виде классифицируют по следующим признакам.

1. По характеру взаимосвязи между переменными -

а) линейные,

б) нелинейные.

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

2. По характеру изменения переменных -

а) непрерывные,

б) дискретные.

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

3. По учету фактора времени -

а) статические,

б) динамические.

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

4. По наличию информации о переменных -

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

б) задачи в условиях неполной информации,

в) задачи в условиях неопределенности.

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

5. По числу критериев оценки альтернатив -

а) простые, однокритериальные задачи,

б) сложные, многокритериальные задачи.

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

Имеется два пункта — начальный Н и конечный К; из первого во второй надо проложить дорогу, которая состоит из вертикальных и горизонтальных отрезков. Стоимость прокладки каждого из возможных отрезков известна (указана на рисунке). Реально дорога будет некоторой ломаной линией, соединяющей точки Н и К. Требуется найти линию с наименьшей стоимостью прокладки:

Будем нумеровать улицы буквами и цифрами. Так, начало планируемой дороги лежит в точке с координатами А1, а конец — в точке F5. Числа на вертикальных и горизонтальных отрезках улиц — стоимости их прокладки (например, участок ВЗ-СЗ стоит 5 единиц в некоторой условной шкале стоимости). Продвигаться при проектировании можно в горизонтальном направлении направо, а в вертикальном — вверх.

Разумеется, возможностей спроектировать дорогу очень много. Например, пройдя сначала весь путь из точки А1 по горизонтали до точки F1, а затем поднявшись по вертикали до точки F5, получим дорогу стоимостью 12+14+8+17-1-9+104-11+10+10=101. Напротив, вначале поднявшись по вертикали до А5, а затем — по горизонтали до F5, получим: 10+10+11+14+12+8+11+5+12=93 — существенно меньше. Однако вопрос о том, как найти самую дешевую дорогу, остается открытым. В принципе возможен перебор всех возможных вариантов (такой метод называют комбинаторным перебором).

Описанная выше постановка задачи — простейшая модель реальной ситуации. Эту же модель можно интерпретировать иначе, например:

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

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

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

Методом динамического программирования решаются, к примеру, следующие задачи:

• выбор кратчайшего пути по городу с произвольной, не обязательно геометрически правильной, сеткой улиц;

• распределение ресурсов между однопрофильными предприятиями с целью максимизации прибыли;

• разработки сетевого плана-графика завоза материалов и производства работ при строительстве объекта с целью минимизации срока строительства.

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

Динамическое программирование — многошаговая процедура оптимизации. На каждом шаге будет совершаться отдельная операция частичной оптимизации; все они в совокупности приводят к оптимальному решению задачи.

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

Последний шаг может быть сделан в F5 либо из F4, либо из Е5. Запишем соответствующие стоимости в квадратики, помещенные в узлы F4 и Е5. Тем самым совершена условная оптимизация последнего шага. Каждый из этих шагов на схеме обозначается стрелкой:

Теперь рассудим, как можно было попасть в F5 за два шага. Исходными положениями могли быть узлы В5, Е4 и FЗ. Путь из D5 безальтернативен, его полная стоимость 5 + 12 = 17 единиц. Запишем число 17 в квадратик в узле D5. Точно так же обстоят дела с путем из FЗ, его полная стоимость за 2 шага, равная 10 + 10 = 20 единиц, помещена в квадратик в узле РЗ. Иначе обстоит дело при движении из Е4: существуют два пути Е4 -> Е5 -> F5 и Е4 -> F4 -> F5. С ними связаны разные стоимости, соответственно 17 + 12 = 29 и 11 + 10 = 21. Запишем в квадратик в узле Е4 минимальную из них и обозначим на схеме стрелкой одношаговый путь Е4 -> F4, соответствующий минимальной стоимости. Тем самым завершена условная оптимизация двух последних шагов (в совокупности).

Третий шаг может быть произведен из позиций С5, D4, ЕЗ и F2. Шаги из С5 и F2 безальтернативны; например, стоимость пути С5 -> F5 можно найти как сумму стоимости пути С5 -> D5 и числа, записанного в квадратике в узле D5. Каждый из двух других путей альтернативен. К примеру, из позиции D4 можно начать движение «вверх» к узлу D5 или «вправо» к узлу Е4. Совокупная минимальная трехшаговая стоимость первой траектории равна 15 + 17 = 32 единицы (число 17 было ранее записано в узле D5), а второй — 8 + 21 = 29 единиц (число 21 было ранее записано в узле Е4). Производим условную оптимизацию и запишем в квадратик в узле В4 число 29. Стрелка, выходящая из узла В4 в сторону узла Е4, показывает направление условного оптимального выбора.

После этого по той же схеме выполняется условная оптимизация четырехшаговых путей, начинающихся в узлах В5, С4, DЗ, Е2 и F1; затем оптимизируем пятишаговые пути и т. д., пока не рассмотрим все узлы.

Рассматривались пути с передвижениями только вверх и вправо. Очевидно, что остальные, «обходные», пути будут неоптимальными. Может оказаться, что два пути, идущие от некоторого пути вверх или вправо, имеют одинаковую стоимость. В этом случае выбирается любой путь. Оптимальный путь из узла А1 в узел F5 — 10+10+4+5+7+10+10+11 + 10=77.

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

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

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

Пусть в рассматриваемой модели число горизонтальных «улиц» равно n, а вертикальных — m. Все данные задачи, входные и выходные, можно свести в массив с размерностью 2n-1 строк и 2m-1 столбцов. Начальные (входные) данные — стоимости горизонтальных участков — занимают в этом массиве места с нечетными номерами строк и четными номерами столбцов; входные данные — стоимости вертикальных участков — занимают места с четными номерами строк и нечетными номерами столбцов.

Входная информация применительно к примеру:

Выходная информация применительно к примеру:

Порядок, в котором формируется массив выходной информации, таков. Вначале заполняются правый столбец и верхняя строка. Затем находится элемент d3,2m-3 и решается вопрос, где поставить стрелку — справа или сверху от него. Затем находятся элементы диагонали d3,2m-5 , d5,2m-3 и определяется местоположение связанных с ними стрелок, затем элементы следующей диагонали d3,2m-7. d5,2m-5, d7,2m-3 пока не дойдем до элемента d2т-1,1.

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

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

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

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

4) Общий эффект (доход) за N шагов слагается из доходов на отдельных шагах, т.е. критерий оптимальности должен быть аддитивным (или приводящимся к нему).

Требуется найти такое решение (п = 1, 2, 3, ..., N), т.е. последовательность , чтобы получить макси­мальный эффект (доход) за N шагов.

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

В основе общей концепции метода динамического программирования лежит принцип оптимальности Беллмана:

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

,

,

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

состоянии ;

- эффект от принятия решения ;

- эффект за оставшиеся п шагов.

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

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

Имеется два пункта — начальный (нижний левый угол) и конечный (верхний правый угол); из первого во второй надо проложить дорогу, которая состоит из вертикальных и горизонтальных отрезков. Стоимость прокладки каждого из возможных отрезков известна:

Имеется два пункта — начальный (нижний левый угол) и конечный (верхний правый угол); из первого во второй надо проложить дорогу, которая состоит из вертикальных и горизонтальных отрезков. Стоимость прокладки каждого из возможных отрезков известна:

Имеется два пункта — начальный (нижний левый угол) и конечный (верхний правый угол); из первого во второй надо проложить дорогу, которая состоит из вертикальных и горизонтальных отрезков. Стоимость прокладки каждого из возможных отрезков известна:

Имеется два пункта — начальный (нижний левый угол) и конечный (верхний правый угол); из первого во второй надо проложить дорогу, которая состоит из вертикальных и горизонтальных отрезков. Стоимость прокладки каждого из возможных отрезков известна:

Имеется два пункта — начальный (нижний левый угол) и конечный (верхний правый угол); из первого во второй надо проложить дорогу, которая состоит из вертикальных и горизонтальных отрезков. Стоимость прокладки каждого из возможных отрезков известна:

Цель:

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

Результаты обучения:

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

Список рекомендуемой литературы:

• Семакин И.Г. Информационные системы и модели. Учебное пособие. – М.: БИНОМ. Лаборатория знаний, 2005.
• Чернов Д., Еременко А. OpenOffice.org для профессионала. – М.: ДМК Пресс, 2008.
• Хахаев И. OpenOffice.org: Теория и практика. – М.: БИНОМ. Лаборатория знаний, 2008.
• Культин Н.Б., Цой Н.Б. OpenOffice.org 3.0 Calc. – М.: BHV, 2009.

Используемые программы:

OpenOffice.org Calc

Табличный процессор OpenOffice.org Calc – программа, предназначенная для обработки числовой и текстовой информации. С ее помощью можно решать экономические, математические, инженерно-расчетные задачи, проводить статистическую обработку данных, а также отображать числовую информацию в виде различных графиков и диаграмм.