close

Вход

Забыли?

вход по аккаунту

?

Gamov 0A9A54A1DB

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное
учреждение высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
МЕТОДЫ ОПТИМИЗАЦИИ
Методические указания
Санкт-Петербург
2015
Составитель – В. Ю. Гамов
Рецензенты: доктор технических наук, профессор Л. А. Осипов;
доктор технических наук, профессор М. Ю. Охтилев
Приведены рекомендации по выполнению самостоятельной работы с использованием табличного процессора Excel для математического моделирования и решения однокритериальных оптимизационных задач на персональном компьютере. Излагаемый материал основывается на использовании теории моделирования, теории оптимизации, теории систем, элементов факторного анализа, алгоритмов обработки и управления, методов построения сложных систем и
процессов.
Предназначено для студентов технических вузов, обучающихся
по специальности 230105 – «Программное обеспечение вычислительной техники и систем управления», а также по направлению подготовки 231000 – «Программная инженерия» (квалификация (степень)
«магистр») по дисциплинам «Компьютерное моделирование» и
«Методы оптимизации».
Публикуется в авторской редакции.
Компьютерная верстка В. Н. Костиной
Сдано в набор 27.10.2014. Подписано к печати . Формат 60×84 1/16.
Усл. печ. л. 2,3. Тираж 100 экз. Заказ № 129.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
2
© Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2015
ПРЕДИСЛОВИЕ
Содержание учебного пособия сформировалось на основе материалов лекций, а также результатов проведения самостоятельных
работ (СР), которые на протяжении ряда лет читались студентам
Санкт-Петербургского государственного университета аэрокосмического приборостроения. Данное учебное пособие помогает студентам подготовиться к самостоятельной работе и освоить теоретический материал с практической стороны для математического моделирования и решения оптимизационных задач на персональном
компьютере.
Изложение материала базируется на использовании теории
моделирования, теории оптимизации, теории систем, элементов
факторного анализа, алгоритмов обработки и управления, методов
построения сложных систем и процессов, доступных для освоения
студентами технических вузов.
3
1. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ЭВМ
Цель работы:
исследовать возможности табличного процессора Excel для математического моделирования и решения оптимизационных задач
на персональном компьютере.
Задание:
– нарисовать схему, наглядно изображающую распределение
рейсов самолетов разных типов по маршрутам на планируемый период;
– провести описание математической модели, выбранной для
оптимизации планирования;
– запустить табличный процессора Excel и ввести исходные данные, характеризующие использование самолетов на различных
маршрутах;
– разместить в ячейках электронной таблицы изменяемые переменные, выражение целевой функции и левых частей уравненийограничений;
– выполнить расчеты по вариантам для получения оптимального плана и рациональных планов, используя для решения задачи
линейного программирования и настройку «Поиск решения» табличного процессора Excel;
– сравнить полученные результаты оптимального плана и рациональных планов с первоначальным;
– сделать выводы по проведенному исследованию.
4
2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
Расчет оптимального плана возможен, если выбран критерий
оптимизации. В качестве такого критерия может служить один из
показателей эффективности. Для планирования использования
самолетов по различным маршрутам этим показателем эффективности может служить показатель суммарных затрат, необходимых
для обеспечения перевозки пассажиров. Очевидно, что этот показатель должен быть как можно меньше. Рассмотрим типичную ситуацию, при которой необходимо оптимальное планирование и принятие эффективного решения.
В аэропорту для перевозки пассажиров по n маршрутам может
быть использовано m типов самолетов. Вместимость самолета i-го
типа равна Аi человек, количество пассажиров, перевозимых по
j-му маршруту за сезон, составляет Bj человек. Затраты, связанные
с использованием самолета i-го типа на j-м маршруте, составляют
Sij. Необходимо определить, сколько рейсов Xij необходимо выполнить самолетами i-го типа на каждом из j-х маршрутов, чтобы удовлетворить потребности в перевозках.
С точки зрения летного состава самым справедливым будет
план, разработанный по принципу равного распределения рейсов
на каждом маршруте, при котором
x11 = x21, x12 = x22 , x13 = x23
и т. д.
Однако этот план, назовем его первоначальным, будет чрезмерно затратным. В каждом варианте самостоятельной работы заданы
общие затраты F1 – затраты по первоначальному плану. С этими затратами надо будет сравнить затраты F, рассчитанные с помощью
математической модели.
5
3. ОПИСАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ
Данная задача является задачей линейного программирования
(прил. 1) с шестью переменными x11, x21, x12 , x22 , x13 , x23 , которая
имеет m = 3 уравнений-ограничений, т. е. число неизвестных больше числа уравнений-ограничений:
À1 × x11 + À2 × x21 = B1,
À1 × x12 + À2 × x22 = B2 ,
À1 × x13 + À2 × x23 = B3 .
(1)
Кроме того, неизвестные переменные неотрицательны:
Xij ³ 0. (2)
Требуется найти оптимальное решение задачи линейного программирования, обращающее в минимум линейную функцию шести неизвестных:
F = (S11 × x11 ) + (S21 × x21 ) + (S12 × x12 ) +
+(S22 × x22 ) + (S13 × x13 ) + (S23 × x23 ). (3)
В ходе решения задачи минимизации целевой функции (3) получим параметры оптимального плана распределения самолетов
по маршрутам {Xij}, т. е. число рейсов самолетов каждого типа,
запланированных на каждый маршрут. Это решение и будет тем
единственным вариантом, который обеспечит наименьшие общие
затраты F.
Однако, этот оптимальный план, рассчитанный с помощью математического моделирования, тоже может быть имеет недостатки, о которых будет сказано ниже.
6
4. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ  
В ЭЛЕКТРОННОЙ ТАБЛИЦЕ
4.1. Размещение исходных данных
Для решения задачи оптимизации планирования может быть
использован табличный процессор Excel [6, 11].
В качестве конкретного примера для нахождения оптимального
варианта распределения самолетов по маршрутам покажем расчеты для двух типов самолетов, распределяемых по трем маршрутам
при следующих исходных данных:
– вместимость самолета:
– 1-го типа (А1), чел.
12
– 2-го типа (А2), чел.
15
– количество пассажиров, перевозимых за сезон:
– по 1-му маршруту (В1), чел.
5400
– по 2-му маршруту (В2), чел.
1350
– по 3-му маршруту (В3), чел.
2700
– затраты для различных маршрутов:
– для самолета 1-го типа на по 1-м маршруте (S11), у. е. 100
– для самолета 1-го типа на по 2-м маршруте (S12), у. е. 196
– для самолета 1-го типа на по 3-м маршруте (S13), у. е. 292
– для самолета 2-го типа на по 1-м маршруте (S21), у. е. 156
– для самолета 2-го типа на по 2-м маршруте (S22), у. е. 306
– для самолета 2-го типа на по 3-м маршруте (S23), у. е. 456
– затраты по первоначальному плану (F1), у. е. 151100
Для использования исходных данных при расчетах, их необходимо ввести в ячейки электронной таблицы. На рис. 1 показан вариант размещения исходных данных.
Из рис. 1 видно, что для исходных данных отведена область ячеек А3:Е8. Размещение заданных числовых значений по адресам
ячеек показано в таблице 1.
Исходные данные:
Тип A1
Тип A2
Затраты на перевозку типом i на маршруте j
S11
S12
S13
12
100
196
292
15
156
306
456
5 400
1 350
2 700
Рис. 1. Вариант размещения исходных данных
7
Таблица 1
Обозначения
Заданные
значения
Адреса ячеек
А1
А2
12
15 5400 1350 2700 100 156 196 306 292 456
В6 В7
В1
С8
В2
D8
В3
Е8
S11
С6
S21
С7
S12 S22 S13 S23
D6
D7
Е6
Е7
4.2. Размещение целевой функции
При решении задач линейного программирования, транспортных задач и других задач оптимизации в табличном процессоре Excel используется надстройка «Поиск решения»
(см. прил. 4). При этом математическая модель в электронной
таблице располагается в двух местах: в ячейках самой электронной таблицы и в специальном диалоговом окне надстройки
«Поиск решения».
В ячейках самой электронной таблицы необходимо отвести специальную область для изменяемых ячеек, для выражений, из которых состоит целевая функция, а также для выражений левой части
уравнений-ограничений.
В диалоговом окне надстройки «Поиск решения» располагается
информация о местонахождении целевой функции, соотношения
между левыми и правыми частями уравнений-ограничений, условие неотрицательности, определяемое выражением (2), адреса изменяемых ячеек и другие ограничения.
Изменяемые ячейки, расположенные в самой электронной таблице, в исходном положении будут содержать начальные значения неизвестных {Xij}, например нулевые. В ходе решения задачи
оптимизации содержимое этих ячеек будет изменяться, приближаясь при каждом шаге к тем значениям, при которых целевая
функция будет иметь минимальное (максимальное) значение.
Примерный вид этой области показан на рис. 2.
Из рис. 2 видно, что для неизвестных {Xij} отведены изменяемые
ячейки С14:Е15.
Размещение изменяемых переменных по адресам ячеек показано в табл. 2.
Таблица 2
8
Изменяемые переменные
x11
x12
x13
x21
x22
x23
Адреса ячеек
C14
D14
E14
C15
D15
E15
Результаты
(после поиска решения):
Число рейсов типом i на маршруте j
1 маршрут
2 маршрут
3 маршрут
Всего
Тип A1
0
Тип A2
0
0
0
0
Целевая функция:
0
0
0
Тип A1
0
0
0
Тип A2
0
0
0
Перевезено всего:
0
0
0
0
Прочие результаты:
Будет перевезено пассажиров:
Рис. 2. Вариант размещения области целевой функции
Описание математической модели (п. 2.2) для решения данной
задачи содержит выражения, элементами которых являются переменные. Для построения математической модели в электронной
таблице необходимо выполнить переход к выражениям, роль переменных в которых будут выполнять адреса ячеек.
Адреса ячеек, отведенные для выражений, из которых состоит
целевая функция (3), показаны в табл.3.
Таблица 3
Выражения = S11 * x11 + S21 * x21 = S12 * x12 + S22*x22 = S13 * x13 + S23 * x23
Адреса
ячеек
C18
D18
E18
Выражения
= (S11 * x11 + S21 * x21) + (S12 * x12 + S22 * x22) +
+ (S13 * x13 + S23 * x23)
Адреса
ячеек
B18
Адреса ячеек, отведенные для выражений левой части уравнений-ограничений (1), показаны в табл.4.
9
Таблица 4
Выражения = A1 * x11 = A2 * x21 = A1 * x12 = A2 * x22 = A1 * x13 = A2 * x23
Адреса
ячеек
C22
C23
D22
D23
E22
E23
Выражения = A1 * x11 + A2 * x21 = A1 * x12 + A2 * x22 = A1 * x13 + A2 * x23
Адреса
ячеек
C24
D24
E24
Проведем размещение математической модели в диалоговом окне
надстройки «Поиск решения». Функция поиск решения выбирается
из пункта «Данные» верхнего меню программы Excel. Если функция
отсутствует, то ее требуется активировать. Для активации требуется
в верхнем меню зайти в команду «Файл», выбрать пункт «Параметры»,
затем в открывшемся окне зайти в пункт «Надстройки». Затем требуется выбрать в списке неактивных надстроек пункт «Поиск решения»
и активировать его через команду «Перейти». Функция поиск решения будет доступна в пункте «Данные» верхнего меню.
Для выполнения поиска решения требуется зайти в функцию
«Поиск решения». Для поиска решения в отобразившемся окне требуется: выбрать ячейку, в которую будет заноситься значение целевой функции (пункт «оптимизировать целевую функцию»); выбрать
область изменяемых ячеек, которые содержат изменяемые значения
(пункт «изменяя ячейки переменных»). Ограничения вводятся через кнопку «Добавить». В результате нажатия на кнопку «Добавить»
будет отображено окно, в котором вводятся ограничения. В этом окне вводятся операнды и их соотношения. Ограничение после ввода
данных добавляется в параметры нажатием на кнопку «Добавить».
4.3. Технология создания электронной таблицы
Создание таблицы проведем пошагово.
1. Запустить программу Excel (Пуск / Программы / Microsoft Excel).
Создать рабочую книгу CR_MO_XX.XLS. (XX – номер варианта).
Рабочая книга будет состоять из шести листов. Лист «L0» – расчет
оптимального плана. Листы «L1», «L2», «L3», «L4» – расчеты рациональных планов. Лист «Результаты» – сводная таблица, графики и
диаграммы.
2. Первому рабочему листу дать новое имя, для этого дважды
щелкнуть на ярлычке «Лист 1» и присвоить ему имя «L0».
3. Ввести исходные данные (рис. 3).
10
Исходные данные:
Затраты на перевозку типом i на маршруте j
S11
S12
S13
Тип A1
12
100
196
292
Тип A2
15
156
306
456
5 400
1 350
2 700
B1
B2
B3
Потребности :
Начальные значения (до поиска решения):
Результаты
(после поиска решения):
Число рейсов типом i на маршруте j
1 маршрут
2 маршрут
3 маршрут
Всего
Тип A1
0
0
0
0
Тип A2
0
0
0
0
Целевая функция:
Рис. 3. Вариант размещения области введения исходных данных
В ячейки В6, В7 занести вместимость самолетов – 12 и 15 соответственно. В ячейки С8, D8, Е8 занести планируемое число пассажиров на маршрутах 5400, 1350 и 2700 соответственно. В ячейках
диапазона (С6:Е7) разместить таблицу затрат, связанных с перевозкой.
4. В ячейки С14, D14, Е14, С15, D15, Е15 занести нули. В дальнейшем значения этих ячеек будут подобраны автоматически.
5. В ячейках С22:Е23 нужно указать формулы для расчета пассажиров по типам самолетов, по маршрутам. В ячейке С22 формула
будет иметь вид: = В6 * С14, остальные формулы можно получить
методом копирования. Следует обратить внимание на особенности
использования абсолютных и относительных адресов.
6. В ячейках С24:Е24 нужно указать формулы для расчета пассажиров по маршрутам. В ячейке С24 формула будет иметь вид:
= СУММ(С22:С23). Остальные формулы можно получить также методом копирования.
7. В ячейку В18 занести формулу, обеспечивающую вычисление
общих затрат – выражение целевой функции = СУММ(С18:Е18).
8. Выполнить команду «Поиск решения» в меню «Сервис». Откроется
диалоговое окно «Поиск решения». Диалоговое окно, предназначенное
для ввода второй части математической модели, показано на рис. 4.
11
Рис. 4. Окно меню «Поиск решения»
9. В поле «Установить целевую ячейку» указать ячейку, содержащую оптимизируемое значение $B$18. Установить переключатель
«Равной: минимальному значению», т.к. в данной задаче требуется минимизировать затраты, исходя из заданного критерия оптимальности.
10. В поле «Изменяя ячейки» задать диапазон подбираемых параметров $C$14:$E$15.
11. Чтобы определить набор ограничений, щелкнуть на кнопке «Добавить». Во всплывающем диалоговом окне «Добавление
ограничения» (рис. 5) в поле «Ссылка на ячейки:» указать диапазон $C$24:$E$24. В качестве условия задать «=». В поле
«Ограничение:» задать диапазон $C$8:$E$8. Это условие указывает, что число перевозимых пассажиров не должно быть меньше
потребностей. Щелкнуть на кнопке «ОК».
12. Снова щелкнуть на кнопке «Добавить». В поле «Ссылка на
ячейки:» указать диапазон $C$14:$E$15. В качестве условия задать
«>= ». В поле «Ограничение:» задать число «0». Это условие указывает, что число рейсов неотрицательно. Щелкнуть на кнопке «ОК».
Рис. 5. Всплывающее диалоговое окно «Добавление ограничения»
12
Рис. 6. Всплывающее диалоговое окно «Результаты поиска решения»
13. Щелкнуть на кнопке «Выполнить» (Рис. 4). По завершению оптимизации откроется диалоговое окно «Результаты поиска решения» (Рис. 6).
Установить переключатель на «Сохранить найденное решение»,
после чего щелкнуть на кнопке «ОК».
Как видно из рис. 7, область для изменяемых ячеек заполнилась
результатами решения.
Исходные данные:
Затраты на перевозку типом i на маршруте j
S11
S12
S13
Тип A1
12
100
196
292
Тип A2
15
156
306
456
5 400
1 350
2 700
B1
B2
B3
Потребности :
Начальные значения (до поиска решения):
Результаты
(после поиска решения):
Число рейсов типом i на маршруте j
1 маршрут
2 маршрут
3 маршрут
Всего
Тип A1
450
113
225
788
Тип A2
0
0
0
0
Целевая функция:
45 000
22 050
65 700
Тип A1
5 400
1 350
2 700
Тип A2
0
0
0
5 400
1 350
2 700
132 750
Прочие результаты:
Будет перевезено пассажиров:
Перевезено всего:
Рис. 7. Результат решения
13
В результате решения задачи моделирования с помощью пакета
Excel получено оптимальное решение. Ввиду того, что число рейсов
должно быть целым числом, возможно округление переменных {Xij} и,
как следствие, незначительное расхождение в результатах расчетов.
14. После окончания работы программы необходимо сохранить
рабочую книгу CR_MO_XX.XLS в своей папке.
14
5. РЕШЕНИЕ И ОБРАБОТКА РЕЗУЛЬТАТОВ
МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ
Оптимальный план, который был получен в результате математического моделирования на листе «L0» электронной таблицы, не
всегда может быть реализован на практике. Вероятнее всего, может
не устроить то, что оптимальному плану одному из типов самолетов
должно быть запланировано ноль рейсов. Такой результат был получен в рассматриваемом нами примере, представленном на рис. 7.
При этом, общие затраты (3) будут составлять F = 132750 у. е.
Если сравнить оптимальный план с первоначальным, при котором
общие затраты F1 = 151100 у. е., то получится, что оптимальный
план дешевле на 18350 у. е.
На практике рекомендуется рассчитывать несколько планов
с учетом особенностей подобного рода. Например, количество рейсов самолетов 1-го типа можно ограничить некоторой величиной.
Однако более практичным является внесение ограничений относительного порядка. Для этого используется коэффициент k. Общие
затраты F рассчитываются при разных соотношениях суммарного
числа рейсов самолетов 1-го и 2-го типов.
x + x12 + x13
k = 11
.
x21 + x22 + x23
Если добавить такое ограничение, то в процессе моделирования
можно рассчитать целый ряд планов. В отличие от оптимального
плана такие планы называются рациональными планами.
Расчет первого рационального плана, при котором k = 1/4, необходимо выполнить на втором листе «L1» рабочей книги. Для получения
математической модели первого рационального плана необходимо:
– скопировать лист «L0»;
– переименовать скопированный лист «L0(1)» на «L1»;
– внести ограничения в диалоговом окне «Поиск решения».
– Для внесения ограничений, соответствующих первому рациональному плану (лист «L1»), необходимо выполнить следующие действия:
– установить курсор в ячейку В18 и выполнить команду «Поиск
решения» в меню «Сервис». Откроется диалоговое окно «Поиск решения». В окне ввести дополнительные ограничения (рис. 8);
– щелкнуть на кнопке «Добавить». В поле «Ссылка на ячейку» (рис. 5) указать ячейку $В$14. В качестве условия выбрать
15
Рис. 8. Диалоговое окно «Ограничения»
пункт «=». В поле «Ограничение» задать $В$15/4. Это условие позволяет внести дополнительное ограничение, обеспечивающее планирование для 2-го типа самолетов в объеме четвертой части от всех
рейсов первого типа самолетов. Щелкнуть на кнопке «ОК».
Расчеты второго, третьего и четвертого рациональных планов
{Xij}, при которых коэффициенты k равны 2/3, 3/2, 4 необходимо
выполнить на листах «L2», «L3», «L4» рабочей книги. Эти листы
рекомендуется формировать как копии листа «L1» с соответствующим переименованием. Ограничения при получении второго, третьего и четвертого рациональных планов будут иметь вид:
$В$14 = $В$15 * 2/3
$С$14:$Е$15> = 0
$С$24:$Е$24 =
= $С$8:$Е$8
$В$14 = $В$15 * 3/2
$С$14:$Е$15> = 0
$С$24:$Е$24 =
= $С$8:$Е$8
$В$14 = $В$15 * 4
$С$14:$Е$15> = 0
$С$24:$Е$24 =
= $С$8:$Е$8
Пятый лист рабочей книги «Результаты» должен содержать сводную таблицу планов, диаграмму процентного распределения рейсов и графики. Сводная таблица содержит информацию по каждому из рассчитанных планов.
Для ее формирования рекомендуется выполнить следующие
действия:
– переключиться на лист «Результаты»;
– установить курсор в первую ячейку свободной таблицы, например В5;
– ввести символ « = »;
– переключиться на лист одного из планов, например «L0»;
– установить курсор на ячейку, например С14;
– нажать клавишу «Enter».
После выполнения указанных действий в ячейке В5 листа
«Результаты» сформировалась формула = ’ L0’!С14.
16
Аналогично формируются все остальные ячейки сводной таблицы.
Ниже приведен пример сводной таблицы в обычном режиме
(табл. 5) и в режиме отображения формул (табл. 6).
Таблица 5
k
–
1/
2/
3/
4
x11
x12
x13
x21
x22
x23
F
450
113
225
0
0
0
132750
0
0
131
360
90
75
156225
0
49
225
360
51
0
147013
92
113
225
286
0
0
141627
263
113
225
150
0
0
137400
k
–
1/
2/
3/
4
x11
x12
x13
x21
x22
x23
F
= ’L0!С14
= ’L0’!D14
= ’L0’!Е14
= ’L0’!С15
= ’L0’!D15
=’L0’!Е15
= ’L0’!В18
= ’L1!С14
= ’L1’!D14
= ’L1’!Е14
= ’L1’!С15
= ’L1’!D15
= ’L1’!Е15
= ’L1’!В18
= ’L2!С14
= ’L2’!D14
= ’L2’!Е14
= ’L2’!С15
=’L2’!D15
= ’L2’!Е15
= ’L2’!В18
= ’L3!С14
= ’L3’!D14
= ’L3’!Е14
= ’L3’!С15
=’L3’!D15
= ’L3’!Е15
= ’L3’!В18
= ’L4!С14
= ’L4’!D14
= ’L4’!Е14
= ’L4’!С15
=’L4’!D15
= ’L4’!Е15
= ’L4’!В18
4
3
2
Таблица 6
4
3
2
Построить график общих затрат для оптимального плана и рациональных планов на основе сводной таблицы.
Построить диаграмму процентного распределения рейсов для
каждого плана на основе сводной таблицы (рис. 10).
Имея несколько планов, наглядно отличающихся друг от друга
рассчитанными затратами на перевозку, принятие решения становится более убедительным. Самым затратным оказался план
(F1 = 151500). Самым экономичным – оптимальный (F = 132750).
Однако, согласно оптимальному плану, второму типу самолетов
должно быть запланировано ноль рейсов. Четвертый рациональный
план (F = 137400) обойдется на 4650 у. е. дороже оптимального, но
вторым типам самолетов все же будет запланировано 150 из 750 рейсов. Третий рациональный план (F = 141627) обойдется на 8877 у. е.
дороже оптимального.
В приведенном примере всего два типа самолетов и три маршрута. В реальных задачах размерности этих параметров значительно
больше, но принцип решения остается тем же.
17
6. СОДЕРЖАНИЕ ОТЧЕТА О ВЫПОЛНЕНИИ РАБОТЫ
Отчет о выполнении работы должен содержать (Прил. 2):
– схему распределения рейсов на планируемый период;
– описание математической модели;
– инструкцию для запуска табличного процессора Excel;
– таблицы размещения изменяемых переменных, выражений
целевой функции и левых частей уравнений-ограничений;
– инструкцию для решения задачи линейного программирования с использованием надстройки «Поиск решения»;
– результаты расчета оптимального плана;
– результаты расчета четырех рациональных планов;
– инструкцию для формирования сводной таблицы;
– график общих затрат для рассчитанных вариантов планов;
– выводы по проведенной работе.
Исходные данные для выполнения работы необходимо получить
из вариантов, представленных в прил. 3.
18
ЗАКЛЮЧЕНИЕ
Таким образом, программу Excel можно использовать для решения сложных задач оптимизации. Для решения таких задач
необходимо сформулировать условия табличным образом, задать
ограничения, которым должно удовлетворять решение при поиске
оптимального набора переменных.
Однако, необходимо помнить, что даже для несложной задачи
оптимизации найти оптимальное решение подбором практически
невозможно.
Исходя из этого, целесообразно находить не оптимальное решение, а рациональные. Эти решения, при удовлетворении требования заданной критериальной эффективности, будут отличаться
друг от друга значениями по другим критериям. Например, по
критериям оперативности, затрат, вероятности достижения цели и
качества выполнения задачи. Такие критерии обычными методами
не сравнимы между собой. Учет двух и более критериев в задачах
оптимизации называется многокритериальной оптимизацией.
В нашем примере была решена однокритериальная задача оптимизации. Примеры многокритериальной оптимизации будут рассмотрены в других методических пособиях.
19
Список литературы
1. Абрамов Л. М., Капустин В. Ф. Математическое программирование. – Учебное пособие. – Л.: ЛГУ, 1981. – 328 с.
2. Акулич И. Л. Глава 1. Задачи линейного программирования, Глава 2. Специальные задачи линейного программирования // Математическое программирование в примерах и задачах. – М.: Высшая школа, 1986. – 319 с. – ISBN 5-06-002663-9
3. Астафьев Н. Н. Бесконечные системы линейных неравенств
в математическом программировании. –М.: Наука, 1991. – 134 с.
4. Ашманов С.А., Тимохов А.В. Теория оптимизации в задачах и
упражнениях. – М.: Наука, 1991. – 446 с.
5. Гасс С. Линейное программирование. – М.: Физико-математическая литература, 1961. – 300 с.
6. Грег Харвей. Microsoft Excel 2013 для чайников = Excel
2013 For Dummies. – М.: «Диалектика», 2013. – 368 с. –
ISBN 978-5-8459-1855-0
7. Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. – М.: Наука, 1966. – 348 с.
8. Карманов В. Г. Математическое программирование. – 3-е издание. – М.: Наука, 1986. – 288 с.
9. Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика. Математическое программирование. – Минск.: Вышейшая
школа, 1994. – 286 с.
10. Томас Х. Кормен и др. Глава 29. Линейное программирование // Алгоритмы: построение и анализ = INTRODUCTION TO
ALGORITHMS. – 2-е изд. – М.: «Вильямс», 2006. – С. 1296. – ISBN
5-8459-0857-4.
11. Уокенбах Д. Excel 2013: профессиональное программирование на VBA = Excel 2013 Power Programming with
VBA. – М.: «Диалектика», 2014. – 960 с. – ISBN 978-5-8459-1877-2
12. Шевченко В. Н., Золотых Н. Ю. Линейное и целочисленное линейное программирование. – Нижний Новгород: Издво Нижегородского госуниверситета им. Н. И. Лобачевского,
2004. – 154 с.
13. Юдин Д. Б., Гольштейн Е. Г. Линейное программирование. – М.: Наука, 1969. – 424 с.
20
ПРИЛОЖЕНИЯ
Приложение 1 
КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных
задач, которые характеризуются линейной зависимостью между
переменными и линейным критерием [1, 8].
Необходимым условием постановки задачи линейного программирования являются ограничения на наличие ресурсов, величину
спроса, производственную мощность предприятия и другие производственные факторы [2].
Сущность линейного программирования состоит в нахождении
точек наибольшего или наименьшего значения некоторой функции
при определенном наборе ограничений, налагаемых на аргументы
и образующих систему ограничений, которая имеет, как правило,
бесконечное множество решений. Каждая совокупность значений переменных (аргументов функции F), которые удовлетворяют системе ограничений, называется допустимым планом задачи
линейного программирования. Функция F, максимум или минимум которой определяется, называется целевой функцией задачи.
Допустимый план, на котором достигается максимум или минимум функции F, называется оптимальным планом задачи [5, 7, 9].
Система ограничений, определяющая множество планов, диктуется условиями производства. Задачей линейного программирования (ЗЛП) является выбор из множества допустимых планов
наиболее выгодного (оптимального).
В общей постановке ЗЛП выглядит следующим образом:
Имеются какие-то переменные х = (х1, х2, … хn) и функция этих
переменных f(x) = f (х1, х2, … хn), которая носит название целевой функции. Ставится задача: найти экстремум (максимум или
минимум) целевой функции f(x) при условии, что переменные x
принадлежат некоторой области G:
ìïf (x) Þ extr
ïí
ïïx Î G
î
В зависимости от вида функции f(x) и области G и различают
разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное про21
граммирование и т. д. Линейное программирование характеризуется тем, что:
а) функция f(x) является линейной функцией переменных х1,
х2, … хn;
б) область G определяется системой линейных равенств или неравенств [7, 12].
Математическая модель любой задачи линейного программирования включает в себя [13]:
– максимум или минимум целевой функции (критерий оптимальности);
– систему ограничений в форме линейных уравнений и неравенств;
– требование неотрицательности переменных.
Пример 1
В других ситуациях могут возникать задачи с большим количеством переменных, в систему ограничений которых, кроме неравенств, могут входить и равенства. Поэтому в наиболее общей форме ЗЛП формулируют следующим образом [3, 10]:
a11x1 + a12 x2 + ... + a1n xn {£,³,=}b1,
a21x1 + a22 x2 + ... + a2n xn {£,³,=}b2 ,
.............
am1x1 + am2 x2 + ... + amn xn {£,³,=}bm .
x1 ³ 0, x2 ³ 0,..., xn ³ 0 F = c1x1 + c2 x21 + ... + cn xn ® max(min)
(4)
(5)
(6)
Коэффициенты ai,j, bi, cj, j = 1, 2, ... , n, i =1, 2, ..., m – любые действительные числа (возможно 0).
Итак, решения, удовлетворяющие системе ограничений (4) условий
задачи и требованиям неотрицательности (5), называются допустимыми, а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (6) целевой функции,– оптимальными [4].
Выше описанная ЗЛП представлена в общей форме, но одна и та
же ЗЛП может быть сформулирована в различных эквивалентных
формах. Наиболее важными формами ЗЛП являются каноническая и стандартная.
В канонической форме задача является задачей на максимум
(минимум) некоторой линейной функции F, ее система ограниче22
ний состоит только из равенств (уравнений). При этом переменные
задачи х1, х2, ..., хn являются неотрицательными:
a11x1 + a12 x2 + ... + a1n xn = b1,
a21x1 + a22 x2 + ... + a2n xn = b2 ,
...........
am1x1 + am2 x2 + ... + amn xn = bm .
x1 ³ 0, x2 ³ 0,..., xn ³ 0 F = c1x1 + c2 x21 + ... + cn xn ® max(min)
(7)
(8)
(9)
К канонической форме можно преобразовать любую задачу линейного программирования.
Правило приведения ЗЛП к каноническому виду:
1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением
в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная неотрицательная переменная со знаком «+»; в случаи неравенства «≥» – со знаком «–»
a11x1 + a12 x2 + ... + a1n xn £ b1, (10)
Вводим переменную
xn+1 = b1 - a11x1 - a12 x2 - ... - a1n xn .
Тогда неравенство (10) запишется в виде:
a11x1 + a12 x2 + ... + a1n xn + xn+1 = b1,
(11)
В каждое из неравенств вводится своя “уравнивающая” переменная, после чего система ограничений становится системой уравнений.
2. Если в исходной задаче некоторая переменная не подчинена
условию не отрицательности, то ее заменяют (в целевой функции
и во всех ограничениях) разностью неотрицательных переменных.
xχ = xχ - xl ,
где l – свободный индекс.
3. Если в ограничениях правая часть отрицательна, то следует
умножить это ограничение на (–1).
4. Наконец, если исходная задача была задачей на минимум, то
введением новой целевой функции F1 = –F мы преобразуем нашу
задачу на минимум функции F в задачу на максимум функции F1.
23
Таким образом, всякую задачу линейного программирования
можно сформулировать в канонической форме.
В стандартной форме задача линейного программирования является задачей на максимум (минимум) линейной целевой функции.
Система ограничений ее состоит из одних линейных неравенств типа «<=» или «>=». Все переменные задачи неотрицательны.
a11x1 + a12 x2 + ... + a1n xn £ b1,
a21x1 + a22 x2 + ... + a2n xn £ b2 ,
...........
am1x1 + am2 x2 + ... + amn xn £ bm .
(12)
x1 ³ 0, x2 ³ 0,..., xn ³ 0 F = c1x1 + c2 x21 + ... + cn xn ® max(min)
Всякую ЗЛП можно сформулировать в стандартной форме.
Преобразование задачи на минимум в задачу на максимум, а также
обеспечение не отрицательности переменных производится так же,
как и раньше. Всякое равенство в системе ограничений равносильно системе взаимно противоположных неравенств:
ïìïai1x1 + ai2 x2 + ... + ain xn £ bi ,
ï
ai1x1 + ai2 x2 + ... + ain xn + xn+1 = bi , Û ïí
ïï
ïïî ai1x1 - ai2 x2 - ... - ain xn £ bi
Существует и другие способы преобразования системы равенств
в систему неравенств, т. е. всякую ЗЛП можно сформулировать в стандартной форме.
24
Пример 2
Привести к каноническому виду задачу
ìïx1 - x2 ³ 1,
ïï
ïï
ïï
íx1 - 2x2 £ 1,
ïï
ïï
ïï
ïîx1 + x2 £ 3, x1 ³ 0, x2 ³ 0, F = x1 + 2x2 ® max. Введем дополнительные переменные x3, x4, x5. При этом, в первое неравенство введем неотрицательную переменную x3 со знаком
минус, а во второе и в третье – со знаком плюс переменные x4, x5 запишем задачу в виде:
ìïx1 - x2 - x3 = 1,
ïï
ïï
ïï
íx1 - 2x2 + x4 = 1,
ïï
ïï
ïï
ïîx1 + x2 + x5 = 3, xj ³ 0, j = 1,...,5.
Переведем max на min, домножив целевую функцию на (–1)
F = -x1 - 2x2 + 0x3 + 0x4 + 0x5 ® min ,
что и дает эквивалентную задачу в канонической форме.
25
Приложение 2
ШАБЛОН ОТЧЕТА ПО РАБОТЕ
ГУАП
КАФЕДРА № 43
ОТЧЕТ
ЗАЩИЩЕН С ОЦЕНКОЙ
ПРЕПОДАВАТЕЛЬ
______________________ _______________ _____________________
должность, уч. степень,
звание
подпись, дата
инициалы, фамилия
ОТЧЕТ ПО САМОСТОЯТЕЛЬНОЙ РАБОТЕ
по дисциплине:
РАБОТУ ВЫПОЛНИЛ
СТУДЕНТ ГР. ________ _____________ __________________
подпись, дата инициалы, фамилия
Санкт-Петербург
20__
26
Цель работы:
исследовать возможности табличного процессора Excel для математического моделирования и решения оптимизационных задач
на персональном компьютере.
Задание:
1. Нарисовать схему, наглядно изображающую распределение рейсов самолетов разных типов по маршрутам на планируемый период;
2. Провести описание математической модели, выбранной для
оптимизации планирования;
3. Запустить табличный процессор Excel и ввести исходные данные,
характеризующие использование самолетов на различных маршрутах;
4. Разместить в ячейках электронной таблицы изменяемые
переменные, выражение целевой функции и левых частей уравнений-ограничений;
5. Выполнить расчеты по вариантам для получения оптимального плана и рациональных планов, используя для решения задачи
линейного программирования и настройку «Поиск решения» табличного процессора Excel;
6. Сравнить полученные результаты оптимального плана и рациональных планов с первоначальным;
7. Сделать выводы по проведенному исследованию.
1. Схема распределения рейсов (нарисовать схему)
27
2. Исходные данные
(по вариантам)
Вместимость 1 типа (А1)
самолета
2 типа (А2)
Количество по 1 маршруту (B1)
пассажиров,
по 2 маршруту (B2)
перевозимых
по 3 маршруту (B3)
за сезон
для самолета 1 типа на 1 маршруте (S11)
для самолета 1 типа на 2 маршруте (S12)
Затраты
для самолета 1 типа на 3 маршруте (S13)
на различных
маршрутах для самолета 2 типа на 1 маршруте (S21)
для самолета 2 типа на 2 маршруте (S22)
для самолета 2 типа на 3 маршруте (S23)
Общие
затраты
на всех маршрутах по первоначальному плану (F1)
Заданные области ячеек электронной таблицы для построения
математической модели
Для исходных данных
Для основной части
А3:E8
А10:E24
3. Математическая модель
À1 × x11 + À2 × x21 = B1,
À1 × x12 + À2 × x22 = B2 ,
À1 × x13 + À2 × x23 = B3 .
Xij ³ 0.
(1)
(2)
F = (S11 × x11 ) + (S21 × x21 ) + (S12 × x12 ) +
+(S22 × x22 ) + (S13 × x13 ) + (S23 × x23 ).
(3)
4. Разработка электронной таблицы
Размещение исходных данных в ячейках электронной таблицы
(область ячеек для исходных данных – __________)
Адреса ячеек, отведенные для исходных данных
(вписать соответствующие значения и адреса ячеек для исходных данных)
28
Обозначения
Заданные
значения
Адреса ячеек
Размещение основной части электронной таблицы – изменяемых
переменных, целевой функции, левых частей уравнений-ограничений
(область ячеек для основной части – _____________)
Адреса ячеек, отведенные для изменяемых переменных
(вписать соответствующие адреса ячеек для изменяемых переменных)
Изменяемые переменные
Адреса ячеек
Адреса ячеек, отведенных для выражений, из которых состоит
целевая функция
(вписать недостающие выражения и соответствующие адреса ячеек)
Выражения
Адреса ячеек
Выражения
Адреса ячеек
Адреса ячеек, отведенные для выражений левой части уравнений-ограничений
(вписать недостающие выражения и соответствующие адреса ячеек)
Выражения
Адреса ячеек
Выражения
Адреса ячеек
5. Поиск решения
Инструкция для решения задачи линейного программирования
с использованием надстройки «Поиск решения»
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
Вид диалогового окна надстройки «Поиск решения» при вводе
ограничения
29
30
6. Результаты моделирования
Инструкция для формирования сводной таблицы
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
Сводная таблица, содержащая варианты планов
Первоначальный Оптимальный
план
план
k
Рациональные планы
(процентное распределение рейсов)
20%
40%
60%
80%
1/
2/
3/
4/
4
3
2
1
x11
x12
x13
x21
x22
x23
F
31
Графики общих затрат для рассчитанных вариантов планов
20%
40%
60%
80%
7. Выводы:
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
_______________________________________________________
32
Приложение 3 
ВАРИАНТЫ ЗАДАНИЙ ДЛЯ РАБОТЫ
Вариант исходных данных выбирается из табл. 7. Для всех вариантов количество маршрутов n = 3, используемых типов самолетов
m = 2. Вместимость самолета i-го типа равна Аi человек, количество
пассажиров, перевозимых по j-му маршруту за сезон, составляет Bj
человек. Затраты, связанные с использованием самолета i-го типа
на j-м маршруте, составляют Sij. Заданные в каждом варианте общие затраты F1 – это затраты по первоначальному плану.
План {Sij} определяет, сколько рейсов самолетов данного типа и
на каком из маршрутов следует запланировать, чтобы удовлетворить потребности в перевозках. Первоначальный план разработан
по справедливому, но недешевому принципу равного распределения рейсов на каждом маршруте. Расчеты должны позволить провести выбор между оптимальным, рациональными и первоначальным планами.
Таблица 7
Варианты 1–10
1
2
3
4
5
6
7
8
9
10
А1
17
32
48
12
17
15
76
48
32
120
А2
32
48
12
17
15
19
32
15
12
76
B1
3500
4000
4500
5000
5500
6000
6500
7000
7500
8000
B2
1000
1250
1500
1750
2000
2250
2500
2750
3000
3250
B3
2000
2300
2600
2900
3200
3500
3800
4100
4400
4700
S11
138
328
398
126
145
161
661
528
285
1350
S12
274
648
782
246
281
311
1269
1008
541
2550
S13
410
968
1166
366
417
461
1877
1488
797
3750
S21
324
394
125
143
159
163
348
132
134
684
S22
644
778
245
279
309
315
668
252
254
1292
S23
964
1162
365
415
459
467
988
372
374
1900
F1
107816 119618 131243 156160 176725 194132 206370 249381 242725 282212
33
Продолжение таблицы 7
Варианты 11–20
11
12
13
14
15
16
17
18
19
20
А1
76
164
12
12
15
17
18
19
20
26
А2
48
120
15
18
20
26
27
32
34
36
B1
8500
9000
6000
9200
8800
8400
7600
7200
6800
6400
B2
3500
3750
3900
4300
4700
5100
5900
6300
7100
7900
B3
5000
5300
5400
5700
5500
6100
3700
3600
6200
4600
S11
616
1681
100
126
128
183
157
209
178
293
S12
1224
3321
196
246
248
353
301
399
338
553
S13
1832
4961
292
366
368
523
445
589
498
813
S21
486
984
156
151
213
224
294
282
378
324
S22
966
1944
306
295
413
432
564
538
718
612
S23
1446
2904
456
439
613
640
834
794
1058
900
F1
269532 300751 279000 315440 328657 337595 294742 282688 387511 339228
Варианты 21–30
21
22
23
24
25
26
27
28
29
30
А1
27
32
34
36
39
42
48
50
76
96
А2
39
42
48
49
50
52
60
76
80
100
B1
5600
5200
4800
4400
3600
3200
2800
2400
1800
1400
B2
8200
8600
8300
9200
8400
9600
8500
9800
8800
9900
B3
3950
4150
4300
4450
4600
4900
5350
5600
5700
5900
S11
219
328
282
378
332
452
418
550
676
1080
S12
435
648
554
738
644
872
802
1050
1284
2040
S13
651
968
826
1098
956
1292
1186
1550
1892
3000
S21
395
344
498
412
531
447
653
669
890
900
S22
785
680
978
804
1031
863
1253
1277
1690
1700
S23
1175
1016
1458
1196
1531
1279
1853
1885
2490
2500
F1
34
312956 312822 320498 327891 321539 378305 340046 356875 345945 368612
Приложение 4 
РАБОТА С НАДСТРОЙКОЙ «ПОИСК РЕШЕНИЯ»  
В ПАКЕТЕ EXCEL
Мощным средством анализа данных Excel является надстройка Solver (Поиск решения). С ее помощью можно определить, при
каких значениях указанных влияющих ячеек формула в целевой
ячейке принимает нужное значение (минимальное, максимальное
или равное какой-либо величине). Для процедуры поиска решения
можно задать ограничения, причем не обязательно, чтобы при этом
использовались те же влияющие ячейки. Для расчета заданного
значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения
переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.
Программа «Поиск решений» (в оригинале Excel Solver) – дополнительная надстройка табличного процессора MS Excel, которая предназначена для решения определенных систем уравнений, линейных
и нелинейных задач оптимизации, используется с 1991 года.
Размер задачи, которую можно решить с помощью базовой версии этой программы, ограничивается такими предельными показателями:
– количество неизвестных (decision variable) – 200;
– количество формульных ограничений (explicit constraint) на
неизвестные – 100;
– количество предельных условий (simple constraint) на неизвестные – 400.
Разработчик программы Solver компания Frontline System уже
давно специализируется на разработке мощных и удобных способов
оптимизации, встроенных в среду популярных табличных процессоров разнообразных фирм-производителей (MS Excel Solver, Adobe
Quattro Pro, Lotus 1–2–3). Высокая эффективность их применения
объясняется интеграцией программы оптимизации и табличного бизнес-документа. Благодаря мировой популярности табличного процессора MS Excel, встроенная в его среду программа Solver, является
наиболее распространенным инструментом для поиска оптимальных решений в сфере современного бизнеса. По умолчанию в Excel
надстройка Поиск решения отключена. Чтобы активизировать ее
в Excel 2007, щелкните значок «Кнопка Microsoft Office», щелкните «Параметры Excel», а затем выберите категорию «Надстройки».
Появится диалоговое окно «Надстройки» рис. 9.
35
Рис. 9. Диалоговое окно «Надстройки»
В поле «Управление» выберите значение «Надстройки Excel» и
нажмите кнопку «Перейти». В поле «Доступные надстройки» установите флажок рядом с пунктом «Поиск решения» и нажмите
кнопку «ОК».
В Excel 2003 и ниже выберите команду «Сервис/Надстройки»,
в появившемся диалоговом окне Надстройки установите флажок «Поиск решения» и щелкните на кнопке «ОК». Если вслед за
этим на экране появится диалоговое окно с предложением подтвердить ваши намерения, щелкните на кнопке «Да». (Возможно, вам
понадобится установочный компакт-диск Office).
Процедура поиска решения 1. Создайте таблицу с формулами, которые устанавливают связи
между ячейками.
2. Выделите целевую ячейку, которая должна принять необходимое значение, и выберите команду:
– в Excel 2007 «Данные/Анализ/Поиск решения»;
– в Excel 2003 и ниже Tools /Solver (Сервис / Поиск решения).
Поле Set Target Cell (Установить целевую ячейку) открывшегося диалогового окна надстройки Solver (Поиск решения) будет содержать адрес целевой ячейки.
3. Установите переключатели Equal To (Равной), задающие значение целевой ячейки,– Мах (максимальному значению), Min (ми36
нимальному значению) или Value of (значению). В последнем случае введите значение в поле справа.
4. Укажите в поле By Changing Cells (Изменяя ячейки), в каких
ячейках программа должна изменять значения в поисках оптимального результата.
5. Создайте ограничения в списке Subject to the Constraints
(Ограничения). Для этого щелкните на кнопке Add (Добавить) и
в диалоговом окне Add Constraint (Добавление ограничения) определите ограничение.
6. Щелкните на кнопке в кнопке Options (Параметры) и в появившемся окне установите переключатель Неотрицательные значения
(если переменные должны быть позитивными числами), Линейная
модель (если задача, которую вы решаете, относится к линейным моделям).
7. Щелкнув на кнопке Solver (Выполнить), запустите процесс
поиска решения (Рис. 4).
8. Когда появится диалоговое окно Solver Results (Результаты
поиска решения), выберите переключатель Keep Solve Solution
(Сохранить найденное решение) или Restore Original Values
(Восстановить исходные значения).
9. Щелкните на кнопке «ОК».
Параметры средства «Поиск решения» «Максимальное время» – служит для ограничения времени, отпущенного на поиск
решения задачи. В этом поле можно ввести время в секундах, не
превышающее 32 767 (примерно девять часов); значение 100, ис-
Рис. 10. Диалоговое окно «параметры поиска решения»
37
пользуемое по умолчанию, вполне приемлемо для решения большинства простых задач (Рис. 10).
Как видно из рис. 10 «Предельное число итераций» – управляет
временем решения задачи путем ограничения числа вычислительных циклов (итераций).
«Относительная погрешность» – определяет точность вычислений. Чем меньше значение этого параметра, тем выше точность вычислений.
«Допустимое отклонение» – предназначено для задания допуска на отклонение от оптимального решения, если множество значений влияющей ячейки ограничено множеством целых чисел.
Чем больше значение допуска, тем меньше времени требуется на
поиск решения.
«Сходимость» – применяется только к нелинейным задачам.
Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в поле Сходимость, поиск прекращается.
«Линейная модель» – служит для ускорения поиска решения путем применения к задаче оптимизации линейной модели.
Нелинейные модели предполагают использование нелинейных
функций, фактора роста и экспоненциального сглаживания, что
замедляет вычисления.
«Неотрицательные значения» – позволяет установить нулевую
нижнюю границу для тех влияющих ячеек, для которых не было
задано соответствующее ограничение в диалоговом окне «Добавить
ограничение».
«Автоматическое масштабирование» – используется, когда числа
в изменяемых ячейках и в целевой ячейке существенно различаются.
«Показывать результаты итераций» – приостанавливает поиск
решения для просмотра результатов отдельных итераций.
«Загрузить модель» – после щелчка на этой кнопке открывается
одноименное диалоговое окно, в котором можно ввести ссылку на
диапазон ячеек, содержащих модель оптимизации.
«Сохранить модель» – служит для отображения на экране одноименного диалогового окна, в котором можно ввести ссылку на диапазон ячеек, предназначенный для хранения модели оптимизации.
Подкаталог «Оценки»:
«линейная» – выберите этот переключатель для работы с линейной моделью;
«квадратичная» – выберите этот переключатель для работы
с нелинейной моделью.
38
Подкаталог «Разности»:
«прямые» – используется в большинстве задач, где скорость изменения ограничений относительно невысока. Увеличивает скорость работы средства «Поиск решения»;
«центральные» – используется для функций, имеющих разрывную производную. Данный способ требует больше вычислений,
однако его применение может быть оправданным, если выдано сообщение о том, что получить более точное решение не удается.
Подкаталог «Метод поиска»:
«Ньютона» – требует больше памяти, но выполняет меньше итераций, чем в методе сопряженных градиентов.
«сопряженных градиентов» – реализует метод сопряженных
градиентов, для которого требуется меньше памяти, но выполняется больше итераций, чем в методе Ньютона. Данный метод следует
использовать, если задача достаточно большая и необходимо экономить память, или, если итерации дают слишком малое отличие
в последовательных приближениях.
39
СОДЕРЖАНИЕ
Предисловие.........................................................................
1. РЕШЕНИЕ ЗАДАЧ ОПТИМИЗАЦИИ НА ЭВМ......................
2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ...................................
3. ОПИСАНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ.........................
4. МАТЕМАТИЧЕСКАЯ МОДЕЛЬ
В ЭЛЕКТРОННОЙ ТАБЛИЦЕ.................................................
4.1. Размещение исходных данных........................................
4.2. Размещение целевой функции........................................
4.3. Технология создания электронной таблицы......................
5. РЕШЕНИЕ И ОБРАБОТКА
РЕЗУЛЬТАТОВ МОДЕЛИРОВАНИЯ И ОПТИМИЗАЦИИ...........
6. СОДЕРЖАНИЕ ОТЧЕТА О ВЫПОЛНЕНИИ РАБОТЫ............
Заключение..........................................................................
Список литературы................................................................
ПРИЛОЖЕНИЯ....................................................................
Приложение 1
КРАТКИЕ СВЕДЕНИЯ ИЗ ТЕОРИИ......................................
Приложение 2
ШАБЛОН ОТЧЕТА ПО РАБОТЕ...........................................
Приложение 3
ВАРИАНТЫ ЗАДАНИЙ ДЛЯ РАБОТЫ.................................
Приложение 4
РАБОТА С НАДСТРОЙКОЙ «ПОИСК РЕШЕНИЯ»
В ПАКЕТЕ EXCEL..............................................................
3
4
5
6
7
7
8
10
15
18
19
20
21
21
26
33
35
Документ
Категория
Без категории
Просмотров
1
Размер файла
1 198 Кб
Теги
0a9a54a1db, gamow
1/--страниц
Пожаловаться на содержимое документа