Кутузов А.Л. Математические методы и модели исследования операций. Линейная оптимизация с помощью WinQSB и Excel
Подождите немного. Документ загружается.
функции и ограничениях), знаки и правые части ограничений:
Если выбран фиксированный формат задания граничных условий, следующая
страница предназначена для ввода граничных условий:
Для каждой переменной можно задать в угловых скобках нижнюю границу (вместо
исходного числа
+0
) и верхнюю границу (вместо исходного числа
+1.0E+20
,
означающего 10
+20
). При этом старую информацию в угловых скобках стирайте
клавишей пробела или Delete. Буквы в угловых скобках (
<C>
) в данной программе
менять нельзя: они лишь указывают, что переменные нецелочисленны (continuous).
После ввода данных вы вернетесь в меню функций. Чтобы проверить правильность
заданной информации, выберите в меню функций п. 4 (просмотр данных задачи) и
затем в открывшемся меню просмотра данных — п. 1 (описание программы
линейного программирования).
Если данные нужно исправить, выберите в меню функций п. 7 (изменение задачи) и
затем в открывшемся меню изменения задачи — п. 1 (
д
ля изменения коэффициентов
задачи) или п. 8 (для изменения граничных условий). При этом программа сначала
предложит ввести название для новой, измененной задачи. Если хотите, введите
новое имя задачи или повторите старое. Затем внесите необходимые исправления в
данные.
Для сохранения задачи на диске выберите в меню функций п. 6. (сохранение задачи
на диске), Воспользовавшись этим пунктом, сохраните наш пример для дальнейшего
использования.
Нахождение решения
Чтобы решить задачу, выберите в меню функций п. 5 (решение задачи). Появится
меню решения:
Ст
р
. 41 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
В этом меню можно выбрать следующие варианты действий:
1.
Решение без вывода симплекс-таблиц.
2.
Решение с выводом первой симплекс-таблицы.
3.
Решение с выводом последней симплекс-таблицы.
4.
Решение с выводом первой и последней симплекс-таблиц.
5.
Решение с выводом всех симплекс-таблиц.
6.
Решение графическим методом (только для задач с двумя переменными).
7.
Отмена автоматической нормализации выходных данных.
8.
Возврат в меню функций.
Отметим, что вывод таблиц возможен только для задач, в которых выполняется
условие: (N + N
1
+ N
2
+ 2N
3
)
<
10, где:
N — количество переменных,
N
1
— количество ограничений «меньше или равно»,
N
2
— количество ограничений «равно»,
N
3
— количество ограничений «больше или равно».
Если выбран вариант решения с выдачей промежуточных таблиц, то процесс можно
в любой момент прервать, нажав клавишу F9.
Для решения нашего примера выберем п. 1 (решение без вывода симплекс-таблиц).
Внизу экрана появится сообщение о том, что решение найдено:
The optimal solution
has been found.
На следующей странице вы увидите меню результатов, которое можно впоследствии
вызывать и из меню функций, выбрав в нем п. 8 (просмотр результатов решения).
Ст
р
. 42 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
В этом меню можно выбрать:
1.
Вывод итогового отчета.
2.
Печать итогового отчета.
3.
Вывод решения.
4.
Печать решения.
5.
Вывод решения с анализом устойчивости.
6.
Печать решения с анализом устойчивости.
7.
Печать последней симплекс-таблицы.
8.
Сохранение решения в ASCII-файле.
9.
Возврат в меню функций.
Наиболее полный и удобный вид отображения результата — итоговый отчет.
Поэтому в нашем примере выберем п. 1 (вывод итогового отчета).
Анализ результатов
Первая страница итогового отчета выглядит следующим образом:
На этой странице выводится следующая информация:
В столбцах Number и Variable — номера и имена переменных, соответственно.
В столбце Solution — найденное оптимальное решение (в данном случае —
5; 1,5; 3; 4).
В столбце Opportunity Cost — двойственные оценки (40; 0; 80; 80). Такая оценка
может быть отлична от нуля в двух случаях:
д
ля нулевой переменной и для
переменной, равной своему граничному значению.
Для нулевой переменной эта оценка показывает, во-первых, на какую величину в
целевой функции следует изменить коэффициент переменной, чтобы в
оптимальном плане она приняла положительное значение (например, насколько
Ст
р
. 43 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
увеличить цену изделия, чтобы его производить стало выгодно), во-вторых, на какую
величину ухудшится значение целевой функции, если уйти от оптимального
плана, добавив в него единицу соответствующей продукции.
Для переменной, равной своему граничному значению, эта оценка показывает, на
какую величину изменится целевая функция, если увеличить соответствующее
граничное значение на единицу.
В столбце Objective Coefficient — коэффициенты целевой функции.
В столбцах Minimum Obj. Coeff. и Maximum Obj. Coeff. — границы интервалов
оптимальности, то есть пределы изменения коэффициентов целевой функции,
при которых сохраняется прежнее оптимальное решение (при этом Infinity означает
∞
).
В последней строке таблицы — значение целевой функции (Maximized OBJ = 1330),
число итераций и время работы процессора.
Если в решаемой задаче переменные ограничены сверху (как в нашем примере),
границы некоторых интервалов оптимальности могут быть указаны с неверными
знаками (при этом коэффициенты целевой функции оказываются вне своих
интервалов оптимальности). Знаки обеих границ таких интервалов нужно просто
изменить на противоположные (не обращайте внимания, что это войдет в
противоречие с заголовками столбцов Minimum и Maximum).
В нашем примере необходимо изменить знаки границ интервалов оптимальности для
цен 1, 3 и 4-го видов продукции. Тогда интервалами оптимальности будут:
для цены 1-го вида продукции — [30, +
∞
),
для цены 2-го вида продукции — [0, 140],
для цены 3-го вида продукции — [30, +
∞
),
для цены 4-го вида продукции — [60, +
∞
).
Вторая страница итогового отчета содержит подробные сведения об ограничениях
задачи, Она выглядит следующим образом:
На этой странице выводится следующая информация:
В столбце Conctr. — номера ограничений.
В столбце Status — их состояние:
Tight
(связанное), если ограничение при подстановке оптимального решения
обращается в равенство (ресурс используется полностью, дефицитен);
Loose
(не связанное), если ограничение обращается в строгое неравенство
(ресурс не используется полностью, недефицитен).
В столбце RHS — правые части ограничений (запасы ресурсов).
В столбце Shadow Price — теневые цены — двойственные оценки, показывающие,
на какую величину изменится целевая функция при увеличении на единицу
Ст
р
. 44 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
правой части ограничения, тогда как остальные данные неизменны (в частности при
добавлении единицы соответствующего ресурса).
ПРИМЕЧАНИЕ
Теневая цена — это максимальная цена, которую стоит платить за дополнительное количество
дефицитного ресурса, чтобы его приобретение было выгодным
В столбце
Slack or Surplus
— разности правой и левой частей ограничений
(величины неиспользованных ресурсов).
В столбцах Minimum RHS и Maximum RHS — границы интервалов осуществимости
(устойчивости), то есть пределы изменения правых частей ограничений (запасов
ресурсов), при которых неизменны соответствующие теневые цены и в
оптимальном решении сохраняется прежний набор ненулевых переменных
(ассортимент продукции).
В нашем примере интервалами осуществимости (устойчивости) будут:
для трудовых ресурсов — [18, 20,6],
для сырья — [72, +
∞
),
для финансов — [94,5, +
∞
).
После просмотра итогового отчета
вы вернетесь в меню функций, где можно:
изменить условия текущей задачи (п. 7 — изменение задачи),
ввести новую задачу (п. 2 — ввод новой задачи)
выйти из программы или пакета, выбрав, соответственно, п. 9 — выход в меню
программ или п. 10 — выход из QSB+ (или QS).
Самостоятельная работа
Установите на своем компьютере пакет прикладных программ QSB+ и с его помощью
самостоятельно воспроизведите решение примера 2.4.1 (задача производственного
планирования).
СОВЕТ
Не жалейте времени, повторите все, что было выполнено в этом разделе, на своем компьютере.
2.4.3. Решение задачи линейного программирования с помощью
программы Excel
Программа Excel позволяет оформить решение любой задачи линейного
программирования в виде, удобном для работы и особенно для демонстрации
полученных результатов коллегам по работе, начальству и т. п. Этим решение задач
линейного программирования с помощью Excel выгодно отличается от решения с
помощью пакетов прикладных программ.
Ввод числовых данных
Решим задачу производственного планирования, сформулированную в разделе 2.4.1.
Для этого на рабочем листе введем ее числовые данные следующим образом:
Ст
р
. 45 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
В 1-й строке таблицы находится заголовок.
Во 2-й — наименования продуктов.
В 3-й строке отведено место для оптимального решения, которое после
вычислений появится в ячейках B3:E3 (в жирной рамке).
В 4-й строке в ячейках B4:E4 заданы коэффициенты целевой функции, а ячейка
F4, в рамке, зарезервирована для вычисления значения целевой функции.
Строки с 6-й по 15-ю содержат коэффициенты, знаки и правые части ограничений.
В столбце Лев.часть после вычислений появятся левые части ограничений.
В столбце Разница — появится разность правых и левых частей.
Предложенная форма таблицы удобна не только для выполнения расчетов, но и для
документирования результатов моделирования, а также обмена идеями и улучшения
взаимопонимания при работе «в команде» — группе лиц, ответственных за принятие
решений. Наглядность таблицы обеспечивается использованием заголовков,
полужирного шрифта, подчеркивания текста и центрирования.
ПРИМЕЧАНИЕ
Денежные величины следует представлять в денежном или финансовом формате (с указанием символа
используемой валюты).
Оформление таблицы облегчают кнопки панели форматирования, в частности:
Объединить и поместить в центре (для центрирования заголовка, занимающего
несколько ячеек),
Денежный формат
(для задания финансового формата),
Увеличить разрядность или Уменьшить разрядность (
д
ля задания нужного числа дробных
знаков).
ПРИМЕЧАНИЕ
Чтобы отобразить знак > или <, наберите знак > или < и затем подчеркните его.
После составления таблицы подберите ширину ее столбцов в соответствии с
содержимым ячеек, для чего:
1.
Выделите весь лист, щелкнув прямоугольник в левом верхнем углу листа (на
Ст
р
. 46 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
пересечении заголовков строк и столбцов).
2.
Дважды щелкните правую границу заголовка любого из столбцов.
Ввод формул
Формулы и ячейки, в которые их следует ввести, указаны в следующей таблице:
Чтобы ввести, например, формулу для вычисления целевой функции:
1.
Укажите ячейку F4.
2.
Нажмите клавишу «=».
3.
В левой части строки формул раскройте список функций и щелкните имя функции
СУММПРОИЗВ. Если его там нет, выберите в списке пункт
Другие функции
. В
открывшемся окне в категории Математические найдите функцию СУММПРОИЗВ и
дважды щелкните ее имя. Откроется диалоговое окно для задания аргументов
этой функции. Оно будет выглядеть следующим образом:
4.
Введите аргументы функции СУММПРОИЗВ.
5.
Щелкните кнопку OK.
Сразу после ввода формулы в ячейке F4 появится 0, так как формула вычисляется с
нулевыми значениями переменных (ячейки B3:E3 пока пусты).
Функция СУММПРОИЗВ позволяет вычислить сумму произведений двух массивов,
первый из которых содержит значения переменных, а второй — коэффициенты
целевой функции.
Чтобы указать соответствующие диапазоны, можно воспользоваться кнопками
свертывания, расположенными справа от полей ввода. Они позволяют временно
убрать панель формул с экрана, чтобы удобнее было выделять диапазон на листе.
Закончив выделение, щелкните кнопку снова для восстановления панели.
Ссылка на первый диапазон должна быть абсолютной, со знаками доллара перед
каждой буквой и цифрой: $B$3:$E$3 (чтобы изменить относительную ссылку на
абсолютную, нажмите клавишу F4 непосредственно после ввода этой ссылки; если
это не сделать сразу, то в дальнейшем ссылку сначала понадобится выделить и
лишь затем нажать клавишу F4).
Ячейка Фо
р
м
у
ла Копи
р
овать в
F4 =СУММПРОИЗВ($B$3:$E$3;B4:E4) F6:F15
I6 =H6-F6 I7:I8; I13:I15
I9 =F9-H9 I10:I12
Ст
р
. 47 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Ссылка на второй диапазон B4:E4, напротив, должна быть относительной: что
понадобится в дальнейшем при копировании формулы.
После ввода формулы для вычисления целевой функции необходимо задать
формулы левых частей ограничений. С этой целью скопируйте формулу из ячейки F4
в ячейки F6:F15. Чтобы копировалась только сама формула (без формата ячейки,
к
которому относятся, например, рамка и символ используемой валюты) можно
воспользоваться специальной вставкой, для этого проделайте следующее:
1.
Щелкните ячейку F4 правой кнопкой мыши и в контекстном меню выберите
команду Копировать.
1.
Выделите диапазон F6:F15, щелкните его правой кнопкой мыши.
2.
В контекстном меню выберите команду
Специальная вставка
.
3.
В группе Вставить открывшегося окна выберите параметр формулы и щелкните
кнопку OK.
При копировании относительная ссылка B4:E4 будет меняться, указывая на массивы
коэффициентов соответствующих ограничений, а абсолютная — $B$3:$E$3 —
останется неизменной.
Чтобы отменить движущуюся границу ячейки F4, нажмите клавишу Esc.
СОВЕТ
В некоторых моделях линейного программирования целевая функция задается простой суммой
переменных (все коэффициенты равны 1).
Д
ля нахождения такой целевой функции можно использовать
функцию СУММ() — вместо СУММПРОИЗВ(). В таком случае в таблице: а) будет отсутствовать строка с
коэффициентами целевой функции (4-я строка примера); б) ячейка с целевой функцией будет
находиться в той строке, где и вычисляемые решения (3-я строка примера); в) формулы левых частей
ограничений нужно будет
ввести отдельно, с помощью функции СУММПРОИЗВ() — без использования
копирования. Это позволит сделать модель более компактной за счет удаления лишней строки с
коэффициентами целевой функции — строки, состоящей в данном случае из одних единиц.
Для проверки формулы в ячейке достаточно дважды щелкнуть эту ячейку. Формула
будет отображена на экране, ссылки на ячейки — выделены цветом, а сами ячейки —
обведены рамками соответствующих цветов (после просмотра нажмите клавишу
Esc
).
Чтобы отображались все введенные формулы:
1.
Выберите в меню Сервис команду Параметры.
2.
В открывшемся окне на вкладке Вид в группе Параметры окна установите флажо
к
Формулы.
Если таблицу с формулами необходимо напечатать, подберите ширину ее столбцов
в соответствии с содержимым ячеек, как это было описано ранее.
Аналогично, с помощью копирования, вводятся формулы в ячейки I6:I15
д
ля
вычисления разницы правых и левых частей ограничений.
Д
ля ограничений со знаком
< из правой части ограничения вычитается левая, а для ограничений со знаком > —
наоборот. Таким образом, если ограничения выполняются и план допустим, то
разница всегда будет неотрицательна.
После ввода формул вы можете подставлять в ячейки B3:E3 любые значения
(количество выпускаемой продукции), получая соответствующую величину прибыли в
ячейке F4 и объем израсходованных ресурсов в столбце
Лев.часть. Столбец Разница
покажет, допустим ли соответствующий производственный план, какие ресурсы
дефицитны (для них разница равна нулю) и каков остаток недефицитных ресурсов
(он равен положительной разнице).
Указание целевой и изменяемых ячеек
Ст
р
. 48 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Теперь воспользуемся средством поиска решений. Для этого в меню Сервис выберите
команду
Поиск решения
, которая откроет одноименное окно
Поиск решения
. При решении
нашей задачи оно должно быть заполнено следующим образом:
Итак, в окне Поиск решения вы должны задать следующие параметры:
Установить целевую ячейку — для указания целевой ячейки, значение которой
необходимо максимизировать, минимизировать или установить равным
заданному числу. Эта ячейка должна содержать формулу для вычисления
целевой функции.
Равной — для выбора варианта оптимизации значения целевой ячейки
(максимизация, минимизация или подбор заданного числа).
Изменяя ячейки — для указания ячеек, значения которых изменяются в процессе
поиска решения до тех пор, пока не будут выполнены наложенные ограничения и
условие оптимизации значения целевой ячейки. В нашем примере это ячейки,
отведенные для значений переменных.
Ограничения — для отображения списка ограничений поставленной задачи.
При вводе ссылок на ячейки (как и при задании аргументов функции СУММПРОИЗВ)
удобно пользоваться кнопками свертывания диалогового окна, расположенными
справа от соответствующих полей.
Добавление ограничений
Для ввода ограничений следует нажать кнопку
Добавить, открывающую окно Добавление
ограничения
, которое выглядит следующим образом:
В этом окне — два поля ввода:
Ст
р
. 49 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm
Ссылка на ячейку — для указания ячейки или диапазона ячеек, на значения которых
необходимо наложить ограничение («левая часть ограничения»).
Ограничение — для задания условия, накладывающегося на значения ячейки или
диапазона, указанного в поле
Ссылка на ячейку
(«правая часть ограничения»). В это
поле можно ввести число, формулу, ссылку на ячейку или диапазон.
В раскрывающемся списке, расположенном между этими полями, можно выбрать:
необходимый знак (<=, =, >=);
пункты цел (целое число) или двоич (двоичное число — 0 или 1), указывающие вид
переменных при целочисленном решении.
Для ввода ссылок на ячейки и диапазоны можно, как и раньше, воспользоваться
кнопками свертывания диалогового окна, расположенными справа от полей ввода. Но
поскольку окно Добавление ограничения и так достаточно невелико, удобнее просто
перетащить его вниз экрана, поместив указатель мыши на заголовке. Затем следует
щелкнуть в нужном поле этого окна и выделить на рабочем листе ячейку или
диапазон, на который делается ссылка.
Каждое ограничение задачи можно вводить индивидуально. Однако когда знаки
ограничений одинаковы, удобнее указывать их левые и правые части в виде
диапазонов ячеек.
После ввода каждого ограничения, кроме последнего, следует нажимать кнопку
Добавить. При этом поля окна Добавление ограничения очищаются и можно вводить
следующее ограничение. После ввода последнего из них, щелкните кнопку OK, чтобы
вернуться в окно Поиск решения, где вы увидите список всех введенных ограничений.
При необходимости их изменения или удаления можно выделить любое из
ограничений и нажать кнопку, соответственно,
Изменить
или
Удалить
.
Задание дополнительных параметров поиска решения
Чтобы задать другие параметры поиска решения, щелкните кнопку
Параметры
,
открывающую окно Параметры поиска решения, которое выглядит так:
Значения большинства параметров, установленные по умолчанию, годятся для
решения большинства задач. Однако специально для решения задач линейного
Ст
р
. 50 из 101Шаблон для книг
(
Word 97
)
15.09.2004mk:
@
MSITStore:\\e
p
b4\New%20files\К
у
т
у
зов.chm::/Manual.htm