Отчет по устойчивости для ограничений

Рассмотрим «Отчет по устойчивости» для ограничений поставленной задачи (в таблице 3):

Сравнивая левые (графа «Результ.значение») и правые части (графа «Ограничение. Правая часть») всех ограничений, легко убедиться, что в оба центра сбыта поставляется ровно столько установок, сколько им требуется, а единственный центра производства, откуда вывозятся не все установки, - Стокгольм (вывезено 110, а произведено 120 установок).

Таблица 3 – Отчет по устойчивости для ограничений

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

Так, при увеличении выпуска в Триесте или Руане на 1 установку стоимость оптимальных перевозок уменьшится соответственно на 7 или на 13 ф.ст. В случае, если центрам сбыта в Лейпциге или Лионе потребуется еще 1 установка, все перевозки подорожают соответственно на 25 или на 14 ф.ст. Следует подчеркнуть, что здесь также речь идет об изменении каждого свободного члена по отдельности, а не всех вместе.

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

Сколько будет стоить самый дешевый план перевозок, если в Руане будет производиться не 90, а, например, 100 установок? Так как выпуск возрос по сравнению с исходным на 10 установок, а «Теневая цена» равна
–13, то оптимум уменьшится на 10*13 = 130. Следовательно, новая стоимость составит 3560 – 130 = 3430 (ф.ст.), в чем легко убедиться, поставив в ячейке D10 число 100 и выполнив «Поиск решения».

Однако нельзя забывать о том, что «Теневыми ценами» можно пользоваться лишь в диапазоне их устойчивости. Он приводится в графах «Допустимое увеличение» и «Допустимое уменьшение». Из этих граф видно, что изменение запасов и потребностей на единицу в любую сторону не выходит за пределы допустимого диапазона. Можно сказать, что приведенные «Теневые цены» будут представлять собой оптимальный план двойственной задачи только до тех пор, пока потребности Лейпцига изменяются в диапазоне от 130 = 150 - 20 до 160 = 150 + 10 установок, или потребности Лиона – в диапазоне от 0 до 100 установок. Для устойчивости «Теневых цен» производство установок в Стокгольме должно быть не меньше 110, в Триесте – от 30 до 60, а в Руане – от 80 до 110.

Поэтому ответить на вопрос, чему будет равен оптимум, если в Руане будет производиться, например, 130 установок, с помощью только «Отчета по устойчивости» невозможно. В самом деле, мы подняли производство на 40 установок (130 – 90 = 40), а «Допустимое увеличение» - всего 20.

Убедимся в том, что данным о диапазоне устойчивости можно доверять. Так как в прямой задаче введено 6 основных переменных, двойственная будет включать 6 ограничений. В оптимальном плане двойственной задачи имеется 6 отличных от нуля переменных – 4 основных (графа «Теневая Цена» в таблице 3) и 2 дополнительных (графа «Нормир.стоимость» в таблице 2). Следовательно, ее базис не является вырожденным, и информация, предоставляемая «Отчетом по устойчивости», соответствует истине.

Отчет по пределам для транспортной задачи

«Отчет по пределам» представлен в таблице 4.

В этом отчете показано, в каких пределах могут изменяться значения переменных, чтобы план оставался допустимым (и каким будет при этом значение целевой функции). Например, если в оптимальном плане X = (20; 90; 40; 0; 90; 0) переменной х₁₁ (количество установок, перевозимых из Стокгольма в Лейпциг) вместо 20 присваивать значения от 20 до 30, то такие планы останутся допустимыми (а затраты на перевозки на этих планах будут принимать значения от 3560 до 3810 ф.ст.). При выходе за пределы этого диапазона либо производственные возможности Стокгольма будут превышены, либо потребности Лейпцига не будут удовлетворены.

Таблица 4 – Отчет по пределам

Порядок выполнения работы

1 Изучить методические указания к лабораторной работе.

2 Ответить на контрольные вопросы.

