WWW.KNIGI.KONFLIB.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

 
<< HOME
Научная библиотека
CONTACTS

Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |

«МАТИ – РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ им. К.Э. Циолковского Кафедра высшей математики Горбацевич В.В. Современное линейное программирование ...»

-- [ Страница 1 ] --

ГОСУДАРСТВЕНЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО

ВЫСШЕМУ ОБРАЗОВАНИЮ

МАТИ – РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ

УНИВЕРСИТЕТ им. К.Э. Циолковского

Кафедра высшей математики

Горбацевич В.В.

Современное линейное программирование (Сборник задач с решениями на MAPLE5) Москва 1999 год Посвящается студентам МАТИ PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

ВВЕДЕНИЕ

Данное пособие посвящено современным методам решения современных задач по линейному программированию. При этом под современными задачами понимаются не более сложные или запутанные, чем опубликованные ранее (как часто бывает в современных книгах), а просто более актуальные задачи, для решения которых оказывается удобным применять методы линейного программирования. Что же касается современных методов решения, то это опять не какие-то изощренные математические методы, а просто использование современного подхода к решению многих математических задач. Речь идет об использовании универсальных математических пакетов, в данном пособии речь будет идти о пакете Maple5 (Release 4), который в настоящее время свободно распространяется через Интернет (и потому отечественный пользователь в данном случае избавлен от уже привычного для него состояния нелегального пользователя при работе с хорошей программой). Сейчас уже вышла новая версия - Release5, для нее все сказанное ниже остается справедливым (хотя в программе появились и новые усовершенствования, но они не коснулись методов решения задач линейного программирования). Задачи линейного программирования неплохо решаются и другими математическими программами - от простенькой на нынешний день программы Eureka до таких мощных пакетов, как MathCad и Mathematica, а также специализированными математическими программами.

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

В Части II приводятся примеры конкретных задач, которые можно записать (и решить!) в виде задач линейного программирования. Происхождение приводимых в данном пособии задач по линейному программированию не совсем обычно. Основные идеи в них принадлежат не автору пособия, а тем студентам старших курсов МАТИ, для которых автор в течение нескольких лет читал лекции по методам оптимизации (в которые, в качестве составной части, занимавшей от 10 до 25 академических часов, входило и линейное программирование). Дело в том, что для получения зачета или сдачи экзамена по этому курсу студенты должны были представить постановки и (в простейших случаях) решения РЕАЛЬНЫХ задач, для которых применимо линейное программирование. Под реальными автор (лектор) понимал задачи, достаточно хорошо знакомые студентам на практике. Не секрет, что подавляющее большинство студентов старших курсов сейчас сочетает (с разной степенью успешности) учебу с работой в какой-то, причем далеко не всегда связанной с профилем института, области. Так вот, именно из таких областей студенты в основном и брали темы для задач. Роль лектора на этом этапе составления задач сводилась к настойчивой демонстрации студентам самых различных вариантов применения линейного программирования. Чтобы преодолеть скепсис студентов, лектору приходилось придумывать для них примеры задач на почти произвольно заданную тему. В конце концов, студенты видели, что составить реальную задачу не так уж и сложно, как им поначалу казалось. Однако составленные ими на первых порах задачи носили иногда довольно абстрактный характер (напоминая “прикладные” задачи во многих известных сборниках задач - там говорится об изготовлении абстрактных изделий A, B, C, о смешивании неких компонент А, Б, В, Г и т.п.). Обсуждая эти задачи, лектор и студенты приходили к постановке вполне конкретных (хотя, конечно, и в сильно упрощенной форме) задач, в которых фигурировали совершенно реальные (на то время) цены и другие числовые данные PDF created with FinePrint pdfFactory trial version http://www.fineprint.com (например, для обоснования одной из задач студент принес справочник по технологии питания и распечатку дневной выручки в “Макдональдс”е, где он работал). Было несколько задач “фантазийного” и развлекательного характера, они часто отражали личные пристрастия студентов. В задачах студентов фигурировали (кроме множества естественных для нашего времени разного сорта бизнесменов - от банкира до бабушки, собирающей пустые бутылки), такие персонажи, как Смок Белью, Белоснежка и семь гномов, встречались даже там колдун, ювелир, рэкетир и палач...

