WWW.KNIGI.KONFLIB.RU

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

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


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

«Brian D Bunday, B.Sc., Ph.D., F.S.S., F.I.M.A. School of Mathematical Sciences, University of Bradford Edward Arnold Б. Банди ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Перевод с ...»

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

Б. Банди

ОСНОВЫ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Basic Linear

Programming

Brian D Bunday,

B.Sc., Ph.D., F.S.S., F.I.M.A.

School of Mathematical Sciences, University of Bradford

Edward Arnold

Б. Банди

ОСНОВЫ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

Перевод с английского О.В. Шихеевой

Под редакцией В.А. Волынского

МОСКВА «РАДИО И СВЯЗЬ» 1989 ББК 32.973 Б23 УДК 519.852 (420) Редакция переводной литературы Банди Б.

Б23 Основы линейного программирования: Пер. с англ. - М.: Радио и связь, 1989. - 176 с.: ил.

ISBN 5-256-00186-8.

В книге английского автора освещены основные положения и методы линейного программирования.

Рассмотрены симплекс-метод и его реализация на ЭВМ, проблема вырожденности, анализ чувствительности и двойственный симплекс-метод, транспортная задача, задача о назначении, двойственность в линейном программировании и др. Алгоритмы решения различных задач линейного программирования реализованы на языке Бейсик, причем программы несложно перевести на такие языки, как Фортран или Паскаль.

Для инженерно-технических работников, связанных с применением линейного программирования.

Б 1602011000-042 141.89 ББК 32. 046 (01)- Производственное издание

БАНДИ БРАЙАН

ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Заведующая редакцией О. В. Толкачева Редактор М. Г. Коробочкина Художественный редактор А. С. Широков Обложка художника В. Н. Забайрова Технический редактор О. А. Гришкина Корректор Г. Г. Казакова ИБ № Подписано в печать с оригинала-макета 11.01.89. Формат 60x88/16. Бумага Тип. № 2. Гарнитура "Пресс-роман". Печать офсетная. Усл. печ. л. 10,78.

Усл. кр.-отт. 11,52. Уч.-изд. л. 10,51. Тираж 50 000 экз. (1 завод: 1 - 25 000 экз.).

Изд. №22183. Заказ № 6622. Цена 70 к.

Издательство "Радио и связь". 101000 Москва, Почтамт, а/я Ордена Октябрьской Революции и ордена Трудового Красного Знамени МПО "Первая Образцовая типография имени А. А. Жданова" Союзполиграфпрома при Государственном комитете СССР по делам издательств, полиграфии и книжной торговли.113054 Москва, Валовая, ©B D Bunday ©Перевод на русский язык, предисловие и примечания редактора перевода, ISBN 5-256-00186-8 (рус.) дополнительный список литературы.

ISBN 0-7131-3509-3 (англ.) Издательство "Радио и связь", Оглавление Предисловие редактора перевода

ДОПОЛНИТЕЛЬНЫЙ СПИСОК ЛИТЕРАТУРЫ

ПРЕДИСЛОВИЕ

ГЛАВА 1 ОСНОВНЫЕ ИДЕИ

1.1. ВВЕДЕНИЕ

1.2. ГРАФИЧЕСКОЕ РЕШЕНИЕ ДВУХМЕРНЫХ ЗАДАЧ

1.3. СТАНДАРТНАЯ ФОРМА ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.............. 1.4. ОБОБЩЕНИЕ НА СЛУЧАЙ n ПЕРЕМЕННЫХ

1.5. ОСНОВНЫЕ РЕЗУЛЬТАТЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1.6. УПРАЖНЕНИЯ

ГЛАВА 2. СИМПЛЕКС-МЕТОД

2.1. СИМПЛЕКС-МЕТОД ПРИ ЗАДАННОМ НАЧАЛЬНОМ ДОПУСТИМОМ

БАЗИСНОМ РЕШЕНИИ

2.2. РЕАЛИЗАЦИЯ СИМПЛЕКС-МЕТОДА НА ЭВМ

2.3. ПОРОЖДЕНИЕ НАЧАЛЬНОГО БАЗИСНОГО ДОПУСТИМОГО РЕШЕНИЯ........... 2.4. ПОЛНОЕ ИЗЛОЖЕНИЕ СИМПЛЕКС-МЕТОДА

2.5. ПРОБЛЕМЫ ВЫРОЖДЕНИЯ

2.6. УПРАЖНЕНИЯ