3 Самостоятельно построить открытую модель транспортной задачи и решить ее с помощью «Поиска решения».

4 Проанализировать все отчеты, предоставляемые «Поиском решения».

ОФОРМЛЕНИЕ РЕЗУЛЬТАТОВ РАБОТЫ

Отчет по лабораторной работе должен включать:

а) формулировку условий транспортной задачи в виде текста;

б) условия транспортной модели в виде задачи линейного программирования;

в) результаты решения задачи (ответ);

г) три отчета, предоставляемые «Поиском решения».

КОНТРОЛЬНЫЕ ВОПРОСЫ

1 Как правильно поставить транспортную задачу для «Поиска решения»?

2 Какой метод использует «Поиск решения» для решения транспортной задачи?

3 Какую информацию предоставляет «Отчет по результатам»?

4 Какую информацию предоставляет «Отчет по устойчивости»?

5 Какую информацию предоставляет «Отчет по пределам»?

ЛИТЕРАТУРА

Основная литература

1 Вентцель Е.С. Исследование операций: задачи, принципы, методология: Учеб. пособие для втузов. – М.: Высшая школа, 2001.

2 Корнилова И.Л. Введение в экономико-математические методы: Учеб. пособие в 2 частях. – Гатчина: изд-во Ленинградского областного института экономики и финансов, 2001.

3 Корнилова И.Л., Парамонова Н.Н. Решение управленческих задач средствами исследования операций с помощью универсального пакета Excel: Учеб .пособие. - СПб.: ИК «Синтез», 2006.

4 Корнилова И.Л., Парамонова Н.Н. Транспортная задача: Метод. указания. - СПб.: ИК «Синтез», 2003.

5 Корнилова И.Л., Парамонова Н.Н. Экономико-математические методы (специальные задачи линейного программирования): Метод. указания. - СПб.: РТП ИК «Синтез», 2000.

6 Корнилова И.Л., Пучков В.Ф. Решение управленческих задач средствами экономико-математического моделирования (издание 2-е, исправленное и дополненное): Учеб. пособие. - Гатчина, изд-во Ленинградского областного института экономики и финансов, 2004.

7 Новиков О.А., Уваров С.А. Логистика. – СПб.: Бизнес-Пресса, 2000.

8 Хачатрян В.М. Прикладные методы математического моделирования экономических систем: Научно-методическое пособие. – М.: Изд-во «Экзамен», 2002.

9 Шелобаев С.И. Математические методы и модели в экономике, финансах и бизнесе: Уч.пособие для вузов. – М.: ЮНИТИ, 2000.

10 Шикин Е.В, Чхартишвили А.Г. Математические методы и модели в управлении: Учеб. пособие для вузов. – М.: Дело, 2002.

Дополнительная литература

11 Таха Хэмди А. Введение в исследование операций: в 2-х кн. - М.: Мир, 1985.

12 Томас Р. Количественные методы анализа хозяйственной деятельности. – М.: Дело и Сервис, 1999.

13 Эддоус М., Стэнсфилд Р. Методы принятия решений. - М.: Аудит, ЮНИТИ, 1997.

14 Кремер Н.Ш., Путко Б.А. и др. Исследование операций в экономике. - М.: Банки и биржи, ЮНИТИ, 1997.

15 Курицкий Б.Я. Поиск оптимальных решений средствами Excel 7.0. – СПб.: ВНV, 1997.

ПРИЛОЖЕНИЕ А

(рекомендуемое)

Задача о назначениях

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

Модель в общем виде   Необходимо распределить n работ между n исполнителями таким образом, чтобы их выполнение было наиболее эффективным. Каждый исполнитель может выполнять только одну работу, и каждая работа может быть выполнена только одним исполнителем. Известна эффективность выполнения i-й работы j-м исполнителем - cij, .