При подготовке данного пособия автор пересмотрел заново формулировки задач и уточнил их (не меняя, по возможности, исходных данных, даже если они - например, цены или ассортимент компьютеров - в настоящее время уже устарели), некоторые условия пришлось перерабатывать, так как условия в них носили все же подчас искусственный характер. В результате получилось собрание задач, отражающее сферы деятельности и интересов студентов МАТИ второй половины 90-х годов, которые и приводятся в Части II Студенты не только составляли задачи, но и находили решения некоторых из них (если задача сводилась к задаче с двумя переменными и могла быть решена даже графически на листе бумаги в клетку). На освоение сложных методов решения задач линейного программирования не было достаточного учебного времени, а просить студентов просто автоматически повторять шаги симплекс-метода (самого распространенного метода решения задач линейного программирования), не вдаваясь особенно в его обоснования, лектор не считал возможным. И вот уже сейчас, через несколько лет, становится ясно, что времена рутинных вычислений стремительно откатываются в прошлое. Современные математические программы-пакеты позволяют решить задачу линейного программирования за несколько минут (включая не только время вычислений, но и запуск компьютера, вызов нужной программы и ввод условий задачи). Тратить время на освоение даже просто алгоритма симплекс-метода сейчас нужно уже далеко не всем тем, кому нужно бывает иногда решать задачи линейного программирования. Возможность за одну минуту просмотреть 3-4 варианта решений одной задачи (при изменении некоторых числовых параметров, входящих в условия) - это то, что получает каждый освоивший, например, пакет В Части III данного пособия приводится описания той части универсального математического системы Maple5 (Release4), которая касается линейного программирования вообще и симплекс-метода в частности. Следует отметить, что в изданных на русском языке книгах по Maple’у описания математических пакетов-расширений довольно поверхностны, а часто просто неточны (что связано, видимо, с тем, что их авторы не являются профессиональными математиками и не используют Maple в полной мере). Приводимых в данном пособии сведений о Maple5 вполне достаточно, чтобы с помощью справочной системы Help в Maple5 или самого простого руководства по интерфейсу Maple (на описание интерфейса в данном пособии просто нет достаточного места) решить любую из задач, приведенных в Части I. В приложениях приведены примеры решений задач из Части I (математические постановки задач, тексты программ для Maple, другие примеры приведены в Части II) и ответы ко всем задачам, а также дана формулировка того задания по составлению и решению задач, которое давалось лектором студентам.

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

Работа выполнена при поддержке Государственной программы интеграции высшего образования и фундаментальной науки на 1997-2000 годы, #480.

PDF created with FinePrint pdfFactory trial version http://www.fineprint.com

ЧАСТЬ I

ПОСТАНОВКА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Линейное программирование - это теория и практика нахождение экстремумов линейных функций нескольких переменных, связанных между собой линейным уравнениями и неравенствами. Такого рода задачи встречаются в самых разнообразных областях человеческой деятельности - в основном на стадии планирования - в экономике, при проектировании предприятий, разработке расписаний движения транспорта (авиационного и наземного), разработке военных операций и др. Для линейной функции и линейных условий удается задачу нахождения экстремума решить (по крайней мере, теоретически) полностью за конечное (хотя, возможно, и очень большое - например, в экономике) число шагов. Для произвольной нелинейной функции и столь же произвольных связей между ними задача оптимизации (т.е. нахождения экстремума) далеко не всегда может быть решена даже при применении самых современных компьютеров. Достаточно глубоко развита здесь теория лишь в случае, когда оптимизируемая функция и уравнения, задающие ограничения на переменные, являются выпуклыми функциями, такими задачами занимается так называемое выпуклое программирование (кстати, слово “программирование”, как и в случае линейного программирования, не имеет прямого отношения к программированию на алгоритмических Функция, экстремум (максимум или минимум) которой нужно найти, в линейном программировании предполагается линейной и потому имеет следующий вид Здесь C0,C1,C2,...CN - некоторые вещественные числа, причем C0 называется свободным членом, а C1,C2,...,CN - коэффициентами линейной функции F от переменных X1,X2,....,XN, звездочкой ‘*’ в компьютерной литературе и языках программирования принято обозначать операцию умножения. Эти переменные можно рассматривать как точку (X1,X2,...XN) в N-мерном векторном пространстве R N, для которой значения отдельных переменных являются координатами. Ясно, что свободный член C0 при поиске точек экстремума можно не учитывать (а потому просто отбросить его), хотя, конечно, на само значение функции в точке экстремума он влияет. Далее, достаточно научиться для произвольных линейных функций находить точки экстремума только одного типа (точки минимума или точки максимума). Пусть мы умеем, например, находить точки максимума, а нам нужно найти точки минимума для функции F=F(X1,X2,...XN). Тогда рассмотрим вместо функции F функцию -F, она тоже линейна и в тех точках, где -F достигает максимума, исходная функция F, очевидно, достигает минимума. Решение задачи линейного программирования - это не одно число, а набор чисел (X1,X2,...XN), его иногда еще называют оптимальным планом.

Ограничения или условия, которым должны удовлетворять переменные X1, X2,..XN в задаче линейного программирования, задаются линейными уравнениями или неравенствами.

Линейные уравнения - это соотношения вида где A1,A2,...AN и B - некоторые вещественные числа (среди них некоторые могут быть равны нулю), причем A1,A2,...AN называются коэффициентами уравнения, а B свободным членом (или правой частью уравнения, когда B стоит в правой части уравнения).



Pages:     || 2 | 3 | 4 | 5 |   ...   | 7 |
 


Похожие работы:

«Roland Легкий способ бросить пить: Добрая книга; Москва; 2007 ISBN 978-5-98124-191-8 Оригинал: Allen Carr, “Easy Way to Control Alcohol” Перевод: Юлия Шпакова Вероника Венюкова Аннотация Аллен Карр, разработавший собственный способ избавления от никотиновой зависимости, ныне известный всему миру как Легкий способ бросить курить, применил свой новаторский метод и к проблеме алкоголизма. В книге Легкий способ бросить пить он развенчивает иллюзии, которые окружают проблему алкоголизма и изображают...»

«Григорьева В.Ю. Попевки стезка, скачек и опромет в теоретических руководствах и певческих рукописях знаменного роспева (2-я половина XV – XX вв.) Среди попевок 2-го, 6-го и 8-го гласов есть несколько, имеющих чрезвычайно близкую графику: это семейство1 скачеков (менший, средний, ) и стезки2 (наиболее употребительные болший, или полной варианты её графики:,, ). Данные попевки мы относим к одному семейству на основании близости графики3, вместе они группируются и в древнерусских теоретических...»

«Клиппинг ключевых публикаций с упоминанием Уралсиб Кэпитал в российских и зарубежных СМИ 05.02-11.02.2011 Общество с ограниченной ответственностью Ул. Ефремова, 8, Москва, Россия, 119048 УРАЛСИБ Кэпитал Телефон: +7 (495) 788 0888 Факс: +7 (495) 785 1206 Дата: 07.02.2011 Источник: Ведомости Автор: Игорь Цуканов Доводы Изосимова Гендиректор Vimpelcom Ltd. Александр Изосимов считает слияние с Wind Telecom лучшим вариантом расширения бизнеса. А через два-три года компания сможет платить и больше...»

«УТВЕРЖДАЮ Декан математического факультета _2013 г. Учебно-методический комплекс по дисциплине СТОХАСТИЧЕСКИЙ АНАЛИЗ Для студентов 3 курса Направление подготовки 010200.62 Математика и компьютерные науки Профиль подготовки Математическое и компьютерное моделирование Математический анализ и приложения Квалификация (степень) Бакалавр Форма обучения Очная Обсуждено на заседании Составитель: кафедры функционального к.ф.м.н., доцент анализа и геометрии 2.07.2013 г. Протокол № 8 _ Е.М.Ершова Зав....»

«ГОСУДАРСТВЕННЫЙ СТАНДАРТ СОЮЗА ССР КАБЕЛИ, ПРОВОДА, ШНУРЫ И КАБЕЛЬНАЯ АРМАТУРА Маркировка, упаковка, транспортирование и хранение Cable, wires, cord and armature. Marking, packing, carriage and storage ОКСТУ 3500* _ * Введено дополнительно. Изм. N 1. Cрок действия с 01.07.83 до 01.07.93* _ * Ограничение срока действия снято постановлением Госстандарта России от 30.03.92 N 318 (ИУС N 6 1992 год). ВВЕДЕН В ДЕЙСТВИЕ постановлением Государственного комитета СССР по стандартам от 15 ноября 1982 г. N...»

«Проект Сказки Кота Мурлыки. Н.П. Вагнер – ученый и литератор. Скажи мне, век молодой, премудрый, до всего доходящий своим умомразумом: будут ли новые люди любить друг друга и будет ли весь дом людской на этой любви как на камне крепком, построен. Кот Мурлыка. Авторы проекта: учащиеся 7б класса МОУ СОШ №5 г. Карпинска Руководитель проекта: Евсеева Лидия Леонидовна, классный руководитель, учитель информатики и математики. г. Карпинск, 2010 год СОДЕРЖАНИЕ Введение...6 1. Биография Н.П....»






 
© 2013 www.knigi.konflib.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.