ГЛАВА 3 АНАЛИЗ УСТОЙЧИВОСТИ РЕШЕНИЯ

3.1. ОБРАЩЕНИЕ БАЗИСА И СИМПЛЕКС-МНОЖИТЕЛИ

3.2. ЧТО ПОЛУЧАЕТСЯ ПРИ ИЗМЕНЕНИИ ЗАДАЧИ

3.3. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД

3.4. УПРАЖНЕНИЯ

ГЛАВА 4 ТРАНСПОРТНАЯ ЗАДАЧА

4.1. ПОСТАНОВКА ЗАДАЧИ И ЕЕ РЕШЕНИЕ

4.2. АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО УЛУЧШЕНИЯ ПЛАНА

4.3. ДИСБАЛАНС И ВЫРОЖДЕННОСТЬ В ТРАНСПОРТНОЙ ЗАДАЧЕ

4.4. ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ НА ЭВМ

4.5. УПРАЖНЕНИЯ

ГЛАВА 5 ЗАДАЧА О НАЗНАЧЕНИЯХ

5.1. ВВЕДЕНИЕ

5.2. МЕТОД РЕШЕНИЯ МАКА

5.3. РЕАЛИЗАЦИЯ МЕТОДА МАКА НА ЭВМ

5.4. УПРАЖНЕНИЯ

ГЛАВА 6 УЛУЧШЕННЫЙ СИМПЛЕКС-МЕТОД

6.1. УЛУЧШЕННЫЙ СИМПЛЕКС-АЛГОРИТМ

6.2. ИНИЦИАЛИЗАЦИЯ АЛГОРИТМА

6.3. ЕЩЕ РАЗ О ВЫРОЖДЕННОСТИ

6.5. УПРАЖНЕНИЯ

ГЛАВА 7. ДВОЙСТВЕННОСТЬ В ЛИНЕЙНОМ ПРОГРАММИРОВАНИИ

7.1. ПРЯМАЯ И ДВОЙСТВЕННАЯ ЗАДАЧИ

7.2. ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

7.3. АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ С ТОЧКИ ЗРЕНИЯ ДВОЙСТВЕННОСТИ

7.4. УПРАЖНЕНИЯ

РЕКОМЕНДАЦИИ ДЛЯ ДАЛЬНЕЙШЕГО ЧТЕНИЯ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

ОТВЕТЫ К УПРАЖНЕНИЯМ

Предисловие редактора перевода Линейное программирование как раздел исследования операций имеет почти сорокалетнюю историю. Внедрение вычислительной техники дало значительный толчок исследованиям в этой области математики. Был разработан ряд алгоритмов решения задач линейного программирования, а в последующие годы были созданы программы и пакеты программ преимущественно для больших ЭВМ. Основная масса литературы по линейному программированию в нашей стране выпущена в 60 - 70-е годы. Исследования в этой области (как теоретические, так и прикладные) продолжаются и в настоящее время. Однако книг по приложениям линейного программирования, учитывающих появление новых алгоритмических языков, а также микроЭВМ и персональных ЭВМ, практически нет.

Предлагаемая читателям книга восполнит этот пробел.

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

Отличительной особенностью книги является ее прикладной характер. Автор не только подробно описывает математический аппарат решения задачи, но и предлагает строгий алгоритм решения, а затем приводит программу на языке Бейсик с описанием ее особенностей. Такая форма изложения удобна и для обучения, и для получения справочного материала. Все более широкое распространение персональных ЭВМ, для которых основным языком программирования является Бейсик, будет способствовать росту интереса к программам, приведенным в книге.

Большое количество примеров значительно упрощает усвоение материала. Приведенные в конце каждой главы упражнения дают возможность самостоятельно опробовать программы, приведенные в книге, и получить практические навыки решения задач линейного программирования. Результаты, полученные на разных ЭВМ, могут несколько отличаться от приведенных в книге из-за различий в разрядности машин и программном обеспечении.

ДОПОЛНИТЕЛЬНЫЙ СПИСОК ЛИТЕРАТУРЫ

1. Юдин Д. Б., Гольдштейн Е. Г. Линейное программирование. Теория, методы и приложения. - М.: Наука, 1969. - 424 с.

2. Еремин И. И., Астафьев Н. Н. Введение в теорию линейного и выпуклого программирования. - М.: Наука, 1976. - 191 с.

3. Булавский В. А.,Звягина Р. А., Яковлева М. А. Численные методы линейного программирования/ Под ред. Л. В. Канторовича. - М.: Наука, 1977. - 367 с.

4. Раскин Л. Г., Кириченко И. О. Многоиндексные задачи линейного программирования. Теория, методы, приложения. - М.: Радио и связь, 1982. - 239 с.

ПРЕДИСЛОВИЕ

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

Математическая теория в предлагаемой книге рассматривается вполне корректно, хотя имеются и более строгие изложения. Недостаточная строгость изложения компенсируется обилием примеров. Основная задача книги - показать, каким образом теоретические идеи воплощаются в практические вычислительные процедуры, реализуемые на ЭВМ. Появление основных теоретических идей совпало по времени с появлением компьютеров, и это не случайно1. Без компьютеров невозможно использовать весь потенциал теории при решении практических задач.

Программы в книге написаны на языке Бейсик (предполагается, что читатель с ним знаком), широко распространенном на большинстве микрокомпьютеров. На многих больших ЭВМ реализованы пакеты программ, основанные на методах, обсуждаемых в настоящей книге. Однако большие ЭВМ могут быть труднодоступны, а пакеты прикладных программ часто применяются вслепую. Интерактивный режим работы микрокомпьютеров позволяет студентам лучше понять, как работают программы. Не надо думать, что эти программы нельзя улучшить. Автор был бы рад получить от читателей соображения по улучшению программ. Предлагаемые программы просты и практичны. При желании можно применить их на других ЭВМ - они легко могут быть переведены на такие языки, как Фортран или Паскаль.

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

В операторах присваивания команда LET опускается. На некоторых компьютерах эта команда обязательна и должна быть вставлена. Команда THEN включена в операторы IF...

THEN GOTO, хотя на некоторых компьютерах команды THEN или GOTO могут быть опущены. Не использовались конструкции IF... THEN... ELSE и REPEAT... UNTIL......, поскольку они применимы не на всех компьютерах. Предполагается, что нумерация массивов начинается с 0. Если нумерация массивов ЭВМ начинается с 1, необходимы некоторые изменения. В любом случае достаточно увеличить на 1 аргументы всех операторов DIM. Например, вместо DIM А (М) будет DIM А (М + 1), вместо В (К, L) - В (К + 1, L + 1) и т. д. Может быть, читатели найдут более элегантные изменения. Приводимые численные результаты получены на ЭВМ PET. На некоторых ЭВМ, работающих с числами другой точности, результаты могут не воспроизводиться идентично, однако различия должны возникать лишь в последних, несущественных знаках.

Автор выражает благодарность друзьям, коллегам и студентам, внесшим вклад в эту книгу. Многие задачи были решены студентами на экзаменах университета г. Брэдфорда.

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

Автор благодарен К. Маку за полезные и содержательные беседы о его методе решения задачи назначения и подходах к программированию этого метода. В заключение автор Это утверждение ошибочно, так как идеи линейного программирования были разработаны еще до появления ЭВМ (см., например, Канторович Л. В. Математические методы в организации и планировании производства Л.: ЛГУ, 1939). - Прим. ред.

благодарит В. Хантер, превратившую беспорядочную рукопись в аккуратно перепечатанный текст.

Брайан Банди

ГЛАВА 1 ОСНОВНЫЕ ИДЕИ



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


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

«ЭлиТнАя генеТиКА, КАчеСТвенные СеМенА и пРофеССионАлЬныЙ СеРвиС 2 Марк лефорт Руководитель Российского филиала Уважаемые клиенты, входя в состав агропромышленной группы, семенная компания Маисадур Семанс предлагает вам новый каталог гибридов кукурузы и подсолнечника. Мы расширяем нашу команду, чтобы быть ближе к вам и всегда помогать в получении лучших результатов с использованием наших продуктов и сервиса. наш успех и сотрудничество основано на 4 направлениях нашей деятельности, в которых мы...»

«20-ое Декабря Введение Поздравляем Вас с выбором труб с соединениями VAM. Соединения VAM начали разрабатываться в начале 1960-х гг. для технологических решений, требующих надежных герметизирующих свойств и эксплуатационных характеристик. С тех пор семейство соединений VAM росло и изменялось, отвечая потребностям рынка с множеством областей применения. Мы ответственно и вдумчиво подходим к проектированию и производству соединений VAM, стремясь предоставить конечному пользователю резьбовое...»

«УТВЕРЖДЕНО на заседании Ученого совета факультета социологии председатель Ученого совета _ А.Ю. Чепуренко 25 июня 2013 г. протокол № 8 ОТЧЕТ по результатам самообследования основной профессиональной образовательной программы высшего профессионального образования по направлению 040100.68 Социология уровня магистра Основание для проведения самообследования: Приказ ректора от 28.03.2013 № 6.18.1-01/2803-07 Москва 2013 Отчет по результатам самообследования профессиональной образовательной программы...»

«ВЫРЕЖЬТЕ И НАКЛЕЙТЕ В УДОБНОМ МЕСТЕ ВЫРЕЖЬТЕ И НАКЛЕЙТЕ В УДОБНОМ МЕСТЕ РЕГИСТРАЦИОННАЯ КАРТОЧКА ИЗДЕЛИЯ Заводской номер двигателя Модель двигателя Марка и модель оборудования, на котором установлен двигатель _ Ф.И.О. лица, ответственного за эксплуатацию оборудования _ Наименование предприятия (организации) Адрес предприятия (организации) _ Телефон предприятия _ Дата ввода двигателя в эксплуатацию Пожалуйста, заполните Регистрационную карточку и направьте ее своему дистрибьютору по...»

«Схема территориального планирования Верхнеуслонского муниципального района Положения ТОМ 1 ПОЯСНИТЕЛЬНАЯ ЗАПИСКА Генеральный директор Файзуллин И.Э. Заместитель Генерального директора Закиров Д.И. по техническим вопросам Главный архитектор фирмы Асадуллин И.Ш. Начальник АПМ-5 Романова И.Ю. Главный архитектор проекта Маржохова Л.Б. КАЗАНЬ 2010 2 Содержание Введение 1. Цели и задачи Схемы территориального планирования Верхнеуслонского муниципального района 2. Современное состояние территории...»

«Ангара САМОРУКОВА, Надежда ФЕЙТ Социально-экономическая трансформация Румынии Эволюция национальной экономики Румынии после 1990 года напрямую зависела от хода рыночных преобразований, жесткости мер по макроэкономической стабилизации, от преодоления хронического антагонизма между задачами подавления инфляции и экономическими интересами хозяйствующих субъектов. Пик экономического спада пришелся в Румынии на 1990—1992 годы. Валовой внутренний продукт (ВВП) сократился за три года почти на 30% (в...»

«Основная образовательная программа высшего профессионального образования Направление подготовки: 220400.62 — Управление в технических системах утверждено приказом Минобрнауки России от 17 сентября 2009 г. № 337 ФГОС ВПО утвержден приказом Минобрнауки России от 22 декабря 2009 г. № 813 Квалификация (степень) выпускника — бакалавр Нормативный срок освоения программы — 4 года Форма обучения — очная. Екатеринбург, 2012 СОДЕРЖАНИЕ 1. Профиль направления подготовки 220400 – Управление в технических...»

«Анализ моделей научно-технического прогресса как фактора экономического развития М.Н. Чечурина Факультет мировой экономики и международных отношений МГТУ, кафедра международных экономических отношений Аннотация. В статье анализируются модели научно-технического прогресса с экзогенным характером прогресса, т.е. вызванным внешними фактами, независимыми от переменных состояния экономики, и эндогенным техническим прогрессом, т.е. внутренне присущим экономике. Кроме того, рассматривается...»

«Межвузовский сборник трудов молодых ученых, аспирантов и студентов Выпуск 1, часть 1 ОБЩИЕ И КОМПЛЕКСНЫЕ ПРОБЛЕМЫ ТЕХНИЧЕСКИХ И ПРИКЛАДНЫХ НАУК Омск – 2004 УДК 378 ББК 74.58 М 43 Межвузовский сборник трудов молодых ученых, аспирантов и студентов. – Омск: Издательство СибАДИ, 2004. – Вып. 1. – Ч. 1. Общие и комплексные проблемы технических и прикладных наук. – 277 с. Настоящий межвузовский сборник трудов молодых ученых, аспирантов и студентов подготовлен по инициативе Совета молодых ученых при...»

«УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПРИРОДОПОЛЬЗОВАНИЕ Специальность 080109 Бухгалтерский учет, анализ и аудит Чебоксары – 2009 Основы природопользования. Учебно-методический комплекс для специальности Бухгалтерский учет, анализ и аудит (080109). Составитель: старший преподаватель, Л.А. Карягин. – Чебоксары: Батыревский филиал ФГОУ ВПО Чувашский государственный университет имени И.Н.Ульянова. 2 СОДЕРЖАНИЕ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ СОДЕРЖАНИЯ ДИСЦИПЛИНЫ...»






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

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