Пример   Необходимо изготовить 4 образца изделий на 4 станках (n = 4), причем каждый образец может изготавливаться только на одном станке, а каждый станок быть занят изготовлением только одного образца. Задана матрица эффективности производства каждого образца на каждом станке (строки соответствуют образцам, а столбцы – станкам): (изготовление первого образца на первом станке вообще не эффективно - c11 = 0, на втором эффективность оценивается c12 = 10, …, эффективность изготовления четверного образца на четвертом станке оценивается c44 = 20). Составить наиболее эффективный план производства изделий.

Введем переменные

,

.

Тогда суммарная эффективность составит

Продолжение приложения А

- в этой сумме часть слагаемых будет равна 0 (для хij = 0), а другая часть будет представлять собой эффективность от выполнения конкретной работы конкретным исполнителем (для хij = 1).   Каждая i –я работа должна быть выполнена одним исполнителем: .   Каждый j–й исполнитель должен выполнить одну из работ:

(10х12 + 15х13 + 4х21 + 4х22 + 2х23 + +10х24 + 20х31 + 30х32 + 5х33 +10х41 + 20х44)   Первый образец обязательно должен быть изготовлен на одном из станков: То же самое должно выполняться для остальных трех образцов: На первом станке должен изготавливаться один образец: То же самое должно выполняться для остальных трех станков:

Тогда модель примет вид

mах	mах (10х12 + 15х13 + 4х21 + 4х22 + 2х23 + 10х24 + 20х31 + 30х32 + 5х33 +10х41 + 20х44)

Продолжение приложения А

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

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

ПРИЛОЖЕНИЕ Б

(обязательное)

Введение в "Систему деловых задач"

Пакет прикладных программ "Quantitative Systems for Business" (или "Система деловых задач") позволяет строить различные экономико-математические модели и находить решение поставленных задач. При этом ход решения по желанию пользователя сопровождается наглядными иллюстрациями, отражающими используемый подход. Это делает программы пакета очень удобными для применения в учебном процессе.

Пакет предназначен для использования под управлением MS DOS. Все необходимые программы находятся в папке QSB. Для обращения к одной из программ пакета необходимо выбрать соответствующий файл с расширением .ехе и с его помощью запустить программу.

После запуска любой из программ пользователь попадает в главное меню. Выбор нужного режима осуществляется либо клавишами управления курсором (вверх/вниз; при этом перемещается подсветка строки меню режимов; подведя подсветку к нужному режиму, необходимо нажать клавишу <ввод>), либо вводом с клавиатуры номера нужного режима.

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

Программа решения транспортных задач запускается файлом tranрrob.exe. Она предназначена для решения транспортных задач размерности не более чем 50 х 50 (50 поставщиков («пунктов отправления») и 50 потребителей («пунктов назначения»)). Решение осуществляется методом потенциалов. Для задач небольшой размерности (до 4 х 5), возможен вывод на экран каждой итерации этого метода. Размерность задач указана для закрытой модели. Модель открытого типа может быть приведена к закрытому типу за счет введения как дополнительного (фиктивного) потребителя, так и поставщика; но при этом ее размерность соответственно возрастет.

Чтобы ввести и новую задачу, выбирают режим 2.

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

Перемещение между отдельными позициями ввода вперед осуществляется клавишей «ввод», а назад - клавишей «backspace». Исправление введенных значений осуществляют, просто печатая новые поверх старых. На некоторые вопросы программе необходимо ответить Y (yes, да), или N (no, нет), просто введя с клавиатуры нужную букву.

Продолжение приложения Б

Задача может быть поставлена как на минимум, так и на максимум.

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

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

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

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

Обычно ввод задачи осуществляется в несколько этапов, после каждого из которых выдается сообщение: «Нажмите SPACE BAR [пробел], если данные правильны».

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

Исходные данные могут быть введены с диска (дискеты) или записаны на них (сохранены) с помощью режимов соответственно 3 и 6. При обращении к этим режимам пользователю задаются вопросы, из какого файла (в какой файл) записывать информацию, и где он находится. Студентам рекомендуется сохранять свои данные, указывая только имя файла. При этом задача будет сохранена в папке QSB, откуда ее впоследствии можно перенести в свою папку. При чтении сохраненной задачи рекомендуется вначале перенести ее в папку QSB, а затем также указать только имя файла.

Введенные данные можно просмотреть и/или распечатать в режиме 4. Студентам рекомендуется использовать этот режим только для просмотра, т.е. на вопрос, следует ли распечатать данные, отвечать всегда N.

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

Продолжение приложения Б

Решение задачи осуществляется в режиме 5 (решения). Здесь пользователю также предлагаются различные виды меню режимов решения. Для создания опорного плана можно выбрать метод аппроксимации Фогеля (МАФ) либо метод северо-западного угла (МСЗУ) (по умолчанию используется последний). В программах пакета можно просмотреть и распечатать не только конечные, но и промежуточные результаты. При просмотре решения по итерациям переход к следующей итерации осуществляется любой клавишей, а нажав G, можно сразу перейти к заключительной таблице.

На каждой итерации в правом верхнем углу каждой клетки таблицы указаны коэффициенты целевой функции. Значение целевой функции на очередном опорном плане указано внизу таблицы. Потенциалы обозначены u(i) и v(j). Суммы потенциалов для каждой клетки не указываются. Клетка, соответствующая той переменной, которая войдет в базис, помечается в таблице двумя звездочками, а остальные вершины цикла - более ярким белым цветом (им же помечены потенциалы, соответствующие новой базисной клетке). Внизу таблицы также указываются номер этой клетки и разность между коэффициентом целевой функции при соответствующей переменной и суммой потенциалов. Разметка цикла наглядно не отображается

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

СОДЕРЖАНИЕ

Введение........................................................................................................... 3

Лабораторная работа 1 Постановка транспортной задачи

и ее решение методом потенциалов................................................................ 3

1 Цель работы................................................................................................. 3

2 Приборы и материалы................................................................................. 3

3 Описание работы.......................................................................................... 3

3.1 Постановка транспортной задачи......................................................... 3

3.2 Разрешимость транспортной задачи.................................................... 6

3.3 Открытая и закрытая модели транспортной задачи........................... 7

3.4 Задача о распределении специалистов, как пример

альтернативной экономической интерпретации транспортной задачи 9

3.5 Опорный план транспортной задачи.................................................. 11

3.5.1 Метод северо-западного угла

построения опорного плана транспортной задачи..................... 12

3.5.2 Метод наименьшей стоимости.................................................... 14

3.5.3 Метод аппроксимации Фогеля................................................... 17

3.6 Метод потенциалов.............................................................................. 19

3.7 Пример решения задачи методом потенциалов................................. 22

3.8 Модификации транспортной задачи................................................... 26

3.9 Порядок выполнения работы.............................................................. 27

4 Оформление результатов работы.............................................................. 27

5 Контрольные вопросы............................................................................... 28

Лабораторная работа 2 Решение транспортной задачи

с помощью надстройки «Поиск решения» в Microsoft Excel...................... 29

1 Цель работы................................................................................................ 29

2 Приборы и материалы............................................................................... 29

3 Описание работы........................................................................................ 29

3.1 Постановка транспортной задачи для «Поиска решения»................ 29

3.2 Отчет по результатам для транспортной задачи............................... 32

3.3 Отчет по устойчивости для транспортной задачи............................. 33

3.3.1 Отчет по устойчивости для переменных.................................... 33

3.3.2 Отчет по устойчивости для ограничений................................... 35

3.4 Отчет по пределам для транспортной задачи.................................... 37

3.5 Порядок выполнения работы.............................................................. 38

4 Оформление результатов работы.............................................................. 39

5 Контрольные вопросы............................................................................... 39

Литература..................................................................................................... 40

Приложение А Задача о назначениях.......................................................... 41

Приложение Б Введение в "Систему деловых задач".................................. 44

Кафедра финансов и статистики

Кафедра менеджмента и маркетинга

Методические указания