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

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

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

…

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

…

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

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

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

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

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

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

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

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

Найти:

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

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

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. По числу критериев оценки альтернатив -

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

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

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

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

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

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

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

Цель:

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

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

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

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

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

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

OpenOffice.org Calc

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