Кутузов А.Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Excel
Подождите немного. Документ загружается.
Для решения нашей задачи воспользуемся программой решения задач о
назначениях и о коммивояжере, входящей в пакеты QSB+ и QS. Для ее запуска
выберите в меню программ п. 6, если работаете в QSB+, или п. 7 при работе в QS.
Откроется меню функций, аналогичное тому, которое используется при решении
задач линейного программирования (см. раздел 2.4.2).
Задание параметров поиска решения
В меню функций выберите п. 2 (ввод новой задачи). В ответ на запрос программы,
введите название решаемой задачи, например
Assignment
.
На следующей странице в угловых скобках (в порядке сверху вниз) задаются
параметры поиска решения:
На этой странице необходимо задать следующие параметры:
максимизировать (
1
) или минимизировать (
2
) целевую функцию;
какая задача решается: о назначениях (
1
) или о коммивояжере (
2
);
количество исполнителей в задаче о назначениях (или городов в задаче о
коммивояжере);
количество работ (задается только в задаче о назначениях);
использовать стандартные названия исполнителей O1…On, работ T1…Tn и
городов C1…Cn (
y
) или задавать другие имена (
n
).
Ввод числовых данных
Перед началом ввода числовых данных вам придется ответить на вопрос программы,
в каком формате вы предпочитаете вводить время выполнения работ (или другие
показатели их эффективности): в свободном (
y
) или фиксированном (
n
).
Выбирая свободный формат, имейте в виду, что он подобен записи на чистом листе
бумаги и более трудоемок.
В том случае, если выбран фиксированный формат, данные (ввод времени или
других показателей эффективности выполнения работ) нужно вводить следующим
образом:
Ст
р
. 91 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
СОВЕТ
Если по условию задачи какая-либо работа не может быть выполнена каким-то исполнителем, то в
качестве времени ее выполнения введите или большое число, значительно превышающее время
выполнения остальных работ, или латинскую букву
M.
Если работы характеризуются эффективностью и решается задача на максимум, то для недопустимых
работ введите очень большое по абсолютной величине отрицательное число или просто
–M
.
После ввода данных вы вернетесь в меню функций (см. раздел 2.4.2).
Чтобы проверить правильность заданной информации, выберите в меню функций
п. 4 (просмотр данных задачи) и затем в открывшемся меню просмотра данных —
п. 1.
Если данные нужно исправить, выберите в меню функций п. 7 (изменение задачи) и
затем в открывшемся меню изменения задачи — п. 1 (
д
ля изменения времени или
других используемых показателей эффективности выполнения работ). При этом
программа предложит ввести название для новой, измененной задачи.
Д
ля
сохранения задачи на диске выберите в меню функций п. 6 (сохранение задачи на
диске).
Нахождение решения
Чтобы решить задачу, выберите в меню функций п. 5 (решение задачи). Появится
меню решения, которое выглядит следующим образом:
В этом меню можно выбрать следующие варианты действий:
1.
Решение без вывода каких-либо таблиц (в задачах о назначениях и о
коммивояжере).
2.
Решение с выводом всех таблиц (в задаче о назначениях).
3.
Решение с выводом первой таблицы (в задаче о назначениях).
4.
Решение с выводом последней таблицы (в задаче о назначениях).
5.
Решение с выводом каждого шага метода ветвей и границ (в задаче о
коммивояжере).
6.
Решение эвристическим методом (в задаче о коммивояжере).
Ст
р
. 92 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
7.
Возврат в меню функций.
ВНИМАНИЕ
Вывод таблиц возможен только в задаче о назначениях, имеющей не более 9 исполнителей и 9 работ.
Если выбрано решение с выдачей промежуточных таблиц, то процесс можно в любой
момент прервать, нажав клавишу F9.
Для решения нашего примера выберем п. 1 (решение без вывода каких-либо таблиц).
Внизу меню решения появится сообщение программы о том, что решение найдено:
The optimal solution has been found.
На следующей странице вы увидите меню результатов, аналогичное тому, которое
используется при целочисленном решении задачи линейного программирования.
Выбрав в нем п. 1, вы получите таблицу с результатами решения, которая выглядит
следующим образом:
В этой таблице выводятся:
в столбцах Object и Task — названия исполнителей и выполняемых ими работ;
в столбце Cost/Prof — время выполнения отдельных работ (или другие показатели
их эффективности);
в последней строке таблицы — общие затраты времени (Minimum OBJ = 20) или
другой суммарный показатель эффективности выполнения работ, число итераций
и время работы процессора.
После просмотра результатов вы вернетесь в меню функций, где можно:
изменить условия текущей задачи, выбрав п. 7 (изменение задачи);
ввести новую задачу, выбрав п. 2 (ввод новой задачи);
выйти из программы или пакета, выбрав, соответственно, п. 9 (выход в меню
программ) или п. 10 (выход из QSB+ (или QS)).
Частные случаи решения задачи о назначениях с помощью QSB+ и QS
При решении задачи о назначениях с помощью программы Excel могут встретиться
следующие частные случаи:
максимизация целевой функции,
несовпадение количества работ и исполнителей,
недопустимость каких-либо назначений.
В этих случаях задача решается так же, как и аналогичная транспортная (см
. раздел
3.3.1). В частности, когда количества работ и исполнителей не совпадают, программа
автоматически добавит необходимое количество фиктивных исполнителей или
работ.
Самостоятельная работа
1.
Воспроизведите на своем компьютере с помощью пакета прикладных программ
Ст
р
. 93 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
QSB+ всю последовательность решения примера, рассмотренного выше (см. раздел
4.2.1).
2.
Изменим несколько условие задачи о подростках (см. раздел 4.1.1). В летних
работах принимают участие четыре подростка и имеется четыре вида работ.
Решите задачу с помощью QSB+. Стоимости назначений указаны в следующей
таблице.
4.2.2. Решение задачи о назначениях с помощью программы Excel
Как вы уже знаете, программ Excel позволяет получить решение любой задачи
линейного программирования, и в частности, задачи о назначениях, в более
наглядном и удобном для демонстрации виде.
Ввод данных
Решение задачи, сформулированной в разделе 4.1, представлено на следующем
рисунке.
Работа 1 Работа 2 Работа 3 Работа 4
Джон
$1 $4 $6 $3
Том
$9 $7 $10 $9
Билл
$4 $5 $11 $7
Робин
$8 $7 $8 $5
Ст
р
. 94 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Задачу о назначениях можно рассматривать как частный случай транспортной
задачи, в которой запасы в пунктах отправления и потребности в пунктах назначения
равны 1. Поэтому модель оформляется так же, как для транспортной задачи, в виде
трех таблиц (см. раздел 3.3.2). Затраты времени на выполнение работ (или другие
показатели их эффективности) вводятся в первую из них, а во вторую (в ячейки
H10:H13 и C15:F15) — вводятся единицы вместе со знаками неравенства, в формате,
который использовался для ввода запасов и потребностей транспортной задачи.
СОВЕТ
Вместо знаков равенства в ограничениях модели, сформулированной в разделе 4.1, лучше
использовать знаки неравенства, даже когда задача сбалансирована (количества исполнителей и работ
совпадают). Знаки неравенства показывают, что на каждую работу назначения должно быть назначено
не менее одного исполнителя (знак >=), а каждый исполнитель может быть назначен не более чем на
одну работу (знак <=).
Использование знаков неравенства делает формулировку задачи более общей,
поскольку точно так же формулируется и несбалансированная задача, когда количество исполнителей
превышает количество работ.
Формулы и ячейки, в которые их следует ввести, указаны в таблице.
Ячейка Форм
у
ла Копировать в
C18 =C4*C10 C18:F21
Ст
р
. 95 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Использование средства поиска решений описано в разделе 1.3. Здесь же напомним
лишь основные моменты.
В окне Поиск решения задается следующая информация.
Необходимо также установить два параметра в диалоговом окне Параметры поиска
решения
.
Анализ результатов
Обратимся еще раз к рабочему листу решения задачи о назначениях с помощью
Excel, который был впервые представлен в предыдущем разделе:
G10 =СУММ(C10:F10) G11:G13; G18:G22
C14 =СУММ(C10:C13) D14:F14; C22:F22
Ст
р
. 96 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Оптимальное решение отображается во второй таблице в жирной рамке, где 1
означает, что исполнитель назначается на выполнение работы, а 0 — не
назначается. Поскольку данная задача является частным случаем транспортной, в
которой запасы и потребности равны 1 (целые числа), то и решение обязательно
будет целым — 0 или 1. В третьей таблице вычисляются затраты времени (или
другие используемые показатели эффективности) по отдельным исполнителям и
работам, а в ячейке G19 — целевая функция.
Частные случаи решения задачи о назначениях с помощью Excel
При решении задачи о назначениях с помощью программы Excel могут встретиться
следующие частные случаи:
максимизация целевой функции,
несовпадение количества работ и исполнителей,
недопустимость каких-либо назначений.
В этих случаях задача решается так же, как и аналогичная транспортная (см. раздел
3.3.2). В частности, когда работ больше, чем исполнителей, можно либо изменить
знаки неравенства в ограничениях задачи, либо добавить фиктивных исполнителей.
Ст
р
. 97 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Самостоятельная работа
1.
Воспроизведите на своем компьютере решение примера с помощью программы
Excel, рассмотренное в начале данного раздела.
1.
Решите следующую задачу. Нужно распределить четырех рабочих по четырем
видам работ. Ввиду различия в квалификации рабочих стоимость выполнения ими
работ различна (она приведена в таблице). При этом первый рабочий не может
выполнять 3-ю работу, а третий — 4-ю. Решите задачу с помощью программы
Excel.
2.
Предположим, что в задаче из упражнения 2 можно ввести нового (пятого)
рабочего, способного выполнить любой вид работ со стоимостью, соответственно,
$60, $45, $30 и $80. Встает вопрос — будет ли экономически выгодным заменить
одного из старых рабочих новым? Найдите ответ с помощью программы Excel.
3.
Пусть в задаче из упражнения 2 необходимо ввести новый вид работы, который
может выполнить любой из четырех рабочих со стоимостью, соответственно, $20,
$10, $20 и $80. Будет ли новая работа более выгодной по сравнению с уже
имеющимися видами работ? Ответ найдите с помощью программы Excel.
Список литературы
1.
Chang Y.-L., Sullivan R. S. QSB+: Quantitative Systems for Business Plus: Version 2.1.
— Prentice Hall, 1996.
2.
Chang Y.-L., Sullivan R. S. QS: Quant System: Version 2.1. — Prentice Hall, 1996.
3.
Moore J. H., Weatherford L. R. Decision Modeling with Microsoft Excel. — Prentice Hall,
2001.
4.
Render B., Stair R. M., Jr. Quantitative Analysis for Management. — Prentice Hall, 2000.
5.
Taylor B. W. Introduction to Management Science. — Prentice Hall, 1999.
6.
Weiss H. J. DS for Windows. — Prentice Hall, 2000.
7.
Акулич И. Л. Математическое программирование в примерах и задачах: Учебное
пособие. — М.: Высшая школа, 1993.
8.
Вентцель Е. С. Исследование операций. Задачи, принципы, методология: Учебное
пособие. — М.: Высшая школа, 2001.
9.
Гарнаев А. Ю. Excel, VBA, Internet в экономике и финансах. — Спб.: БХВ —
Петербург, 2002.
10.
Глухов В. В., Медников М. Д., Коробко С. Б. Математические методы и модели для
менеджмента: Учебник. — Спб.: Лань, 2000.
11.
Друри К. Введение в управленческий и производственный учет. — М.: Аудит,
ЮНИТИ, 1998.
12.
Исследование операций: В 2-х томах / Под ред. Дж. Моудера, С. Элмаграби; Пер.
с англ. — М.: Мир, 1981.
13.
Кузин Б. И., Юрьев В. Н., Шахдинаров Г. М. Методы и модели управления фирмой:
Работа 1 Работа 2 Работа 3 Работа 4
Рабочий 1
$50 $50 — $20
Рабочий 2
$70 $40 $20 $30
Рабочий 3
$90 $30 $50 —
Рабочий 4
$70 $20 $60 $70
Ст
р
. 98 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Учебник. — Спб.: Питер, 2001.
14.
Кузнецов Ю. Н., Кузубов В. И., Волощенко А. Б. Математическое
программирование: Учебное пособие. — М.: Высшая школа, 1980.
15.
Курицкий Б. Я. Поиск оптимальных решений средствами Excel 7.0. — Спб.: BHV —
Санкт-Петербург, 1997.
16.
Кутузов А. Л. Математические методы в экономике и менеджменте: Практикум по
использованию пакетов прикладных программ QSB+, QS и программы Excel. —
Спб.: Изд-во СпбГТУ, 2001.
17.
Липсиц И. В. Коммерческое ценообразование: Учебник. Сборник деловых
ситуаций. Тесты. — М.: БЕК, 2001.
18.
Саати Т. Л. Математические модели конфликтных ситуаций / Пер. с англ. — М.
Советское радио, 1977.
19.
Таха Х. А. Введение в исследование операций / Пер. с англ. — М.: Вильямс, 2001.
20.
Шеннон Р. Имитационное моделирование систем — искусство и наука / Пер. с
англ. — М.: Мир, 1978.
Приложение. Установка программ и
правила работы с ними
Установка средства поиска решения в Excel
Программа Excel (версии 5.0 и выше) включает средство поиска решения,
позволяющее решать любые задачи математического программирования. Это
программа-надстройка, которая должна быть установлена при инсталляции
программы Excel на вашем компьютере. Чтобы убедиться в этом, раскройте меню
Сервис
— там должна быть команда
Поиск решения
. Если ее нет, выберите в меню
Сервис команду Надстройки и в раскрывшемся списке установите флажок рядом с
названием надстройки
Поиск решения
— соответствующая команда появится в меню
Сервис. Если же в списке такой надстройки нет, ее нужно установить.
Для установки надстройки Поиск решения вам понадобится компакт-диск с пакетом
Microsoft Office, с которого ранее устанавливались ваши офисные программы, в
частности Excel. Установка выполняется в следующей последовательности:
1.
Щелкните на кнопке Пуск и выберите пункт Настройка, затем — Панель управления.
2.
В окне Панель управления щелкните на значке Установка и удаление программ.
3.
В окне Установка и удаление программ на вкладке Установка/удаление выберите в списке
пункт с названием вашей версии Microsoft Office и щелкните на кнопке
Добавить/удалить
.
4.
В окне программы установки выберите параметр Добавить или удалить компоненты —
изменить набор установленных компонентов
и щелкните на кнопке
Далее
.
5.
В следующем окне щелкните на знаке плюс (+) сначала рядом с названием Microsoft
Excel для Widows
, а затем рядом с названием Надстройки.
6.
Щелкните на значке Поиск решения, а затем — на значке Запускать с моего компьютера
из появившегося списка.
7.
Щелкните на кнопке Обновить. В ходе установки понадобится вставить компакт-
д
ис
к
с Microsoft Office.
Ст
р
. 99 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Установка и запуск пакетов QSB+ и QS
Пакеты QSB+ и QS содержат MS-DOS-программы и могут быть установлены путем
простого копирования файлов в любую папку.
Работа с пакетом QSB+ начинается с запуска программы QSB, а с пакетом QS — с
запуска программы QS. Перед запуском любой из этих программ рекомендуется ее
предварительно настроить, для чего щелкните значок программы (или ее ярлык)
правой кнопкой мыши и выберите команду
Свойства
. В открывшемся окне свойств
выберите параметры настройки, перечисленные в следующей таблице:
Общие правила работы с пакетами QSB+ и QS
Работа с пакетами QSB+ и QS в основном сводится к выбору пунктов меню и к вводу
данных. Поскольку пакеты не русифицированы, в данном пособии даются переводы
основных меню и сообщений, появляющихся на экране. Для тех пользователей, у
которых имеется любая программа автоматического перевода [5], существует еще
одна возможность — машинный перевод текста. Для этого необходимо, чтобы пакеты
работали в оконном режиме (см. настройки в предыдущем разделе), а переводимый
текст был скопирован в буфер обмена.
Пункты меню удобнее всего выбирать нажатием соответствующей цифры или буквы.
Можно также подвести курсор к нужному пункту меню с помощью клавиш управления
курсором и нажать клавишу Enter.
При наборе на клавиатуре буквенных данных всегда вводятся латинские буквы
независимо от выбранной раскладки клавиатуры.
После ввода любого числа или знака нажимайте клавишу Enter, чтобы перейти на
следующую позицию ввода. Для возврата на предыдущие позиции используйте
клавиши управления курсором и Back Space.
При вводе данных в фиксированном формате программа отображает знаки
неравенств в виде специальных символов. Маленький символ
∈
означает «меньше
или равно», большой символ
∈
— «больше или равно». Когда курсор попадает на
один из этих символов, нужно:
либо просто нажать клавишу Enter, если знак следует сохранить;
либо набрать вместо него
>
,
>=
,
<
,
<=
или
=
, если знак нужно изменить (на зна
к
отводится две позиции, поэтому после набора знака
>
,
<
или
=
нажмите клавишу
пробела).
После окончания ввода или просмотра данных на очередной странице программы
всегда нажимайте клавишу Page Down
д
ля перехода на следующую страницу или
возврата в меню. В тех случаях, когда программа после нажатия Page Down выдала в
нижней строке экрана какое-либо сообщение, нажмите эту клавишу еще раз.
Если данные занимают несколько страниц (например,
д
ля задач с большим
количеством переменных или ограничений),
д
ля возврата на предыдущие страницы
используйте клавишу
Page Up
.
Полезные клавиши:
F8
— печать содержимого текущей страницы на принтере;
Вкладка Па
р
амет
р
ы
Программа
Закрывать окно по завершении сеанса
работы
Шрифт
Только растровые, 10
×
18
Экран
Оконный
Ст
р
. 100 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm