Для многих моделей Л П, как и в данном случае, дробные значения переменных решения не имеют физического смысла. Например, решение «произвести 3,12 стульев Captain и 6,88 стульев Mate» реализовать невозможно. С другой стороны, для многих задач дробные значения, безусловно, имеют смысл (например, «произвести 98,65 галлонов бензина»). В тех случаях, когда дробные ответы смысла не имеют, существует четыре возможных выхода.
1. Добавить в модель ЛП так называемое условие целочисленности, которое требует, чтобы одна или несколько переменных решения принимали только целые значения. Это приведет к изменению модели, которая превратится в модель целочисленной оптимизации или целочисленного программирования. Модели целочисленного программирования имеют дополнительные особенности, которые отличают их от обычных моделей ЛП, поэтому на данном этапе мы их рассматривать не будем. Целочисленному программированию посвящена глава 6.
2. Решать задачу как обычную задачу линейного программирования, а затем округлить (до ближайшего целого числа) все переменные решения, для которых дробные ответы невозможно реализовать. Однако во многих случаях эта простая и очевидная тактика может привести к недопустимым или неоптимальным решениям.
3. Можно считать, что результаты работы модели задают средний недельный уровень производства для периода из нескольких последующих недель. Например, решение «произвести 70,5 стульев Captain и 80,25 стульев Mate» можно реализовать следующим образом: согласно производственному плану еженедельно производится 70,5 стульев Captain, но 1) каждую первую неделю продается 70 стульев Captain, а половина стула переходит на следующую неделю как полуфабрикат, который следует закончить; 2) каждую вторую неделю продается 71 стул марки Captain. Аналогично еженедельно производится 80,25 стульев марки Mate, но 1) каждые три недели продается только 80 стульев этой марки, а все незаконченные части стула рассматриваются как полуфабрикат, и 2) каждую четвертую неделю продается 81 стул Mate. Если следовать этим правилам, то среднее недельное производство для четырехнедельного периода действительно составит 70,5 Captain и 80,25 Mate, как предписывается решением задачи ЛП. Преимущества и недостатки использования усредненной недельной модели обсуждаются в главе 5 при описании динамических моделей.
4. Можно рассматривать результаты использования модели Oak Product только как ориентиры для планирования, а не как оперативные решения, которые следует реализовывать. В таком случае эти результаты будут служить основой для принятия окончательного решения, которое неизбежно будет учитывать другие аспекты реальной ситуации, не нашедшие отражения в абстрактной модели Л П. Весьма вероятно, что эти аспекты все равно приведут к отклонению окончательных решений от нецелочисленных решений, полученных с помощью модели ЛП. В таком случае решение, предложенное моделью ЛП, служит точкой отсчета при рассмотрении дополнительных соображений и является основой для анализа ситуации, для чего, собственно говоря, и разрабатываются модели.
На практике применяются все вышеуказанные подходы. На данном этапе будем считать, что дробные значения представляют некие средние уровни производства (вариант 3), или модель разрабатывается в качестве основы для планирования и анализа (вариант 4).
Решим решение задачи о выпуске двух видов стульев в электронных таблицах.
Исходные данные для задачи представлены на рис.
Упрощенная модель Oak Products Тип стульев Captain Mate Удельная прибыль $ 56 $ 40 Прибыль Произведенное к-во $ 0 Потребность в деталях Суммарное потребление Начальный запас Конечный запас Длинные штифты 8 4 0 < 1280 1280
Короткие штифты 4 12 0 < 1600 1600
Ножки 4 4 0 < 760 760 Прочные сиденья 1 0 0 < 140 140 Облегченные сиденья 0 1 0 < 120 120 Стулья Мин. производство Резерв Произведено 1 1 0 > 100 -100
Рис.
9. Исходные данные В ячейках B4 и C4 будем искать значения переменных, обеспечивающих максимум прибыли.
Проделывая процедуры, аналогичные в задаче о красках получим:
Упрощенная модель Oak Products Тип стульев Captain Mate Удельная прибыль $ 56 $ 40 Прибыль Произведенное к-во 130 60 $ 9 680 Потребность в деталях Суммарное потребление Начальный запас Конечный запас Длинные штифты 8 4 1280 < 1280 0 Короткие штифты 4 12 1240 < 1600 360 Ножки 4 4 760 < 760 0 Прочные сиденья 1 0 130 < 140 10 Облегченные сиденья 0 1 60 < 120 60 Стулья Мин. производство Резерв Произведено 1 1 190 > 100 90
Рис.
10. Найденное оптимальное решение Таким образом, если спланировать выпуск 130 стульев Captain и 60 стульев Mate, то прибыль будет максимальна и составит 9680 $.
Отчет по результатам решения представлен на рис. 11
Microsoft Excel 11.0 Отчет по результатам Рабочий лист: [СТ1.xls]Лист2 Отчет создан: 05.
06.2005 13:08:55 Целевая ячейка (Максимум) Ячейка Имя Исходное значение Результат $D$ 4 Произведенное к-во Прибыль $ 0 $ 9 680 Изменяемые ячейки Ячейка Имя Исходное значение Результат $B$ 4 Произведенное к-во Captain 0 130 $C$ 4 Произведенное к-во Mate 0 60 Ограничения Ячейка Имя Значение Формула Статус Разница $D$ 6 Длинные штифты Суммарное потребление 1280 $D$ 6<=$F$ 6 связанное 0 $D$ 7 Короткие штифты Суммарное потребление 1240 $D$ 7<=$F$ 7 не связан. 360 $D$ 8 Ножки Суммарное потребление 760 $D$ 8<=$F$ 8 связанное 0 $D$ 9 Прочные сиденья Суммарное потребление 130 $D$ 9<=$F$ 9 не связан. 10 $D$ 10 Облегченные сиденья Суммарное потребление 60 $D$ 10<=$F$ 10 не связан. 60 $D$ 12 Произведено Стулья 190 $D$ 12>=$F$ 12 не связан. 90 $B$ 4 Произведенное к-во Captain 130 $B$ 4>=0 не связан. 130 $C$ 4 Произведенное к-во Mate 60 $C$ 4>=0 не связан. 60
Рис.
11. Отчет по результатам поиска оптимума.
Более сложная задача представлена и решена в приложенном файле ST6. xls
Заключение
В проделанной курсовой работе рассмотрена задача линейного программирования, в которой объектом исследования является планирование оптимального выпуска стульев компанией Oak Product. Основная цель — учебная: научиться решать подобные задачи — достигнута. Освоен такой мощный инструмент исследования задач поиска эффективных управленческих решений как «Поиск решений» в электронных таблицах Excel из пакета MicrosoftOffice.
При постановке задач линейного программирования очень важно сформулировать критерий оптимизации, для которого ищется либо максимум либо минимум в некоторой области, ограниченной какими то ресурсными или физическими ограничениями.
Ограничения — это математические условия, которые исключают определенные комбинации значений переменных решения. Допустимые решения — это значения переменных, удовлетворяющие всем ограничениям. Линейное программирование занимается поиском допустимого решения, оптимизирующего линейную целевую функцию. Задача линейного программирования — это математическая модель, обладающая следующими свойствами.
1. Линейность целевой функции, которую необходимо максимизировать или минимизировать.
2. Линейность ограничений, каждое из которых представляет собой неравенство или равенство.
Учитывая гибкость моделирования на базе электронных таблиц, необходимо следовать определенным правилам, чтобы построить табличную модель, обладающую такими свойствами:
1) точно соответствует модели ЛП,
2) легко документируется,
3) имеет форму, пригодную для оптимизации с помощью средства Поиск решения,
4) не вызывает проблем при интерпретации отчетов средства Поиск решения. Чтобы успешно использовать средство Поиск решения, необходимо придерживаться следующих правил.
1. Все формулы, влияющие на целевую функцию или ограничения, должны быть линейными, если в них прямо или косвенно (через формулы других ячеек) входят переменные решения.
2. Линейная модель является частным случаем нелинейной модели. Однако для средства Поиск решения такое суждение неправомерно: эта надстройка использует разные алгоритмы для оптимизации разных классов моделей. Если в диалоговом окне Параметры поиска решения не установить опцию Линейная модель и оптимизировать модель ЛП с помощью средства Поиск решения, можно не получить оптимального решения; даже если оптимальное решение будет получено, отчеты для линейной и нелинейной моделей выглядят по-разному.
3. В диалоговом окне Поиск решения при задании правых частей ограничений необходимо ссылаться на ячейки рабочего листа, которые являются константами или которые не будут меняться в процессе оптимизации. Кроме того, не разрешается вводить формулы при определении левых частей ограничений в диалоговом окне Добавление ограничения. Чтобы избежать ошибок и ненужных сложностей, не следует вводить формулы или константы непосредственно в поля левых или правых частей ограничений диалогового окна Добавление ограничения. Рекомендуется помещать формулы и константы в ячейки таблицы, а в полях диалогового окна Добавление ограничения указывать адреса соответствующих ячеек.
4. В моделях большого размера полезно присваивать имена диапазонам ячеек переменных решения, ячейке показателя эффективности, группам ячеек, содержащих левые части ограничений одного знака, и группам ячеек, содержащих правые части ограничений одного знака.
Перед выполнением процесса оптимизации в диалоговом окне Поиск решения нужно указать целевую ячейку, изменяемые ячейки, ограничения и установить флажок Линейная модель. Кроме того, если отрицательные значения переменных решения не имеют смысла, нужно установить флажок опции Неотрицательные значения. После завершения оптимизации на экране появится диалоговое окно Результаты поиска решения, содержащее сообщения о завершении вычислений и позволяющее создать один или несколько отчетов о поиске решения.
Если цель — максимизация прибыли, то это задача на поиск максимума.
Если цель — уменьшить затраты, получится модель минимизации. Ограничения записываются в виде неравенств со знаком < или >. В некоторых случаях необходимо ввести ограничения в виде равенств.
Задача о выпуске стульев поставлена и решена как задача максимизации с помощью встроенной функции Excel — «Поиск решения».
Абрамов Л.М., Капустин В. Ф. Математическое программирование. Л., Изд-Ленингр. ун-та, 1976. — 184 с.
Акоф Р., Сасиени М. Основы исследования операций. М.: Мир, 1974.
Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие — 2-е изд., испр. и доп. — М.: Высш. шк., 1993 — 336 с.
Ашманов С. А. Линейное программирование. — М.: Наука, 1981.
Баканов М.И., Шеремет А. Д. Теория экономического анализа: Учебник. -4-е изд., доп. и перераб. — М.: Финансы и статистика, 2000. — 416 с.
Баканов М.И., Шеремет А. Д. Экономический анализ: ситуации, тесты, примеры, задачи, выбор оптимальных решений, финансовое прогнозирование: Учеб. пособие. — М.: Финансы и статистика, 1999. -656 с.
Банди Б. Основы линейного программирования: Пер. с англ. — М.: Радио и связь, 1989. -176 с.
Бирман И. Я. Оптимальная экономика. М.: Экономика, 1968
Габасов Р., Кириллова Ф. М. Методы линейного программирования. Ч.
1. Общие задачи, Минск, Изд-во БГУ им. В. И. Ленина, 1977. — 176 с.
Габасов Р., Кириллова Ф. М. Методы линейного программирования. Ч.
2. Транспортные задачи, Минск, Изд-во БГУ им. В. И. Ленина, 1977. — 240 с.
Гарнаев А. Ю. Использование MS-Excel и VBA в экономике и финансах. — СПб.: БХВ — Санкт-Петербург, 1999. — 336 с.
Глухов В.В., Медников М. Д., Коробко С. Б. Математические методы и модели для менеджмента — СПб.: Издательство «Лань», 2000. -480 с.
Гольштейн Е.Г., Юдин Д. Б. Линейное программирование, теория, методы и приложения. — М.: Наука, 1969.
Гасс С. Линейное программирование. — М.: Физматгиз, 1961.
Канторович Л.В., Горстко А. Б. Оптимальные решения в экономике. М.: Наука, 1972
Конюховский П. В. Математические методы исследования операций. — СПб: Питер, 2001. — 192 с., ил.
Кузнецов Ю.Н., Кузубов В. И., Волощенко А. Б. Математическое программирование: Учеб. пособие. — 2-е изд., перераб и доп. — М.: Высш. школа, 1980. -300 с.
Ляшенко И. Н, Карагодова Е. А, Черникова Н. В., Шор Н. З. Линейное и нелинейное программирование. Издательское объединение «Вища школа», 1975. — 372 с.
Пер. с яп. / М. Кубонива, М. Табата, С. Табата, Ю. Хасэбэ, под ред. М.
Кубонива. Математическая экономика на персональном компьютере: — М.: Высш. школа, 1980.
Солодовников А.С.
Введение
в линейную алгебру и линейное программирование. М., Изд. «Просвещение», 1966. — 184 с.
Схрейвер А. Теория линейного и целочисленного программирования: В 2-х т. Т.1: Пер с англ. — М.: Мир, 1991. -360 с.
Тынкевич М.А. Экономико-математические методы (исследование операций). Изд. 2, испр. и доп. — Кемерово, 2000. — 177 с.
x2
x1
C
