МИНИСТЕРСТВО ОБРАЗОВАНИЯ
Российской федерации
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ РАДИОТЕХНИКИ, ЭЛЕКТРОНИКИ И АВТОМАТИКИ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
В.М. Панченко а.В. Панов
ТЕОРИЯ ПРИНЯТИЯ
РЕШЕНИЙ
Линейное программирование
Учебное пособие
МОСКВА 2002
ББК 22.18
П
16
УДК 519.852
Рецензенты: д.т.н., проф. Р.Ф. Григорьев
д.т.н., проф. А.П. Свиридов
П 16 Панченко В.М., Панов А.В. Теория принятия решений. Линейное программирование: Учебное пособие / Московский государственный институт радиотехники, электроники и автоматики (технический университет). - М., 2002. - 52 с.
ISBN 5-7339-0306-6
Данное учебное пособие предлагается в качестве информационной поддержки процесса обучения по дисциплине «Теория принятия решений» в части проблематики линейного программирования. Методология изложения материала реализует принципы рационально-эмпирического подхода к изучению дисциплины. Пособие может быть использовано при самоподготовке для отработки соответствующих теоретических положений, а также допускает применение в качестве дополнительного источника при дистанционном обучении.
Учебное пособие предназначено для студентов специальности 220200.
Табл.16. Ил.11. Библиогр.: 19 назв.
Печатается по решению редакционно-издательского совета Московского государственного института радиотехники, электроники и автоматики (технического университета).
П
Без объявл. ББК 22.18
ISBN 5-7339-0306-6 В.М. Панченко, А.В. Панов, 2002
Введение
Государственный образовательный стандарт 2000 года в рамках специальности 220200 – «Автоматизированные системы обработки информации и управления» в части требований к обязательному минимуму содержания основной образовательной программы определяет следующие разделы учебной дисциплины «Теория принятия решений»:
основные понятия исследования операций и системного анализа;
методологические основы теории принятия решений;
задачи выбора решений, отношения, функции выбора, функции полезности, критерии;
детерминированные стохастические задачи, задачи в условиях неопределенности;
задачи скалярной оптимизации, линейные, нелинейные, дискретные;
многокритериальные задачи, парето-оптимальность, схемы компромиссов;
динамические задачи, марковские модели принятия решений;
принятие решений в условиях неопределенности.
Касаясь проблематики исследования операций и системного анализа, мы непременно сталкиваемся с таким классом задач, как задачи оптимизации. Они имеют как важное теоретическое, так и прикладное значение.
В классической теории оптимизации для нахождения точек максимума и минимума (экстремальных точек) функций в условиях как отсутствия, так и наличия ограничений на переменные широко используется аппарат дифференциального исчисления. Получаемые при этом методы не всегда оказываются удобными при их численной реализации. Однако соответствующие теоретические результаты лежат в основе большинства методов решения математических моделей, среди которых можно выделить следующие: методы динамического, целочисленного, нелинейного программирования, методы многокритериальной оптимизации и методы сетевых моделей. Наиболее известными и эффективными из методов решения задач оптимизации являются методы линейного программирования (ЛП).
Обследование
научной деятельности группы действительных
членов Американского общества исследования
операций, проведенное Р. Шенноном и В.
Байлесом, выявило рейтинг относительной
полезности методов исследования операций
(ИСО) в их повседневной научной работе
[1]. Данные исследований приведены в
табл. 1. Как видно, одно из первых мест в
рейтинге занимает ЛП.
Исследования Ф. Уэтсона 1000 крупнейших фирм США выявили примерно аналогичную систему рейтингов методов, применяемых при современном внутрифирменном планировании (рис. 1) [2]. По современным оценкам американских экспертов [3], около 75% от общего числа применяемых оптимизационных методов приходится на ЛП. Около четверти машинного времени, затраченного в последние годы на проведение научных исследований, было отведено решению задач ЛП и их многочисленных модификаций.
Целью создания данного учебного пособия явилось не описание достижений, полученных в вычислительной практике ЛП за последние тридцать лет, т.е. со времени создания Дж. Б. Данцигом симплекс-метода. Материалы по ЛП достаточно полно отражены в соответствующих источниках. Основу изложения составляет описание транспортной задачи линейного программирования (ТЗЛП), ее интерпретация и типовые варианты решений в различных базисах, что позволяет реализовать принцип «спора моделей», обнаружить ряд изоморфизмов изучаемых моделей и выявить возможности их использования в других предметных областях.
Авторы выражают благодарность студентке МИРЭА Л.И. Мингуловой за активное участие и помощь в процессе апробации учебных материалов пособия при проведении индивидуальных занятий и комплекса самостоятельных работ.
Верстка и подготовка электронной версии учебного пособия к печати осуществлены при участии студентов МИРЭА А.В. Филатова и А.А. Мустонен.