Книги, рекомендованные членами сообщества
|
|
Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 2005. - 128 с.
В пособии отражен многолетний опыт чтения лекций и проведения практических занятий по линейному программированию. Основное внимание уделено симплексному методу и его реализации наиболее экономным способом при помощи таблиц Гаусса. Рассмотрены случаи сведения симплексного метода к наглядному геометрическому способу. Начальный план транспортной задачи строится методом наименьших тарифов, что обеспечивает быстрое получение оптимального плана. Структура книги позволяет обойтись без учебника так как каждый параграф содержит краткую, но достаточную теоретическую информацию.
Для студентов всех форм обучения на факультетах, для которых математика не является профилирующей дисциплиной.
Ознакомиться (djvu/rar, 858 кб) ifolder.ru
|
 |
Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2005. - 407 с.
В учебном пособии представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого планирования и управления, элементы теории игр и массового обслуживания. Рассмотрены некоторые вопросы применения ЭВМ для решения задач математического программирования. Приводится большое количество экономических задач с решениями и для самостоятельной работы. Для студентов экономических вузов, экономистов и лиц, занимающихся самообразованием.
Скачать издание 2005 года (djvu/rar, 3,6 Мб) rghost.ru || ifolder
Скачать издание 2002 года (на мой взгляд, идентичное) (djvu/rar, 5,75 Мб) ifolder.ru
|
Несколько книг по наводке
 |
Банди Б. Основы линейного программирования: Пер. сангл. - М.: Радио и связь, 1989. - 176 с: ил.
В книге английского автора освещены основные положения и методы линейного программирования. Рассмотрены симплекс-метод и его реализация на ЭВМ, проблема вырожденности, анализ чувствительности и двойственный симплекс-метод, транспортная задача, задача о назначении, двойственность в линейном программировании и др. Алгоритмы решения различных задач линейного программирования реализованы на языке Бейсик, причем программы несложно перевести на такие языки, как Фортран или Паскаль.
Для инженерно-технических работников, связанных с применением линейного программирования.
Ознакомиться (djvu/rar, 1,76 мб) ifolder.ru || mediafire
|
 Таха, Хемди А. Введение в исследование операций, 7-е издание.: Пер. с англ. - М.: Издательский дом "Вильямс", 2005. - 912 с: ил.
Исследование операций ориентировано на решение практических задач, которые можно описать с помощью математических моделей. В книге представлены основные разделы теории исследования операций: математическое программирование (линейное и нелинейное, детерминированное и стохастическое), теория принятия решений и теория игр, теория управления запасами, теория массового обслуживания, имитационное моделирование. Книга может служить учебным пособием по теории и практическому применению методов исследования операций. Каждая тема начинается с вводного материала, доступного студентам первых курсов, далее уровень изложения постепенно повышается и рассчитан уже на студентов старших курсов и аспирантов. В конце каждой главы приводится набор комплексных задач, связанных с излагаемой темой, которые значительно углубляют и расширяют ее.
Написанная без излишнего академизма (но достаточно строго) книга будет полезна широкому кругу читателей: студентам, аспирантам и преподавателям высших учебных заведений, экономистам, инженерам, разработчикам программного обеспечения и т.д.
Скачать((djvu/rar, 8,11 Мб) ifolder.ru || Рапида
К этой книге прилагается программа "Tora", позволяющая делать расчеты (симплекс-метод, транспортные, сетевые задачи и т. д.). Скачать (300 кб) rghost.ru || ifolder
В комплекте с этой книгой идет диск с шаблонами Excel. Скачать (4, 29 мб) ifolder || fayloobmennik.net || f-bit.ru Книги по собственно линейному программированию
| Ашманов С. А. Линейное программирование. - М.: Наука. Главная редакция физико-математической литературы, 1981.- 340 с.
В книге излагаются основные разделы теории и численные методы решения задач линейного программирования. Значительное место уделяется качественному исследованию свойств содержательных моделей методами линейного программирования. Основной материал сопровождается упражнениями теоретического характера.
Скачать (djvu/rar,3.32 Мб) ifolder.ru || mediafire
|
 |
А.С. Барсов Что такое линейное программирование. - Госдарственное издательство физико-математической литературы, 1959, 104 с. (Популярные лекции по математике, вып. 33)
В книге дается постановка общей задачи линейного программирования, методы ее решения и приложения к конкретным экономическим задачам. Рассматривается применение теории линейного программирования к решению транспортных задач при минимуме стоимости и минимуме времени перевозок, а также намечены пути решения задачи с учетом обоих факторов.
Книга рассчитана на математиков, инженеров и экономистов, занимающихся вопросами математического планирования, в частности применением автоматических цифровых вычислительных машин к этим вопросам.
Скачать (djvu/rar, 1,29 Мб) ifolder.ru || mediafire || Рапида
|
 |
Булдаев А.С. Прямые методы решения задачи линейного программирования. - Иркутск, 2000. - 25 с.
Булдаев А.С. Двойственные методы решения задачи линейного программирования. - Иркутск, 2000. - 28 с.
Методическое пособие по выполнению контрольных работ для студентов математических и экономических специальностей.
Скачать (djvu/rar, 233 кб) ifolder.ru || fayloobmennik.net || rapidshare.com
|
 |
Васильев Ф. П., Иваницкий А. Ю. Линейное программирование. - М.: Изд-во «Факториал», 1998. - 176 с.
В книге дается строгое изложение основ теории линейного программирования с использованием минимального аппарата математического анализа и линейной алгебры, без привлечения теории многогранных множеств и теорем отделимости. Симплекс-метод излагается полно и строго, включая так называемый вырожденный случай. На базе симплекс-метода строится теория двойственности, доказывается ряд важных теорем линейного программирования (существование решения, теорема Фаркаша, неравенство Хоффмана и др.). Излагаются теория устойчивости для общей задачи линейного программирования, основные методы регуляризации для решения некорректных задач.
Для студентов вузов математических и экономических специальностей, а также для специалистов в области оптимизации..
Скачать (djvu/rar, 2,18 Мб) ifolder.ru || mediafire
|
 |
Гасс С. Линейное программирование.- М.:Физматгиз, 1961 - 303 с.
Книга посвящена систематическому изложению и обоснованию вычислительных методов линейного программирования. Монография представляет собой обработанный курс лекций для аспирантов высшей сельскохозяйственной школы. Отсюда и построение книги, характер изложения материала, обилие примеров и упражнений. Из основных методов линейного программирования здесь подробно изложены только симплексный метод и его модификация. Значительно меньше внимания и места уделяется так называемому двойственному симплексному методу. В книге приводится ряд практических рекомендаций, позволяющих упростить применение изложенных в ней алгоритмов к решению конкретных задач. Усвоение описанных методов и алгоритмов не требует специальной математической подготовки. Все вопросы, выходящие за рамки элементарного курса математики, вынесены в отдельную главу.
Скачать (djvu/rar, 3,62 Мб) ifolder.ru || mediafire.com || libgen.info
|
 |
Гасс С. Путешествие в Страну Линейного Программирования. Пер. с англ. Ю. II. Сударева. Предисл. Ю. В. Овсненко. М., "Мир", 1973. - 176 стр. с илл. (В мире науки и техники)
Почему самые разные специалисты вынуждены прибегать к математическим методам оптимального управления и, в частности, к линейному программированию? Как от сугубо практической задачи перейти к ее математической модели? Как соотносится эта модель с реальной действительностью? Каковы возникающие при этой трудности? На все эти вопросы в доступной н занимательной форме отвечает в настоящей книге крупный американский ученый С. Гасс. уже известный советскому читателю по своей монографин «Линейное программирование».
Книга представляет интерес для самого широкого круга читателей-от школьников старших классов до руководителей предприятий и организаций.
Ознакомиться (djvu/rar, 2.81 Мб) ifolder.ru || mediafire.com || libgen.info
|
 |
Данциг Д. Линейное программирование, его применения и обобщения. - М., Прогресс, 1966. - 600 с.
На Западе Данцига считают основоположником линейного программирования. так как развитие этой днсциплины в США фактически началось с разработки им в конце 40-х годов знаменитого симплекс-метода для численного решения основной задачи линойпого программирования. Монография Данцига удачно сочетает в себе предельно элементарное изложение основных, исходных вопросов линейного программирования, которое будет доступно даже совсем неискушенному в математике читателю, с главами, посвященными таким глубокий и математически тонким теориям, как принцип разложения или дискретное (целочисленное) программирование. Эту книгу можно, с известным основанием, считать своего рода энциклопедией линейного программирования (на год издания), в которой содержится в той или иной форме описание большинства основных вопросов, относящихся к этой дисциплине.
Скачать (djvu/rar,7,85 Мб) ifolder.ru || mediafire.com
|
 |
Палий И. А. Линейное программирование. Учебное пособие / И. А. Палий. - М.: Эксмо, 2008. - 256 с. - (Техническое образование).
Рассматриваются следующие темы: построение математических моделей задач линейного программирования, графическое решение задач с двумя переменными, симплекс-метод, теория двойствеиностн. метод потенциалов решения транспортной задачи, паросочетания. потоки в сетях, венгерский алгоритм решения задач о назначениях и транспортной задачи.
Изложение теоретического материала сопровождается большим количеством подробно разобранных примеров решения задач, что облегчает усвоение доказательств теорем и работы алгоритмов.
Для студентов технических и социально-экономических специальностей вузов всех форм обучения.
Книга найдена
Ознакомиться (djvu/rar, 3.35 Мб) ifolder.ru || mediafire.com
|
 |
Ромакин М.И. Элементы линейной алгебры и линейного программирования. М., Высшая школа, 1963. - 278 с.
Матрицы. Векторные пространства. Системы линейных уравнений. Выпуклые множества. Системы линейных неравенств. Тождественные преобразования и неотрицательные решения линейных систем. Общая задача линейного программирвоания. Графический метод. Симплексный метод. Практические задачи, решаемые методами линейного программирования
В пособии, содержатся образцы решенных задач, а также упражнения и вопросы для самопроверки, что делает его пригодным для студентов-заочников.
Для студентов инженерно-экономических специальностей технических вузов.
Ознакомиться (djvu/rar, 4.09 Мб) ifolder.ru || mediafire.com
|
 |
Солодовников А. С., Бабайцев В. А., Браилов А. В. Математика в экономике.Учебник. том 1 - М.: Финансы и статистика, 2000, 224 c.
Первая часть курса охватывает вопросы линейной алгебры и ее приложений в экономике. В учебнике подробно изложены следующие вопросы: арифметические векторы и системы линейных уравнений, матрицы и определители, линейные экономические модели, элементы аналитической геометрии, метод наименьших квадратов, решение общей задачи линейного программирования, теория двойственности.
Для преподавателей и студентов экономических вузов и факультетов, бизнес-школ, колледжей.
Скачать (djvu/rar,2.19 MB) ifolder.ru || || mediafire.com
|
 |
Д. Б. Юдин, Е. Г. Гольштейн Задачи и методы линейного программирования. - М. Советское радио, 1961. - 492 с.
Книга является первым в отечественной литературе систематическим изложением теоретических основ, методов и приложений новой математической дисциплины - линейного программирования. Основное внимание здесь обращено на обоснование и описание вычислительных алгоритмов, которые доводятся до расчетных схем и иллюстрируются примерами.
Книга предназначена для широкого круга специалистов - математиков, инженеров и экономистов с повышенной математической прдготовкой.
Скачать (djvu/rar, 7,47 Мб) ifolder.ru или mediafire
|
Книги по математическому программированию и исследованию операций
 |
Акулич И. Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов.- М.: Высш. шк., 1986.- 319 с, ил.
Пособие написано в соответствии с программой курса "Математические методы исследования операций". Рассматриваются задачи линейного, нелинейного и динамического программирования. Изложен материал, позволяющий получить довольно полное представление о возможностях практического использования математического программирования при решении конкретных экономических задач. Это пособие предназначено прежде всего для тех. кто самостоятельно изучает указанные вопросы и желает приобрести необходимые навыки в решении практических задач. В начале каждого параграфа приводятся определения, формулы, а также методические указания, необходимые для решения задач; затем дается подробное решение типовых задач с краткими пояснениями теоретических положений. В каждом параграфе приводятся задачи для самостоятельного решения.
Скачать (djvu/rar, 2,65 Мб) ifolder.ru || f-bit.ru
|
 |
Акулич И.Л. Математическое программирование в примерах и задачах. Лань, 2011. 352 с. ISBN 978-5-8114-0916-7.
В учебном пособии рассматриваются задачи линейного, нелинейного и динамического программирования. Приведены определения, формулы, а также методические указания, необходимые для решения задач; даны решения типовых задач, показаны возможности использования в этих целях различных пакетов прикладных программ. В конце каждого параграфа приведены задачи для самостоятельного решения.
Учебное пособие предназначено для студентов, аспирантов и преподавателей вузов, изучающих экономико-математические методы и модели и их использование при решении практических задач.
Скачать (PDF, 16.4 Мб) rusfolder.com || rghost.ru
|
 |
Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. - М.: ИНФРА-М, 2003. - 444 с. - (Серия «Высшее образование»).
Учебное пособие подготовлено в соответствии с требованиями государственного образовательного стандарта и содержит учебные материалы и методику решения широкого спектра экономических задач. В методике реализован новый подход к проведению практических занятий с использованием компьютерных технологий обучения в сочетании с программными средствами решения задач.
Для студентов экономических вузов и преподавателей.
Скачать (6,6 Мб doc) ifolder.ru || mediafire
|
 |
Аронович А.Б., Афанасьев М.Ю., Суворов Б.П. Сборник задач по исследованию операций. М., Изд-во МГУ, 1997. - 256 с ISBN 5-211-03766-9
В учебное пособие включен материал по основным разделам курси "Исследование операций" - линейному программированию, задачам транспортного типа, системам массового обслуживания, системам управления запасами, моделям сетевой оптимизации и т.д
Покаждой теме даются теоретический материал и большое количество задач
Для преподавателей, аспирантов и студентов экономических вузов.
Скачать (divu, 2.09 Мб) ifolder.ru || mediafire.com
|
 |
Бережная Е.В., Бережной В.И. Математические методы моделирования экономических систем: Учеб. пособие. - 2-е изд., перераб. и доп. - М.: Финансы и статистика, 2006. - 432 с: ил.
Рассматривается моделирование экономических систем с использованием марковских случайных процессов, моделирование систем массового обслуживания, методы и модели корреляционно-регрессионного анализа и прогнозирования временных рядов экономических показателей. Приводятся оптимизационные методы и модели в управлении экономическими системами, линейное, динамическое, параметрическое и целочисленное программирование, а также транспортные задачи линейного программирования, теория игр и принятие решений.
Для преподавателей, аспирантов, студентов экономических вузов и факультетов, менеджеров.
Скачать (8,35 Мб pdf) ifolder.ru || f-bit.ru
|
 |
Вентцель Е.С. Введение в иссследование операций. - М., Советское радио, 1964. - 390 с.
В книге излагаются основы науки исследования операций, занимающейся способами рациональной организации целенаправленной человеческой деятельности. Изложение предмета ведется в основном на материале задач, связанных с боевым применением техники. Однако математические методы обоснования рациональных решений излагаются так, что могут быть приложены в любой области практики. Материал изложен в популярной, общедоступной форме. Книга рассчитана на широкий круг читателей: инженеров, аспирантов, конструкторов, научных работников, студентов химических и технических вузов.
Скачать (djvu/rar, 8, 43 мб) ifolder.ru || Рапида
|
 |
Вентцель Е.С. Исследование операций. - М.: Советское радио, 1972 г. - 552 с.
В книге рассматриваются основные понятия и методологические принципы исследования операций, математические методы оптимизации (линейное, динамическое программирование, теория игр и статистических решений), а также методы математического моделирования операций. Большое внимание уделяется прикладной теории марковских случайных процессов (с приложениями в области теории массового обслуживания, теории надежности) и математическому описанию процессов, протекающих в сложных, многоэлементных системах (метод динамики средних). Рассматриваются методы статистического моделирования операций на ЭЦВМ и основы метода сетевого планирования. Изложение ведется на уровне, вполне доступном читателю, знакомому с обычным вузовским курсом математики и с элементами теории вероятностей. Излагаемые методы иллюстрируются большим количеством примеров из разных областей практики.
Книга рассчитана на широкий круг читателей - инженеров, экономистов, научных работников и хозяйственных руководителей, интересующихся применением математики к обоснованию оптимальных решений.
Скачать (djvu/rar, 4, 4 Мб) ifolder.ru || f-bit.ru || narod.ru
|
 |
Вентцель Е. С. Исследование операций: задачи, принципы, методология.- 2-е изд., стер - М.І Наука. Гл. ред. физ.-мат. лит., 1988.-208 с- (Пробл. науки и техн. прогресса).- ISBN 5-02-013900-9.
Популярно излагаются основы исследования операций - науки о выборе разумных, научно обоснованных решений во всех областях человеческой деятельности. Главное внимание уделяется не математическому аппарату, а вопросам методологии: постановке задач, выбору математических моделей, осмыслению результатов расчета. Применяемый в книге математический аппарат несложен и не выходит за пределы обычного втузовского курса математики, в тех редких случаях, когда автору волей-неволей приходится выходить за рамки этого курса, необходимые сведения даются в тексте. Книга рассчитана на широкий круг читателей: инженеров, аспирантов, конструкторов, научных работников, студентов экономических и технических вузов.
Содержание: Предмет и задачи исследования операций, Разновидности задач исследования операций и подходов к их решению, Линейное программирование, Динамическое программирование, Марковские случайные процесы, Теория массового обслуживания, Статистическое моделирование случайных процессов, Игровые методы обоснования решения.
Скачать 2 издание (1988) (djvu/rar, 3,43 мб) ifolder.ru || f-bit.ru || depositfiles.com
Скачать 1 издание (1986 год) (pdf/rar 2,1 мб) ifolder.ru || narod.ru
|
 |
Волков И.К., Загоруйко Е.А. Исследование операций: Учеб для вузов / Под ред. В.С. Зарубина, А П. Крищенко. - М.: Иэд-во МГГУ им. Н.Э. Баумана. 2000 - 436 с (Сер Математика в техническом университете. Вып. XX).
Исследование операций аккумулирует те математические методы, которые используются для принятия обоснованных решений в различных областях человеческой деятельности. В учебной литературе эта дисциплина еще не нашла полного отражения, хотя владеть ее методами современному инженеру необходимо.
В книге основное внимание уделено постановке задач исследования операций, методам их решения и критериям выбора альтернатив. Рассмотрены методы линейного и целочисленного программирования, оптимизация на сетях, марковские модели принятия решений, элементы теории игр и имитационного моделирования. Значительное число примеров поможет при изучении материала. Содержание учебника соответствует курсу лекций, который авторы читают в МГТУ им. Н.Э. Баумана.Для студентов технических университетов. Может быть полезен преподавателям, аспирантам и инженерам.
|
 |
Грешилов А.А. Прикладные задачи математического программирования: Учебное пособие. - 2-е изд. - М.: Логос, 2006. - 288 с: ил.
Рассмотрен широкий круг задач математического программирования в различных областях производства, экономики и менеджмента, повседневной жизни, а также в сфере разработки компьютерных игр. Представлены линейное программирование, сетевые (поточные) задачи, основы динамического программирования и теории игр. Изложены современные подходы к развитию методов решения задач математического программирования. Даны краткий математический словарь и перечень математических терминов.
Для студентов высших учебных заведений, получаюших образование по направлениям и специальностям техники и технологии, экономики и менеджмента. Представляет интерес для широкого круга читателей, изучающих, разрабатывающих и использующих современные методы оптимизации, исследования операций и системного анализа.
Скачать (djvu/rar, 2, 62 Мб) ifolder.ru || fayloobmennik.net || rapidshare.com
|
  Исследование операций: В 2-x томах. Под ред.ред. Дж. Моудера, С. Элмаrраби.- М., Мир, 1981. - 712 с.+ 677 с., ил.
Том 1. Методологические основы и математические методы.
В первом томе приводятся теоретические основы исследования операций и ряд детерминированных и стохастических моделей, используемых для оптимизации систем. В качестве математическоrо аппарата для анализа детерминированных моделей применяются методы линейноrо, нелинейноrо, целочисленноrо и rеометрическоrо проrраммирования. при рассмотрении стохастических моделей используются методы теорий массового обслуживания и полезности, принятия решений, теории иrр, имитационноrо моделирования и динамическоrо проrраммирования.
Том 2. Модели и применения.
Второй том посвящен применению методов исследования операций для решения задач проrнозирования в промышленности, управления трудовыми ресурсами и запасами, повышения надежности и улучшения ремонта оборудоввания. Обсуждаются оптимальные способы размещения объектов, составления календарных планов, выбора наилучших проектных решений и разработки вычислительных и информационных систем. Рассматривается эффективност применения этих методов в таких сферах деятельности человека, как транспорт, здравоохранение, управление производственно-технологическими процессами.
Для специалистов в области исследования операций, теории управления, экономистов, инженеров-конструкторов, разработчиков АСУ, а также студентов соответствующих специальностей.
Скачать Том 1 (djvu/rar, 14,92 Мб) ifolder.ru || rapidshare.com || libgen.info
Скачать Том 2 (djvu/rar, 13,38 мб) ifolder.ru || rapidshare.com || libgen.info
 |
Калихман И. Л., Войтенко М. А. Динамическое программирование в примерах и задачах: Учеб. пособие.-М.: Высш. школа, !979.- 125 с, ил.
Пособие представляет собой руководство к решению задач по динамическому программированию. В нем излагаются общие принципы применения методов динамического программирования к некоторым экономическим задачам оптимизации. Рассматриваются многошаговые детерминированные модели задач оптимального распределения ресурсов, управления запасами, замены оборудования и др. Наряду с решенными примерами в пособии содержится достаточное количество задач для самостоятельного решения.
Предназначается для студентов экономических специальностей вузов.
Скачать (djvu/rar, 2,85 Мб) ifolder.ru || mediafire
|
 |
Калихман И. Л. Сборник задач по математическому программированию. Изд. 2-е, доп. и перераб. М., «Высш. школа», 1975. -270 с. с ил.
Настоящий сборник содержит примеры и задачи по курсу математического программирования. Примеры предназначены для освоения вычислительных методов, задачи, преимущественно экономического содержания, - для упражнений и приложении этих методов к экономическим исследованиям.
Большинство параграфов содержит справочный теоретический материал и подробный разбор типовых примеров.
Нет стр 133-138
Скачать (pdf/rar, 6.76 Мб) ifolder.ru || mediafire.com
Скачать (divu, 2.36 Мб) ifolder.ru || mediafire.com
|
 |
Карманов В. Г. Математическое программирование: Учеб. пособие. - 5-е изд., стереотип. - М.: ФИЗМАТЛИТ, 2004. - 264 с.
Рассматривается широкий круг вопросов, связанных с математическим программированием. Изложены теоретические основы возникающих здесь задач линейного, выпуклого и нелинейного программирования и построения численных методов для их решения. По сравнению с изданием 1986 г. в книгу включены результаты, связанные с исследованиями в области численных методов оптимизации и их применением к решению экстремальных задач, в том числе задач вырожденного типа.
Книга написана на основе лекций, которые автор читал в течение ряда лет на механико-математическом факультете и на факультете вычислительной математики и кибернетики Московского государственного университета.Четвертое издание - 2000 г.
Для студентов высших учебных заведений.
Скачать (djvu/rar, 1,66 Мб) ifolder.ru || fayloobmennik.net || libgen.info
|
 |
Катулев А. Н., Северцев Н. А., Соломаха Г. М. Исследование операций и обеспечение безопасности: прикладные задачи: Учеб. пособие для вузов / Под ред. академика РАН П.С. Краснощекова. - М.: ФИЗМАТЛИТ, 2005. - 240 с.
Книга посвящена методам принятия решений. В сборник включены статические и динамические задачи с решениями, раскрывающими основные компоненты обобщенной модели операции, подходы и принципы оценки эффективности стратегий участвующих в ней сторон, необходимые условия и методы отыскания оптимальных решений для различных условий: определенности, неопределенности в цели операции, конфликта и риска.
Для студентов старших курсов, аспирантов и других специалистов, изучающих математические методы исследования операций и обеспечения безопасности.
Скачать (djvu/rar 1,43 Мб) ifolder.ru || narod.ru || libgen.info
|
 |
Конюховский П. В. Математические методы исследования операций в экономике-СПб: Питер, 2000.-208 с: ил.-(Серия «Краткий курс»).
В пособии представлены базовые разделы курса "Математические методы исследования операций в экономике": теория линейного и нелинейного программирования, методы решения транспортных и сетевых задач, элементы дискретного (целочисленного) программирования, динамическое программирование, применение методов линейного программирования в теории матричных игр. Упор делается на изложении теоретических и практических аспектов алгоритмов решения экстремальных задач, которые формулируются на базе известных экономико-математических моделей. Отдельное внимание уделяется вопросам содержательной экономической интерпретации формальных математических понятий.
Пособие предназначено для студентов вузов, обучающих по экономико-математическим, экономическим и управленческим специальностям. Также оно может представлять интерес для специалистов, чья профессиональная деятельность связана с решением задач наилучшего выбора в условиях ограниченности ресурсов.
Скачать (djvu/rar, 4,11 Мб) ifolder.ru || mediafire
|
 |
Косоруков О.А, Мищенко А.В. Исследование операций: Учебник / Косоруков О.А., Мищенко А.В. // Под общ. ред. д.э.н., проф. Н.П. Тихомирова. - М: Издательство «Экзамен», 2003. - 448 с.
В учебнике основное внимание уделено вопросам математического моделирования экономических процессов средствами исследования операций. К этим методам в первую очередь относятся те, которые используют аппарат математического программирования, теории расписаний, теории управления запасами, теории игр, теории массового обслуживания и др. В последнее время сюда же с полным основанием можно отнести такие задачи, как управление портфелем ценных бумаг, управление финансовыми ресурсами, в том числе кредитными, управление инвестициями и др. Авторы приводят математический аппарат исследования операций (линейное программирование, симплексный метод, теория игр, целочисленное линейное программирование, динамическое программирование, сетевые модели, нелинейное программирование, основы теории массового обслуживания и др.), показывают сферы приложений методов исследования операций на наглядных примерах.
Для студентов, обучающихся по экономическим специальностям, а также специалистов, занимающихся задачами организационного управления.
Скачать (djvu/rar, 5.63 Мб) ifolder.ru || rghost.ru || libgen.info
|
 |
Костевич Л. С. Математическое программирование: Информ. технологии оптимальных решений: Учеб. пособие / Л.С. Костевич. - Мн.: Новое знание, 2003. - 424 с: ил. ISBN 985-6516-83-8.
Доступно изложено применение линейных, целочисленных, динамических, параметрических, игровых методов и алгоритмов оптимизации в информационных технологиях управления. Рассмотрены вопросы эффективного сетевого планирования, построения оптимальных маршрутов и т.д. Теоретический материал сопровождается примерами решения конкретных задач. Некоторые решения реализованы с помощью электронных таблиц Microsoft Excel.
Для студентов вузов, обучающихся по экономическим специальностям, экономистов, менеджеров.
Ознакомиться (pdf/rar, 20.37 Мб) ifolder.ru || mediafire.com
|
 |
Костюкова О.И. Исследование операций: Учеб. пособие для студ. спец. 31 03 04 «Информатика» всех форм обучения / О.И. Костюкова. Мн.: БГУИР, 2003. - 94 с: ил.
Учебное пособие составлено в соответствии с рабочей программой курса «Исследование операций». В него включены сведения об основных результатах и алгоритмах теории исследования операций. Дается представление о математическом аппарате исследования операций, рассматриваются и анализируются математические модели основных типов задач, встречающихся в приложениях.В курсе рассмотрены следующие вопросы: целочисленное линейное программирование, динамическое программирование, кратчайшие пути, потоки в сетях, линейное программирование и теория игр.
Пособие может быть рекомендовано для курсового и дипломного проектирования.
Скачать (djvu/rar, 1,5 мб) ifolder.ru || mediafire
|
 |
А. В. Кузнецов, В. А. Сакович, Н. И. Холод Высшая математика. Математическое программирование. : Учеб./Под общ. ред. А. В. Кузнецова - Минск, Выш. шк., 1994.- 286 с: ил.
Завершает комплекс учебников по дисциплине «Высшая математика». Излагаются методы решения задач линейного программирования, элементы теории двойственности, рассматриваются программирование на сетях, дискретное и выпуклое программирование, основы теорий матричных игр, динамического и параметрического программирования, даются сведения из стохастического программирования. Приводится достаточное количество примеров экономического содержания с анализом полученных результатов. Для студентов экономических специальностей вузов.
Скачать (djvu/rar, 1,53 мб) ifolder.ru || mediafire
|
 |
Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию - Мн.: Вышэйш. школа, 1978. - 256 с., ил.
Учебное пособие соответствует программе курса Математическое программирование для экономических специальностей вузов. Приводится теоретический материал, необходимый для решения практических задач. Различные приемы решения задач иллюстрируются примерами. Дано достаточное количество задач для самостоятельного решения. Все задачи снабжены ответами.
Обложка от другого издания
Скачать (divu, 3,62 Мб) ifolder.ru || mediafire.com
|
 |
Лю Б. Теория и практика неопределенного программирования / Б. Лю; Пер. с анrл.- М.: БИНОМ. Лаборатория знаний, 2005. - 416 с.: ил (Адаптивные и интеллектуальные системы)
В книrе дается подробное изложение аппарата неопределенноrо проrраммирования, включая обсуждение принципов построения соответствующих оптимизационных моделей, а также алrоритмов, обеспечивающих решение разнообразных прикладных задач с использованием этих моделей. Рассмотрены: транспортные задачи, моделирование систем управления запасами, задачи составления кормовых смесей, моделирование производственного процесса, проблемы водоснабжения, задача размещения и распределения оборудования, задача распределения капиталовложений, задача тополоrической оптимизации, задача маршрутизации движения транспорта, оптимизации резервирования, задача о критическом пути, задача составления расписания параллельно действующих машин.
Книrа ориентирована на исследователей, инженеров и студентов, специализирующихся в области исследования операций, теории систем, информатики, орrанизационноrо управления и техники.
Скачать (djvu/rar, 3,63 Мб) ifolder.ru || fayloobmennik.net || libgen.info
|
 |
Матряшин Н.П, Макеева В.К. Математическое программирование. - Харьков, «Вища школа», 1978. - 180 с.
В пособии рассматриваются наиболее распространенные математические методы решения конкретных экономических задач. Во втором издании существенно переработаны главы о теории двойственности и графическом методе решения задач линейного программирования, а также о целочисленном и параметрическом программировании. Издание содержит большое количество практических задач, которые рассматриваются на всех стадиях -от постановки до анализа их решения.
Пособие рассчитано на студентов экономических специальностей, работников экономических и плановых служб.
Скачать (2,6 Mb) ifolder.ru || mediafire
|
 |
Мину М. Математическое программирование. Теория и алгоритмы: Пер. с фр. и предисловие А. И. Штерна.-М.: Наука. Гл. ред. физ.-мат. лит., 1990.- 488 с
С единых позиций рассматриваются разделы математического программирования. Излагаются теория и алгоритмы конечномерной и бесконечномерной оптимизации, в частности методы решения задач вариационного исчисления и оптимального управления, дискретное и динамическое программирование, способы декомпозиции больших систем. Рассматриваются разнообразные приложения. Простота и наглядность изложения совмещаются со строгостью доказательств.
Для научных работником и инженеров, работающих в области прикладного математики, а также для студентов вузов.
Скачать (djvu/rar, 11мб) ifolder.ru || libgen.info
|
 |
Минюк С. А., Ровба Е. А., Кузьмич К. К. Математические методы и модели в экономике: Учеб. пособие. - Мн.: ТетраСистемс, 2002. - 432 с.
Книга состоит из 47 лекций, которые включают в себя: методы оптимизации и детерминированные экономические модели, теорию вероятностей и стохастические экономические модели, математическую статистику и экономические модели. Учебное пособие отражает содержание курсов "Теория вероятностей и математическая статистика", "Математическое программирование" и родственных им по названию, которые традиционно читаются на экономических специальностях вузов. Краткость и сжатость, а также достаточный уровень математической строгости характеризуют данную книгу. Предназначено для преподавателей и студентов экономических вузов и факультетов, колледжей.
Скачать (5.22 MB pdf) ifolder.ru || rghost.ru
|
 |
Шикин Е. В., Шикина Г. Е. Исследование операций: учеб. - М. : ТК Велби, Изд-во Проспект, 2006. - 280 с.
В учебнике рассмотрены задачи линейного и целочисленного программирования, приведены примеры и решения транспортных задач. роанализирован широкий спектр игр: матричные, биматричные, позиционные и некоторые другие игры. Отдельные главы посвящены сетям и многокритериальным оптимизационным задачам. Учебник позволяет овладеть методами количественного подхода и качественного анализа. Прикладной характер решаемых задач позволяет использовать полученные знания на практике для поиска оптимальных решений в управлении.
Для студентов, аспирантов, преподавателей вузов, а также всех интересующихся вопросами поиска оптимальных решений в управлении с помощью математических методов.
Скачать (djvu/rar, 2,77 Мб) ifolder.ru || f-bit.ru || rapidshare.com
|
 |
Е. В. Шикин, А. Г. Чхартишвили Математические методы и модели в управлении. - М., Дело, 2000. - 440 с.
Книга содержит изложение основных математических методов и моделей, используемых при выработке управленческих решений. Рассматриваются: сетевая оптимизация, линейное программирование, управление запасами, модель Леонтьева, метод анализа иерархий, методы прогнозирования, вероятностные и статистические методы, методы теории игр, основы теории управления организованными системами и некоторые другие. Книга рассчитана на студентов и преподавателей вузов, слушателей учебных программ по менеджменту и государственному управлению, руководителей разного уровня, интересующихся современными подходами к проблеме принятия решений в управлении.
Скачать (djvu/rar, 4,1 Мб) Литература по высшей (абстрактной) алгебре
Книги в основном в формате djvu. Для чтения файлов данного формата скачатьWinDjView-1.0
(885Кб) или (2,71 Мб) или страница с последней версией
См. также раздел |
|
В учебнике представлены модели линейного и целочисленного программирования, классические методы оптимизации, задачи выпуклого и динамического программирования, модели управления запасами и сетевого планирования и управления, элементы теории игр и массового обслуживания, оптимизация финансового портфеля. В книге содержится большое количество задач. Задачи с решениями представлены на протяжении всего изложения учебного материала, а задачи для самостоятельной работы приведены в конце каждой главы.
Шаг 1. Выбирайте книги в каталоге и нажимаете кнопку «Купить»;
Шаг 2. Переходите в раздел «Корзина»;
Шаг 3. Укажите необходимое количество, заполните данные в блоках Получатель и Доставка;
Шаг 4. Нажимаете кнопку «Перейти к оплате».
На данный момент приобрести печатные книги, электронные доступы или книги в подарок библиотеке на сайте
ЭБС возможно только по стопроцентной предварительной оплате. После оплаты Вам будет предоставлен доступ к
полному тексту учебника в рамках Электронной библиотеки или мы начинаем готовить для Вас заказ в типографии.
Внимание! Просим не менять способ оплаты по заказам. Если Вы уже выбрали какой-либо способ оплаты и не
удалось совершить платеж, необходимо переоформить заказ заново и оплатить его другим удобным способом.
Оплатить заказ можно одним из предложенных способов:
- Безналичный способ:
- Банковская карта:
необходимо заполнить все поля формы. Некоторые банки просят подтвердить оплату – для этого на Ваш номер телефона придет смс-код.
- Онлайн-банкинг: банки, сотрудничающие с платежным сервисом, предложат свою форму для заполнения.
Просим корректно ввести данные во все поля.
Например, для
" class="text-primary">Сбербанк Онлайн
требуются номер мобильного телефона и электронная почта.
Для " class="text-primary">Альфа-банка
потребуются логин в сервисе Альфа-Клик и электронная почта.
- Электронный кошелек: если у Вас есть Яндекс-кошелек или Qiwi Wallet,
Вы можете оплатить заказ через них. Для этого выберите соответствующий способ оплаты и заполните предложенные поля,
затем система перенаправит Вас на страницу для подтверждения выставленного счета.
И1
|Ш^ш^Я|
ШЯл
Определение показателей эффективности
многоканальной СМ О с отказами
Граф состояний С МО
лц
Предельные вероятности состояний
(формулы Эрланга)
2!
р_
А!
/I!
>
Р2
где р
Р
Р
=
/
7РО"
- "
Р/>
~7
/">*
" "
""~
^Г^О
I
/О
Я:
X/|i - интенсивность н.ир\ JKH каната
Вероятность отказа
Относительная пропускная
способность
Абсолютная пропускная
способность
Среднее число занятых
каналов
nl,/>о
Р
я!
п
Определение точки и размера заказа
в задачах управления запасами
Статическая модель без дефицита
вровень i-niac.i
3,пp.i 1ы
С
Л = nil = N / I I
2Т
НУ~Врс
Время
Оптимальный размер заказа
(формула Ушсона)
Оптимальный интервал
межд> поставками
л0 - J
\ С2
, *2 "~ количество кормов I и II, входящих в
дневной рацион. Тогда этот рацион (см. табл. 1.2) будет включать
(3*1 + 1-*2) единиц питательного вещества S\, (1-jq +2*2) единиц
вещества S2 и O"*i + ^Х2) единиц питательного вещества 5з- Так
как содержание питательных веществ S\, Si и S} в рационе должно быть не менее соответственно 9, 8 и 12 единиц, то получим
систему неравенств:
3*
! + 2x2 z 8,
(1.7)
+ 6х2 > 12.
Кроме того, переменные
xi > 0, х2 > 0.
(1.8)
Общая стоимость рациона составит (в руб.)
+
/ = 4xj 6x2(1-9)
Итак, экономико-математическая модель задачи: составить
дневной рацион X = (х\, х2), удовлетворяющий системе (1.7) и условию (1.8), при котором функция (1.9) принимает минимальное значение.^
Для формулировки задачи в общей постановке обозначим:
Xj (j = 1,2, ..., и) - число единиц корма я-го вида; 6, (/ = 1, 2, ...,
т), - необходимый минимум содержания в рационе питательного
1
вещества Sf, ay - число единиц питательного вещества 5 , в единице корма у"-го вида; с, - стоимость единицы корма у"-го вида.
Тогда экономико-математическая модель задачи примет вид:
найти такой рацион X - (х\, Х2, ..., х„), удовлетворяющий системе
(1.10)
+ am2X2+...+amnxnzbm
и условию
xi ;> 0, х2 ^ 0,..., хя > 0,
(1.11)
при котором функция
F= cix, + c2x2 +...+ с„хп
поинимает максимальное значение.
(1.12)
Общая постановка задач
21
3. Задача об использовании мощностей (задача о загрузке оборудования).
Предприятию задан план производства продукции по времени
и номенклатуре: требуется за время Г выпустить п\, П},..., nk единиц продукции Р\, Р^ ..., РЬ Продукция производится на станках
S\, .$2, > $т- Для каждого станка известны производительность ау
(т.е. число единиц продукции PJ, которое можно произвести на
станке 5/) и затраты by на изготовление продукции PJ на станке S/
в единицу времени.
Необходимо составить такой план работы станков (т.е. так
распределить выпуск продукции между станками), чтобы затраты
на производство всей продукции были минимальными.
Составим экономико-математическую модель задачи.
Обозначим \у - время, в течение которого станок /S/ будет занят изготовлением продукции PJ (i - I, 2,..., m\j = 1, 2, ..., k).
Так как время работы каждого станка ограничено и не превышает Т, то справедливы неравенства:
- "
(1.13)
x
ml + Xm2+---+xmk ^ Т.
Для выполнения плана выпуска по номенклатуре необходимо,
чтобы выполнялись следующие равенства:
+а
°11*11 + "21*21+- м1*и1 = "Ь
а
х
+а
х
Л
°12*12 + 22 22+--- т2 т2 = 2>
a
lkxlk
/j ^
+U
2kx2k+---+amkxmk =nk-
Кроме того,
zO(i = },2,...,m;j=\,2,...,k).
Xij
(1.15)
Затраты на производство всей продукции выразятся функцией
F= Ь\\Х\\ + Ь\2Х\2 +-+ bmkXmk.
(1"16)
Экономико-математическая модель задачи об использовании
мощностей примет вид: найти такое решение X = (хцрс^, -, хт/с),
22_
Глава 1
удовлетворяющее системам (1.13) и (1.14) и условию (1.15), при котором функция (1.16) принимает минимальное значение.
4. Задача о раскрое материалов.
На раскрой (распил, обработку) поступает материал одного
образца в количестве а единиц. Требуется изготовить из него /
разных комплектующих изделий в количествах, пропорциональных числам b\, bi, ...b/ (условие комплектности). Каждая единица
материала может быть раскроена и различными способами, причем использование /"-го способа (/ = 1,2, ..., п) дает <% единиц k-ro
изделия (k= 1,2, ..., /).
Необходимо найти план раскроя, обеспечивающий максимальное
число комплектов.
Составим экономико-математическую модель задачи.
Обозначим х/ - число единиц материала, раскраиваемых /-м
способом, чх - число изготавливаемых комплектов изделий.
Так как общее количество материала равно сумме его единиц,
раскраиваемых различными способами, то
ы
в.
(1.17)
Требование комплектности выразится уравнениями
Еде/ел»*** (k = 1,2, ...,/;.
(1.18)
*,>()(/ = 1,2,..., л).
(1.19)
ы
Очевидно, что
Экономико-математическая модель задачи: найти такое решение Х=(х\, Х2,..., х„), удовлетворяющее системе уравнений (1.17) -
(1.18) и условию (1.19), при котором функция F = х принимает максимальное значение.
1.3. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи.
Р е ш е н и е. Прежде всего определим всевозможные способы
распила бревен, указав соответствующее число получаемых при
этом брусьев (табл. 1.3).
Общая постановка задач
23
Т а б л и ц а 1.3
Число получаемых брусьев длиной, м
Способ
распила i
1,2
3,0
5,0
-
-
2
3
5
2
-
1
-
-
4
-
1
2
-
1
Обозначим: щ - число бревен, распиленных /-м способом
(/ = 1, 2, 3, 4); х - число комплектов брусьев.
Учитывая, что все бревна должны быть распилены, а число
брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид:
F- х-» max
при ограничениях:
, + х2 + *з + *4 = 195,
5*1 + 2х2
= 2х,
Х^
=
jX)
х,;>0(/=1,2, 3, 4»
Задачу о раскрое легко обобщить на случай от раскраиваемых
материалов.
Пусть каждая единица у"-го материала (/" = 1, 2, ..., т) может
быть раскроена п различными способами, причем использование
i-го способа (/ = 1, 2, ... , л) дает а,д единиц k-го изделия (k = 1, 2,
..., t), а запас у"-го материала равен ду единиц.
Обозначим ху - число единиц у"-го материала, раскрываемого
i-м способом.
Экономико-математическая модель задачи о раскрое в общей
постановке примет вид: найти такое решение X = (х\\, x\i, ..., х„т),
удовлетворяющее системе
п
J^xy < fly (у = 1,2,..., т),
п т
/=1у=1
24
Глава 1
и условию x,j>Q, при котором функция F = х принимает максимальное значение.
5. Транспортная задача рассмотрена в гл. 7.
1.3. Общая задача линейного программирования
Рассмотренные выше примеры задач линейного программирования позволяют сформулировать общую задачу линейного программирования.
Дана система т линейных уравнений и неравенств с п переменными
а2\х\+а22х2+...+а2„х„
a
k+l,lxl + ak+l,2x2+- -+ak+\,nxn =
a
k+2,lxl
+a
k+2,2x2+---+ak+2,nxn = bk+2>
=bm
и линейная функция
F =
с„х„
Необходимо найти такое решение системы Х= (х\, х2,
где
(1.21)
j, ..., х„),
(1.22)
при котором линейная функция F (1.21) принимает оптимальное
(т.е. максимальное или минимальное) значение.
Система (1.20) называется системой ограничений, а функция F
- линейной функцией, линейной формой, целевой функцией или
функцией цели.
Более кратко общую задачу линейного программирования
можно представить в виде:
=
£ cjxj
(или -> min)
Общая постановка задач
25
при ограничениях:
2>„х, ,уху = *,(/ = k + \,k + 2,...,m),
=l
J
X j > Q (j = l, 2, .... /; / < л) .
Оптимальным решением (или оптимальным планом) задачи линейного программирования называется решение Х= (х\, х%, ..., х,
..., х„) системы офаничении (1 20), удовлетворяющее условию
(1.22), при котором линейная функция (1.21) принимает оптимальное (максимальное или минимальное) значение.
Термины "решение" и "план" - синонимы, однако первый
используется чаще, когда речь идет о формальной стороне задачи
(ее математическом решении), а второй - о содержательной стороне (экономической интерпретации).
При условии, что все переменные неотрицательны (х/ > 0,j=l, 2,
..., л), система офаничении (1.20) состоит лишь из одних неравенств,
- такая задача линейного профаммирования называется стандартной; если система офаничении состоит из одних уравнений, то задача называется канонической1. Так, в приведенных выше примерах
задач линейного профаммирования задачи 1 и 2 - стандартные,
задача 4 - каноническая, а задача 3 - общая.
Любая задача линейного профаммирования может быть сведена к канонической, стандартной или общей задаче. Рассмотрим
вначале вспомогательную теорему.
Теорема 1.1. Всякому решению (сц, <Х2,..., а„) неравенства
a,iX}+a. = (2/3; 5/3; 2; 5) является допустимым, а при q =2,
С2 =1, т.е. ^2 = (2/3; - 7/3; 2; 1) - недопустимым.
Среди бесконечного множества решений системы выделяют
так называемые базисные решения.
Базисным решением системы т линейных уравнений с п переменными называется решение, в котором все п-т неосновных переменных равны нулю.
В задачах линейного программирования особый интерес представляют допустимые базисные решения, или, как их еще называют,
опорные планы. Число базисных решений является конечным, так
как оно равно числу групп основных переменных, не превосходящему С^ . Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным.
2.3. Найти все базисные решения системы, приведенной в задаче 2.1.
Р е ш е н и е. В задаче 2.1 было установлено, что существует
три группы основных переменных х\, х?, х\, хз; х\, х^, т.е. число
базисных решений равно 3.
Найдем первое базисное решение, взяв в качестве основных
переменные х\, Х2 и неосновных - переменные хз, Хф Приравняв
неосновные переменные нулю, т.е. при хз = Х4 = 0, получим систему уравнений в виде
х, - х2 = О,
2х! + х2 = 2,
откуда Х| = 2/3; Х2 = 2/3. Следовательно, первое базисное решение системы Х\ = (2/3; 2/3; 0; 0) - допустимое.
1
Именно такие решения представляют интерес в большинстве задач
линейного программирования.
32
Глава 2
Если взять за основные переменные х\, д/j и приравнять нулю
=
соответствующие неосновные переменные *2 *4 = 0, получим
второе базисное решение Х^ = (2/3; 0; 2/3; 0) - также допустимое. Аналогично можно найти и третье базисное решение
Х3 = (2/3; 0; 0; - 2/3) - недопустимое.*Совместная система (2.1) имеет бесконечно много решений, из
них базисных решений - конечное число, не превосходящее С™.
2.2. Выпуклые множества точек
В школьном курсе математики выпуклыми назывались многоугольники, целиком расположенные по одну сторону от прямых,
на которых лежат их стороны.
В
Рис. 2.1
Например, многоугольник на рис. 2.1, а - выпуклый, а многоугольник на рис. 2.1, б не является выпуклым (он расположен
по обе стороны от прямой ВС),
Общим определяющим свойством, которое отличает выпуклый многоугольник от невыпуклого, является то, что если взять
любые две его точки и соединить их отрезком, то весь отрезок
будет принадлежать этому многоугольнику. Это свойство может
быть принято за определение выпуклого множества точек.
Множество точек называется выпуклым, если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий
эти точки.
Согласно этому определению многоугольник на рис. 2.1, о является выпуклым множеством, а многоугольник на рис. 2.1, б
таковым не является, ибо отрезок MN между двумя его точками М
и N не полностью принадлежит этому многоугольнику.
Элементы линейной алгебры и геометрии
33
/Г71
7
Выпуклыми множествами могут быть не только многоугольники. Примерами выпуклых множеств являются круг, сектор, отрезок,
многоугольная область, куб, пирамида (рис. 2.2, а-е), многогранная область, прямая, полуплоскость, полупространство и т.п.
Выпуклые множества обладают важным свойством, которое
устанавливается следующей теоремой.
Теорема 2.2. Пересечение (общая часть) любого числа выпуклых
множеств есть выпуклое множество.
D Пусть М и N - любые две точки пересечения двух1 множеств А и В (рис. 2.3). Так как точки М и N принадлежат пересечению множеств, т.е. одновременно и выпуклому множеству А, и
выпуклому множеству В, то согласно определению выпуклого
множества все точки отрезка MN будут принадлежать как множеству А, так и множеству В, т.е. пересечению этих множеств. А это и означает,
что пересечение данных множеств есть
выпуклое множество.
Среди точек выпуклого множества
можно выделить внутренние, граничные
и угловые точки.
Точка множества называется внутренней, если в некоторой ее окрестности2
содержатся точки только данного множества.
Рис. 2.3
Точка множества называется граничной,
если в любой ее окрестности содержатся как точки, принадлежащие
данному множеству, так и точки, не принадлежащие ему.
1
Для доказательства теоремы ограничимся случаем двух множеств.
Под окрестностью точки плоскости (пространства) подразумевается круг
(шар) с центром в этой точке.
2
34
Глава 2
Особый интерес в задачах линейного программирования представляют угловые точки.
Точка множества называется угловой (или крайней), если она не
является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.
D
На рис. 2.4 приведены примеры различных точек многоугольника: внутренней (точки М), граничной (точка N) и угловых
(точки А, В, С, D, E). Точка А - угловая, так как для любого отрезка, целиком принадлежащего многоугольнику, например, отрезка АР, она не является внутренней; точка А - внутренняя для
отрезка KL, но этот отрезок не принадлежит целиком многоугольнику.
Для выпуклого множества угловые точки всегда совпадают с
вершинами многоугольника (многогранника), в то же время для
невыпуклого множества это не обязательно. Так, на рис. 2.5 точка
А является вершиной невыпуклого многоугольника, но не угловой
(она является внутренней для отрезка KL, целиком принадлежащего этому многоугольнику).
К
D
Рис. 2.5
Элементы линейной алгебры и геометрии
35
Множество точек называется замкнутым, если включает все
свои граничные точки. Множество точек называется ограниченным, если существует шар (круг) радиуса конечной длины с центром в любой точке множества, который полностью содержит в
себе данное множество; в противном случае множество называется неограниченным.
Если фигура ограничена только прямыми или их отрезками,
то число ее угловых точек конечно; в случае криволинейности
границ фигура содержит бесконечно много угловых точек, что
позволяет сделать следующее определение.
Выпуклое замкнутое множество точек пространства (плоскости),
имеющее конечное число угловых точек, называется выпуклым многогранником (многоугольником), если оно ограниченное, и выпуклой многогранной (многоугольной) областью, если оно неограниченное.
До сих пор рассматривались выпуклые множества точек на
плоскости и в пространстве. Аналитически такие точки изображаются упорядоченной парой чисел (х\, хз) или упорядоченной
тройкой чисел (х\, х^, *з)- Понятие точки можно обобщить, подразумевая под точкой (или вектором) упорядоченный набор п
чисел Х= (х\, *2> > *я)> в котором числа х\, х-^, ..., х„ называются
координатами точки (вектора). Такое обобщение имеет смысл, так
как если взять какой-либо экономический объект, то для его характеристики двух-трех чисел обычно бывает недостаточно и необходимо взять п чисел, где п > 3.
Множество всех точек Х = (х\, Х2,..., х„) образует n-мерное точечное (векторное) пространство. При п > 3 точки и фигуры «-мерного
пространства не имеют реального геометрического смысла и все исследования объектов этого пространства необходимо проводить в
аналитической форме. Тем не менее оказывается целесообразным и в
этом случае использовать геометрические понятия для облегчения
представлений об объектах л-мерного пространства.
2.3. Геометрический смысл решений
неравенств, уравнений и их систем
Рассмотрим решения неравенств.
Теорема 2.3. Множество решений неравенства с двумя переменными
а
\\х\ + al2x2£bi
(2.2)
Глава 2
36
является одной из двух полуплоскостей, на которые вся плоскость
делится прямой а\\х\ + 012*2 = °ь включая и эту прямую, а другая
полуплоскость с той же прямой есть множество решений неравенства
«11*1
_1_
х>
L.
«12*2 - "l-
УЪ *5\
V"^/
D Для произвольной абсциссы х\ ордината точки М (рис. 2.6),
лежащей на прямой а\\х\ + а\2х2 = Ь\, при условии 012 * 0, есть
а\\
Ъ\
,.
Ъ\
а\\
= -- xj +-- , т.е. координаты точки м х\\ -- jcj +-
-
a
\2
«12
\2
«12
а
Рис. 2.6
Через точку М проведем прямую, параллельную оси Qx2. Тогда
для любых точек Р и Q этой прямой, расположенных выше и ниже точки М, т.е. в верхней и нижней полуплоскостях, будут верны
и
Х
Х
или
-°11
неравенства х2п>х2м
2Р- 10
*2 ^--х\+-^«12 " «12
*2 ^ --*i +-- При условии «и >0 неравенства преобразуют«12
«12
ся соответственно к виду «njq + а\2х2 > Ь\ и а\\х\ + а\2х2 < Ь\, т.е
координаты всех точек верхней полуплоскости удовлетворяют
неравенству (2.2), а нижней полуплоскости - неравенству (2.3). В
случае а\2 < 0, наоборот, координаты всех точек верхней полу-
Элементы линейной алгебры и геометрии
37
плоскости удовлетворяют неравенству (2.3), а координаты нижней
полуплоскости - неравенству (2.2).
2.4. Построить множество решений неравенства:
а) Зх, - 4х2 + 12 <; 0; б) 3*i - 2х2 £ 0.
Р е ш е н и е. В соответствии с теоремой 2.3, множество решений неравенства есть полуплоскость.
а) Построим границу полуплоскости - прямую 3xi - 4x2+
+ 12 = 0, найдя точки ее пересечения с осями координат А (~4;0)
и В (0;3) на рис. 2.7, а.
/)(-4;0)
-3 -2 -
1
2
3
х,
Рис. 2.7
Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не
лежащую на ее границе - построенной прямой. Если неравенство
выполняется в контрольной точке, то оно выполняется и во всех
точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. И наоборот, в
случае невыполнения неравенства в контрольной точке, оно не
выполняется во всех точках полуплоскости, содержащей контрольную точку, и выполняется во всех точках другой полуплоскости.
В качестве контрольной точки удобно взять начало координат
О (0;0), не лежащее на построенной прямой. Координаты точки О
не удовлетворяют неравенству: 3 - 0 - 4 - 0 + 12 < О, следовательно,
решением данного неравенства является нижняя полуплоскость,
не содержащая контрольную точку О. Искомая полуплоскость
выделена штриховкой.
38
Глава 2
б) Построим границу полуплоскости - прямую Зх\ - 4x2 = Q по
двум точкам. Одной из этих точек является начало координат на рис.
2.7, б (в уравнении прямой отсутствует свободный член), а другую
точку берем на прямой произвольно, например, А (2; 3) на рис. 2.7, б.
В качестве контрольной возьмем, например, точку 5(1; 0). Самую
"простую" точку О (0; 0) здесь в качестве контрольной брать не
следует, ибо она лежит на построенной прямой. Так как координаты контрольной точки В (1; 0) удовлетворяют неравенству, т.е.
3 1 - 2 0 > 0, то решением данного неравенства является нижняя (правая) полуплоскость, содержащая эту точку >
Учитывая, что множество точек, удовлетворяющих уравнению
«п*1 + 012*2 + - + «1/А*и ~Ь\
(2-4)
при /1=3, является плоскостью, а при я>3 - ее обобщением в
«-мерном пространстве - гиперплоскостью, теорему 2.3 можно
распространить на случай трех и более переменных.
Теорема 2.4. Множество всех решений линейного неравенства с п
переменными
«12*2 + является одним из полупространств, на которые все пространство
делится плоскостью или гиперплоскостью (2.4), включая и эту плоскость (гиперплоскость).
Рассмотрим множество решений систем неравенств.
Теорема 2.5 Множество решений совместной системы т линейных неравенств с двумя переменными
anxi +al2x2
При построении областей решений систем неравенств могут
встретиться и другие случаи: множество решений - выпуклая многоугольная область (рис. 2.9, а); одна точка (рис. 2.9, б); пустое множество, когда система неравенств несовместна (рис. 2.9, в).
б
X,
Рис. 2.9
Теорема 2.6. Множество решений совместной системы т линейных неравенств с п переменными является выпуклым многогранником
(выпуклой многогранной областью) в n-мерном пространстве.
Рассмотрим множество допустимых решений системы т линейных уравнений с л переменными.
Теорема 2.7. Множество всех допустимых решений совместной
системы т линейных уравнений с п переменными (т < п) является
выпуклым многогранником (выпуклой многогранной областью) в
n-мерном пространстве.
Доказательство этой теоремы приведено в гл. 3. Здесь же проиллюстрируем теорему на примерах.
2.6. Построить множество допустимых решений:
а) уравнения 2х\ + 3*2 = 6;
Элементы линейной алгебры и геометрии
41
btj + 3x2 + *з = 12,
б) системы уравнений
Xj + X2 - XQ = 1.
Убедиться в справедливости теоремы 2.7.
Р е ш е н и е, а) Рассмотрим частный случай системы линейных
уравнений (т < п), содержащей п = 2 переменных, т.е. состоящей
из одного уравнения (т = 1). Множество всех решений данного
уравнения есть прямая 2х\ + 3x2 = 6, а множество допустимых
решений (при дополнительном условии xj > 0, х^ > 0) - точки
отрезка АВ (рис. 2.10, а), который можно рассматривать как частный случай выпуклого многогранника с двумя угловыми точками
Л(3; 0) и 5(0; 2).
О
1
2
5
6
Рис. 2.10
б) Построить непосредственно множество решений системы
уравнений с я = 4 (я > 3) переменными не представляется возможным. В данном случае (когда разность между числом переменных и уравнений л - т ~ 2) можно поступить так: разобьем
все переменные на основные, например х^ и х^ (определитель из
коэффициентов при них отличен от нуля), и неосновные
(свободные) переменные х\ и х-^, и вместо множества решений
системы построим множество значений их неосновных переменных (выполнить это возможно, так как их всего две).
С этой целью выразим основные переменные через неосновные:
= 12-2*, -Зх 2 ,
42
Глава 2
Так как рассматриваются допустимые значения переменных,
т.е. *| £ 0, *2 £ 0, хз > О, Х4> 0, то
12 - 2х, - Зх2 £ О,
-1 + х, + х2 £ О,
>0, X 2 S O .
(I)
(II)
(Ill, IV)
Решениями полученной таким образом системы неравенств
являются точки четырехугольника ABCD на рис. 2.10, б с четырьмя угловыми точками Л(0; 1), 5(0; 4), С(6; 0), Д1; 0) (рекомендуем убедиться в этом самому читателю).
В данном примере графические построения проведены не в пространстве всех переменных, а в плоскости двух неосновных переменных х\, X}. Но так как любой паре неосновных переменных х\, Х2
соответствуют определенные значения основных переменных х^, х$, а
следовательно, одно и только одно решение данной системы уравнений, то каждой точке построенного четырехугольника ABCD соответствует одна и только одна точка множества допустимых решений
системы уравнений, представляющего в данном случае выпуклый
многогранник в четырехмерном пространстве>
Между допустимыми базисными решениями и угловыми точками
множества допустимых решений системы линейных уравнений существует взаимнооднозначное соответствие. Это утверждение будет
доказано в гл. 3, здесь же ограничимся примером.
2.7. Убедиться в том, что между базисными решениями систем,
приведенных в задаче 2.6, и угловыми точками множества их
допустимых решений существует взаимнооднозначное соответствие.
Р е ш е н и е, а) Система, состоящая из одного уравнения, имеет два допустимых базисных решения. Первое базисное решение
Х\ = (3; 0) получается из уравнения, если в качестве основной
взять переменную х\, а неосновной - переменную х-^ = 0. Второе
базисное решение Х^ = (0; 2) получается, если основная переменная *2> а неосновная - переменная jq = 0. Из рис. 2.10, а следует,
что допустимым базисным решениям Х\ и Х^ однозначно соответствуют угловые точки отрезка АВ - множества допустимых решений уравнения.
б) Для системы, приведенной в задаче 2.6, б, можно получить
четыре допустимых базисных решения (рекомендуем читателю най-
Элементы линейной алгебры и геометрии
43
ти их самостоятельно): Xi = (1; 0; 10; 0), Х2 = (6; 0; 0; 5), Х3 = (0; 1;
9; 0), ^4 = (0; 4; 0; 3). Из рис. 2.10, б следует, что этим допустимым базисным решениям однозначно соответствуют точки D(\;
0), С(6; 0), Л(0; 1) и В(0; 4) многоугольника ABCD - множества
допустимых решений системы уравнений >
УПРАЖНЕНИЯ
В задачах 2.8 и 2.9 решить системы уравнений.
= 3,
„„ [Зх,+х 2 -х 3 2.8.
2.9
3*1 - 4^2 + 6x3 = 5.
Х -
= -4,
В задачах 2.10 и 2.11 найти базисные решения.
" + а4(а2Л"2 + ссзА"з) = а^! + а 2 а 4 А г 2 + а 3 а 4 А г 3 .
Основы методов линейного программирования
47
Обозначив /| = ct|, (2 = а 2 а 4 , t3 = а3а4 , получим окончательно
X = tiXi + t2X2 + /3-^3 >
где?, S: 0,/2 £ 0,/3 £ 0 и /, + /2 + t3 = 1.
Рис. 3.2
Таким образом точка X есть выпуклая линейная комбинация угловых точек (вершин) треугольника
Из теоремы 3.1 следует, что выпуклый многогранник порождается своими угловыми точками или вершинами: отрезок - двумя
точками, треугольник - тремя, тетраэдр - четырьмя точками и
т.д. В то же время выпуклая многогранная область, являясь неограниченным множеством, не определяется однозначно своими
угловыми точками: любую ее точку нельзя представить в виде
выпуклой линейной комбинации угловых точек.
3.2. Свойства задачи
линейного программирования
В разд. 1.3 были рассмотрены различные формы задачи линейного программирования и показано, что любая задача линейного
программирования может быть представлена в виде общей, канонической или стандартной задачи.
В данном разделе будем рассматривать каноническую задачу
(1.20) - (1.22), в которой система ограничений есть система уравнений (2.1).
Для обоснования свойств задачи линейного программирования
и методов ее решения целесообразно рассмотреть еще два вида
записи канонической задачи.
Глава 3
48
Матричная форма записи:
F = СХ -> max (min)
(3.6)
АХ = В,
(3.7)
при ограничениях
(3.8)
где
г
= (с\,С2,...,с„); А =
«11
«12
«1л
«21
«22
«2я
/7___*
/7__-i
„
;л =
;* =
П
Г1
Y
^2
А
Здесь С - матрица-строка, А - матрица системы, X - матрица-столбец переменных, В - матрица-столбец свободных членов.
Векторная форма записи:
(3.9)
F = СХ -» max (min)
при ограничениях
Р2х2+...+Рпхп = Р,
(ЗЛО)
(3.11)
X>Q,
1
где СХ - скалярное произведение векторов С = (q, C2, ..., с„) и
Х=(х\, х2, ..., х„), векторы
«21
«22
.«/nl^
V«m2-
«2я
состоят соответственно из коэффициентов при переменных и
свободных членов.
Векторное неравенство X > 0 означает, что все компоненты
вектора А1 неотрицательны, т.е. Jty > 0, у = 1,2,...,я.
1
Скалярным произведением СХ двух векторов С = (сь с2, ..., с„) и JT =
= (KI, x2, ..., х„) называется число, равное сумме произведений соответствующих координат этих векторов: СХ = clx\ + с2х2 + ... + с„х„.
Основы методов линейного программирования
49
В гл. 2 была сформулирована, но не доказана в общем виде
следующая теорема.
Теорема 3.2. Множество всех допустимых решений системы ограничений задачи линейного программирования является выпуклым.
П Пусть X, =(Jcj1US"),...,41)) и Х2 = (хр>,*<2)>-.*12)) -два
допустимых решения задачи (3.6) - (3.8), заданной в матричной
форме. Тогда АХ\ = В и АХ2 = В. Рассмотрим выпуклую линейную
комбинацию решений Х\ и Х^, т.е.
X = сцЛ"] + о.2Х2 при <Х| > 0,а2 > 0 и а, + а 2 = 1,
и покажем, что она также является допустимым решением системы (3.7). В самом деле
АХ = А(о.{Х{ + а.2Х2) = а[АХ1 + (l - а.{}АХ2 = щВ + (1 - а,)Д = В,
т.е. решение X удовлетворяет системе (3.7). Но так как Х\ >0,
Х2 >Q, 0ц > О, а 2 > 0 , то и X >0, т.е. решение X удовлетворяет и
условию (3.8).И
Итак, доказано, что множество всех допустимых решений задачи
линейного программирования является выпуклым, а точнее (если
учесть изложенное в гл. 2), представляет выпуклый многогранник
или выпуклую многогранную область, которые в дальнейшем будем
называть одним термином - многогранником решений.
Ответ на вопрос, в какой точке многогранника решений возможно оптимальное решение задачи линейного программирования, дается в следующей фундаментальной теореме.
Теорема 3.3. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает максимальное1
значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное значение более чем в одной
угловой точке, то она принимает его в любой точке, являющейся
выпуклой линейной комбинацией этих точек.
D Будем полагать, что многогранник решений является ограниченным. Обозначим его угловые точки через Х\, Х^, ..., Хр, а
1
Формулировка теоремы остается такой же и при отыскании минимального значения линейной функции.
50
Глава 3
оптимальное решение -
через X* (рис.3.3). Тогда
F\X*\ ^ Л^А") для всех точек X многогранника решений. Если X* - угловая
точка, то первая часть теоремы доказана.
Предположим, что X* не
является угловой точкой,
тогда на основании теоремы 3.1 X* можно представить как выпуклую линейную комбинацию угловых
точек многогранника решений, т.е.
Рис. 3.3
X* = с^А", + а.гХ2+...+арХ,
=1.
а
Так как F(X) - линейная функция, получаем
F(X*) =
(3.12)
В этом разложении среди значений ДА}) (/ = 1, 2, ..., р) выберем максимальное. Пусть оно соответствует угловой точке
Xk (l < k < р) ; обозначим его через М, т.е. ДА^) = М. Заменим в
выражении (3.12) каждое значение этим максимальным значением М. Тогда, учитывая, что а у > 0, У]ау = 1, найдем ЛАГ* | <
< щМ +а2М+...+арМ - Л/У^а у = М. По предположению А* -
7=1
оптимальное
решение,
поэтому,
с
одной
стороны,
ЛАГ* j > Л^) = М, но, с другой стороны,
доказано, что
Л"А"*) <, М, следовательно, F(X"\ = М = F(Xk), где А^ - угловая
Основы методов линейного программирования
51
точка. Итак, существует угловая точка Х^, в которой линейная
функция принимает максимальное значение.
Для доказательства второй части теоремы допустим, что F(X)
принимает максимальное значение более чем в одной угловой
точке, например, в точках Х\, Х^, ..., Xq. где 1<д<р; тогда
Пусть X - выпуклая линейная комбинация этих угловых точек, т.е.
9
X = alX] +a.2X2+...+a(/Xq, а у > О (j = \,2,...,q), £а у =1.
y=i
В этом случае, учитывая, что функция F(X) - линейная, получим
F(X) = F(a.1X1 + а2*2-к..+суд = о,/1^,) + a2F(X2)+...
9
...+aqF(Xg\ = СХ|Л/ + а2Л/+...+а(?Л/ = Л/У^а 7 = М,
т.е. линейная функция F принимает максимальное значение в
произвольной точке X, являющейся выпуклой линейной комбинацией угловых точек Х\, Xi, ..., XqM
З а м е ч а н и е. Требование ограниченности многогранника
решений в теореме является существенным, так как в случае
неограниченной многогранной области, как отмечалось в теореме 3.1, не каждую точку такой области можно представить
выпуклой линейной комбинацией ее угловых точек.
Доказанная теорема является фундаментальной, так как она
указывает принципиальный путь решения задач линейного программирования. Действительно, согласно этой теореме вместо
исследования бесконечного множества допустимых решений для
нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений.
Следующая теорема посвящена аналитическому методу нахождения угловых точек.
Теорема 3.4. Каждому допустимому базисному решению задачи
линейного программирования соответствует угловая точка много-
52
Глава 3
гранника решений, и наоборот, каждой угловой точке многогранника
решений соответствует допустимое базисное решение.
D Пусть X = (х\, Х2, .., хт; 0, 0, ..., 0) - допустимое базисное
решение системы ограничений (3.10) задачи, в котором первые т
компонент - основные переменные, а остальные п - т компонент - неосновные переменные, равные нулю в базисном решении (если это не так, то соответствующие переменные можно
перенумеровать). Покажем, что X - угловая точка многогранника
решений.
Предположим противное, т.е. что X не является угловой точкой. Тогда точку X можно представить внутренней точкой отрезка, соединяющего две различные, не совпадающие с X, точки
Xi=(4\$,...,}i$; О, 0,...,0)и
(2}
X 2 -(х
Л
- V-ч
Л
х®-" и0" "» >«/>
0 0)
>Х№
2 " » */»
другими словами, - выпуклой линейной комбинацией точек Х\ и
Xi многогранника решений, т.е.
X = а{Х{ + с^Л^,
(3.13)
где ai > 0, <х2 > 0, а.1 + сс2 = 1 (полагаем, что ctj * 0, <х2 * 0, ибо в
противном случае точка Л"совпадает с точкой Х\ или Х^).
Запишем векторное равенство (3.13) в координатной форме:
Поскольку х
S 0, х
> 0 (у = 12,...,л), а, > 0, а 2 > 0, то из
последних п-т равенств следует, что jcj^j = 0, x^|j = 0, ...,
ху = 0, х\" = 0, т.е. в решениях Х\, Х^ и X системы уравнений
(3.10) значения п-т компонент равны в данном случае нулю. Эти
компоненты можно считать значениями неосновных переменных.
Но значения неосновных переменных однозначно определяют зна-
Основы методов линейного программирования
53
чения основных, следовательно, х\" = лг| " = х\, ..., х% = х$ = х2.
Таким образом, все п компонент в решениях X, Х\ и Xi совпадают, и значит, точки Х\ и Aj сливаются, что противоречит допущению. Следовательно, X- угловая точка многогранника решений.
Докажем обратное утверждение. Пусть X = (х\, x-i, ..., хт; О, О,
..., 0) - угловая точка многогранника решений и первые ее т
координат положительны. Покажем, что X - допустимое базисное решение.
Если векторы Р\, PI, ..., Рт линейно независимы1, то ранг г
матрицы А, составленной из компонент этих векторов, равен т,
т.е. определитель \А\ * О, следовательно, переменные х\, х^, ..., хт
являются основными, и решение X = (х\, Х2, ..., хт; О, 0, ..., 0) -
базисное, допустимое, т.е. утверждение доказано.
Предположим противное, т.е. векторы Р\, PI, ..., Рт линейно
зависимы; тогда в равенстве
a.iPl+...+a.mPm+...+anPn=0
(3.14)
хотя бы один из коэффициентов а (,..., ат,..., а„ отличен от нуля.
Умножим почленно равенство (3.14) на множитель ц > 0:
ца1^+...+цссот/"т+...+мал/"л =0.
(3.15)
Подставив координаты угловой точки X многогранника решений в систему ограничений (ЗЛО), получим
PlXi+...+Pmxm+...+Pnxn = P.
(3.16)
Равенство (3.15) почленно сложим с равенством (3.16), а затем
вычтем его из равенства (3.16). Получим
1
-+Pm(xm + цат)+...+^(х„ + ца„) = Р.
(3.17)
- - .+Рт(хт - цат)+.. .+?„(*, - цал) - Р.
(3.18)
Векторы PI, Р2, ..., Р„ (они же столбцы матрицы А) называются линейно зависимыми, если можно подобрать такие числа aj,a 2 ,...,a n , не
равные нулю одновременно, что а.\Р\ + а2/2+---+ося^)л =0, где 0 -
нулевой вектор (состоящий из нулей). В противном случае векторы
PI, ?2, ..., Р„ называются линейно независимыми.
54
Глава 3
Сравнивая полученные равенства (3.17), (3.18) с равенством
(3.16), заключаем, что при любом ц системе ограничений (3.10)
удовлетворяют решения Х\ = (х\ + цсц, ..., хт + цат; О, О, ..., 0) и
Хг =(х,-ца, ..., хт-рат;0, О, ..., 0).
Поскольку Xj > О (/" = 1, 2, ..., л), то можно подобрать ц. настолько малым, что все компоненты решений Х\ и Х^ будут неотрицательными. В результате Х\ и Xi будут различными допустимыми решениями задачи (3.9) - (3.11). При этом, как легко видеть, решение -(Х1 + Х2) = (х},х2,...,хт; О, 0, ..., 0) = X, т.е. точка X лежит на отрезке (в данном случае в его середине), расположенном в многограннике решений. Значит X не является угловой
точкой, что противоречит условию. Следовательно, наше допушение неверно, т.е. векторы Р\, PI, -, Рт линейно независимы и
X - допустимое базисное решение задачи (3.9) - (З.И).И
Из теорем 3.3 и 3.4 непосредственно вытекает важное следствие: если задача линейного программирования имеет оптимальное
решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.
Итак, оптимум линейной функции задачи линейного программирования следует искать среди конечного числа ее допустимых базисных
решений.
Глава 4
ГЕОМЕТРИЧЕСКИЙ МЕТОД
РЕШЕНИЯ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
В гл. 2 и 3 было доказано, что множество допустимых решений
(многогранник решений) задачи линейного программирования
представляет собой выпуклый многогранник (или выпуклую
многогранную область), а оптимальное решение задачи находится, по крайней мере, в одной из угловых точек многогранника
решений.
Рассмотрим задачу в стандартной форме (1.4)-(1.6) с двумя
переменными (п = 2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число
переменных я больше числа уравнений т на 2, т.е. п - т - 2.
F=0
Рис. 4.1
56
Глава 4
Пусть геометрическим изображением системы ограничений
является многоугольник ABCDE (рис. 4.1). Необходимо среди точек этого многоугольника найти такую точку, в которой линейная
функция F = clxl + с2х2 принимает максимальное (или минимальное) значение.
Рассмотрим так называемую линию уровня линейной функции
F, т.е. линию, вдоль которой эта функция принимает одно и то же
фиксированное значение а, т.е. F = а, или
с,х, + с2х2 = а.
(4,1)
Линии уровня широко используются, например, на картах
прогноза погоды, где извилистые линии - так называемые изотермы есть не что иное, как линии уровня температуры Т = с.
Еще более простым примером линий уровня являются параллели
на географической карте. Это линии уровня широты.
Предположим, надо найти самую северную точку какой-либо
области, например страны или материка. Это будет точка, имеющая наибольшую широту, т.е. точка, через которую проходит параллель (линия уровня) с самой большой широтой (уровнем).
Именно так и надо поступать при геометрическом решении
задач линейного программирования. На многоугольнике решений
следует найти точку, через которую проходит линия уровня функции F с наибольшим (если линейная функция максимизируется)
или наименьшим (если она минимизируется) уровнем.
Уравнение линии уровня функции (4.1) есть уравнение прямой
линии. При различных уровнях а линии уровня параллельны, так как
их угловые коэффициенты определяются только соотношением между коэффициентами с\ и с-^ и, следовательно, равны. Таким образом,
линии уровня функции F - это своеобразные "параллели", расположенные обычно под углом к осям координат.
Важное свойство линии уровня линейной функции состоит в
том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую сторону -
только убывает.
Пусть имеются три линии уровня
F = c,x, + с2х2 =а\, (I)
F = с,*, + с2х2 = а2 (II)
F = clxl+c2x2 =я 3 >
Геометрический метод решения задач
57
причем линия II заключена между линиями I и III. Тогда а\ < ai <
< Яз
или а
а
\ > °2 > З-
В самом деле, на штриховой линии (перпендикулярной к линиям уровня на рис. 4.2) уровень является линейной функцией, а
значит, при смещении в одном из направлений возрастает, а в
другом - убывает.
F=a2
О
Рис. 4.2
Для определения направления возрастания рекомендуется
изобразить две линии уровня и определить, на которой из них
уровень больше. Например, одну из линий можно взять проходящей через начало координат (если линейная функция имеет
вид F = с,*! + с2х2, т.е. без свободного члена, то это соответствует нулевому уровню). Другую линию можно провести произвольно, так, например, чтобы она проходила через множество
решений системы ограничений. Далее, определив направление
возрастания линейной функции (обозначим его вектором q),
найдем точку, в которой функция принимает максимальное
или минимальное значение, подобно тому как на карте находится самая северная или самая южная точка (на рис. 4.1 -
это точка С или А).
58
Глава 4
4.1. Решить геометрически 1-ю задачу из разд. 1.2:
F = 2х\ + Зх2 -> max
при ограничениях:
fx,+3x 2 <18,(1)
2х, + х2 < 16, (И)
х2 <5, (III)
Зх,
<21,
х, > 0 , х 2 >0.
О
Рис. 4.3
Р е ш е н и е. Изобразим многоугольник решений (аналогично
тому, как в задаче 2.5) на рис. 4.3. Очевидно, что при F- 0 линия
уровня 2х\ + 3x2= 0 проходит через начало координат (строить ее
не обязательно). Зададим, например, F = 6 и построим линию
уровня 2х| + 3^2 = 6. Ее расположение указывает на направление
возрастания линейной функции (вектор q). Так как рассматриваемая задача - на отыскание максимума, то оптимальное решение -
в угловой точке С, находящейся на пересечении прямых I и II,
59
Геометрический метод решения задач
т.е. координаты точки С определяются решением системы урав{х + Ъх2 = 18
нений = 4, т.е. С(6;4).
+ 2х2 £ 8,
х, > 0, х2 s 0.
4.5. F = 2х, - х2 -> min
при ограничениях:
х, + х2 > 4,
-X] + 2х2 < 2,
*! + 2х2 < 10,
х, > 0, х2 > 0.
Геометрический метод решения задач
63
4.6. F = х{ + х2 -» max
4.7. F = 2х\ - х2 -> min
при ограничениях:
при ограничениях:
х, - 4х2 - 4 <, 0,
Зх, - х2 > О,
! + х2 - 4 s 0,
f X] + х2 2 4,
J 2х, - х2 £ 2,
(-дг, - 2х2 2 -10,
х, > 0, х2 > 0.
х, £ 0, х2 S: 0.
4.8. F = х, - х2 -> max
при ограничениях:
4.9. Текст условия приведен в
задаче 1.4.
- Х\+Х2
"
[ - 2х2 < -8,
Xj
+ Х2
4.10. Текст условия приведен в
задаче 1.5.
<: 5,
X! > 0, х2 £ 0.
Задачи 4.11, 4.12 решить геометрически, предварительно приведя их к стандартной форме.
4.11.
4.12.
F = -4х, - 2х2 + х3 - х4 -> max F = x, + 2х2 + х3 - х4 - 6 -> min
при ограничениях:
при ограничениях:
- х2 + 4х3 - 2х4
= 2,
[-Х, + 5х2 + х3 + х4 + х5
! + 2х2 - х3 + 4х4 = 3,
\ 2х, - х2 + х3 - Зх4
s 0, j = 1,2,3,4.
[
= 10,
= 6,
Юх2 + х3 + 2х4 + Зх5 = 25,
Глава 5
СИМПЛЕКСНЫЙ МЕТОД
5.1. Геометрическая интерпретация
симплексного метода
В гл. 3 рассмотрены основные теоремы линейного программирования, из которых следует, что если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя
бы одной угловой точке многогранника решений и совпадает, по
крайней мере, с одним из допустимых базисных решений системы ограничений (см. теоремы 3.3, 3.4). Там же был указан путь
решения любой задачи линейного программирования: перебрать
конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор в конце концов приведет к оптимальному решению (если оно
существует), однако его практическое осуществление связано с
огромными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико.
Число перебираемых допустимых базисных решений можно
сократить, если производить перебор не беспорядочно, а с учетом
изменений линейной функции, т.е. добиваясь того, чтобы каждое
следующее решение было "лучше" (или, по крайней мере, "не
хуже"), чем предыдущее, по значениям линейной функции
(увеличение ее при отыскании максимума F -> max, уменьшение
- при отыскании минимума F-+ min).
Такой перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере.
Симплексный метод
65
Пусть область допустимых решений изображается многоугольником ABCDEGH (рис. 5.1). Предположим, что его угловая точка
А соответствует исходному допустимому базисному решению. При
беспорядочном переборе пришлось бы испытать семь допустимых
базисных решений, соответствующих семи угловым точкам многоугольника. Однако из чертежа видно, что после вершины А
выгодно перейти к соседней вершине В, а затем - к оптимальной
точке С.
v-°
ч
ч
0
Рис. 5.1
Вместо семи перебрали только три вершины, последовательно
улучшая линейную функцию.
Идея последовательного улучшения решения легла в основу
универсального метода решения задач линейного программирования - симплексного1 метода.
Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины многогранника ограничений
(называемой первоначальной) к соседней, в которой линейная
функция принимает лучшее (по крайней мере, не худшее) значение
1
Симплекс (лат. simplex - простой) - простейший выпуклый многогранник в л-мерном пространстве с п+1 вершиной (например, тетраэдр в
3-мерном пространстве); симплексом является также область допустимых
решений неравенства вида
< 1.
66
Глава 5
(по отношению к цели задачи) до тех пор, пока не будет найдено
оптимальное решение - вершина, где достигается оптимальное
значение функции цели (если задача имеет конечный оптимум).
Впервые симплексный метод был предложен американским
ученым Дж. Данцигом в 1949 г., однако еще в 1939 г. идеи метода
были разработаны российским ученым Л В.Канторовичем.
Симплексный метод, позволяющий решить любую задачу линейного программирования, универсален. В настоящее время он
используется для компьютерных расчетов, однако несложные примеры с применением симплексного метода можно решать и вручную.
Для реализации симплексного метода - последовательного
улучшения решения - необходимо освоить три основных
элемента:
способ определения какого-либо первоначального допустимого
базисного решения задачи;
правило перехода к лучшему (точнее, не худшему) решению;
критерий проверки оптимальности найденного решения.
Для использования симплексного метода задача линейного
программирования должна быть приведена к каноническому виду,
т.е. система ограничений должна быть представлена в виде уравнений. Алгоритм конкретной вычислительной реализации этих
элементов рассмотрим на примерах.
5.2. Отыскание
максимума линейной функции
В качестве первого примера рассмотрим задачу об использовании ресурсов, сформулированную в разд. 1.2 и уже решенную
геометрически в задаче 4.1.
5.1. Решить симплексным методом задачу:
F = 2х, + Зх2 -> max
при ограниченияхх, +3х 2 =£18,
*
Зх,
s21,
2
х, > 0, х2 > 0.
(5Л)
Симплексный метод
67
Р е ш е н и е. С помощью дополнительных неотрицательных
переменных перейдем к системе уравнений. В данном случае все
дополнительные переменные вводятся со знаком "плюс", так как
все неравенства имеют вид "<" [см. систему ограничений (1.26)].
Получим систему ограничений в виде:
V
Л|
I
т
"З V
JA2
I
т
V
АЗ
10
- JO,
2Х| + х2 + х4 = 16,
Х2 +
Зх, +
= 5,
(5.2)
= 21.
Для нахождения первоначального базисного решения разобьем
переменные на две группы - основные и неосновные. Так как
определитель, составленный из коэффициентов при дополнительных переменных xj, Xj, х$, л%, отличен от нуля, то (см. разд. 2.1) эти
переменные можно взять в качестве основных на первом шаге
решения задачи. При выборе основных переменных на первом
шаге не обязательно составлять определитель из их коэффициентов и проверять, равен ли он нулю. Достаточно воспользоваться
следующим правилом:
в качестве основных переменных на первом шаге следует выбрать
(если возможно) такие т переменных, каждая из которых входит
только в одно из т уравнений системы ограничений, при этом
нет таких уравнений системы, в которые не входит ни одна из
этих переменных.
68
Глава 5
Дополнительные переменные удовлетворяют этому правилу.
Если выбранные по этому правилу переменные имеют те же знаки, что и соответствующие им свободные члены в правых частях
уравнений, то полученное таким образом базисное решение будет
допустимым. В данном случае так и получилось.
I ш а г. Основные переменные: х-), х$, х$, х$.
Неосновные переменные: х\, х^.
Выразим основные переменные через неосновные:
Х^ - 10 -
Xj - ЗД^2,
. = 16 - 2х, - х-,.
х5 = 5
XL
= 21 -
(5.3)
ЗДС,
Положив неосновные переменные равными нулю, т.е. х\ = О,
JC2 = 0, получим базисное решение Х\ = (0; 0; 18; 16; 5; 21), которое является допустимым и соответствует вершине 0(0;0) многогранника OABCDE на рис. 5.2. Поскольку это решение допустимое, нельзя отбросить возможность того, что оно оптимально.
Выразим линейную функцию через неосновные переменные:
F = 2х| + Здс 2 . При решении Х\ значение функции равно F(X\).
Легко понять, что функцию F можно увеличить за счет увеличения любой из неосновных переменных, входящих в выражение
для F с положительным коэффициентом. Это можно осуществить,
перейдя к такому новому допустимому базисному решению, в
котором эта переменная будет неосновной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). При таком
переходе одна из основных переменных перейдет в неосновные, а
геометрически произойдет переход к соседней вершине многоугольника, где значение линейной функции "лучше" (по крайней
мере "не хуже"). В данном примере для увеличения F можно переводить в основные либо х\, либо х^, так как обе эти переменные
входят в выражение для Fco знаком "плюс". Для определенности
в такой ситуации будем выбирать переменную, имеющую больший коэффициент, т.е. в данном случае х^ (такое правило выбора
не всегда дает наименее трудоемкое решение, иногда имеет смысл
провести предварительные специальные оценки).
Симплексный метод
69
Система (5.3) накладывает ограничения на рост переменной х^.
Поскольку необходимо сохранять допустимость решений, т.е. все
переменные должны оставаться неотрицательными, то должны
выполняться следующие неравенства (при этом х\ = О как неосновная переменная):
х3 = 18 - Зх2 ^ 0,
о /Л
к - х\
п
*
<18/3,
х4 = 16
£
2
,
2
откуда
16/1,
ху5 = 5<; 5
/1-
Каждое уравнение системы (5.3), кроме последнего, определяет
оценочное отношение - границу роста переменной х^, сохраняющую неотрицательность соответствующей переменной. Эта
граница определяется абсолютной величиной отношения свободного члена к коэффициенту при xi при условии, что эти числа
имеют разные знаки. Последнее уравнение системы не ограничивает рост переменной *2. так как данная переменная в него не
входит (или формально входит с нулевым коэффициентом). В
этом случае условимся обозначать границу символом да. Такой же
символ будем использовать, когда свободный член и коэффициент при переменной в уравнении имеют одинаковые знаки, так
как и в этом случае нет ограничений на рост переменной.
Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член отсутствует (т.е. равен 0), а переводимая переменная имеет положительный коэффициент. И в этом случае граница обозначается символом оо. Обратите внимание, что при нулевом свободном члене и
отрицательном коэффициенте при переводимой переменной
уравнение ограничивает рост этой переменной нулем! (любое
положительное ее значение вносит отрицательную компоненту в
следующее базисное решение). Все возможные случаи, которые
возникают при оценке переменной, переводимой в основные,
перечислены в конце разд. 5.3.
Очевидно, что сохранение неотрицательности всех переменных
(допустимость решения) возможно, если не нарушается ни одна
из полученных во всех уравнениях границ. В данном примере
наибольшее возможное значение для переменной xi определяется
как *2 = п™1 (18/3; 16/1; 5/1; да} = 5. При х^ = 5 переменная xs
обращается в нуль и переходит в неосновные.
Глава 5
70
Уравнение, где достигается наибольшее возможное значение
переменной, переводимой в основные (т.е. где оценка минимальна), называется разрешающим. В данном случае - это третье
уравнение. Разрешающее уравнение будем выделять рамкой в
системе ограничений.
II ш а г.
Основные переменные: х^, *з. *4> *бНеосновные переменные: х\, х$.
Выразим новые основные переменные через новые неосновные, начиная с разрешающего уравнения (его используем при
записи выражения для Х2):
_
с
_
х3 = 18 -
*i
х4 = 16 - 2х,
3(5- jc s),
(5- дс 5),
(5.4)
х5 = 21 -
или
х2 = 5 х3 =
3 -
х5,
х, +3х5,
х4 = 11 - 2Х] + х§ ,
х5 = 21 - Зх,
Второе базисное решение Х^ = (0; 5; 3; 11; 0; 21) является допустимым и соответствует вершине А (0;5) на рис. 5.2. Геометрическая интерпретация перехода от Х\ к Xi - переход от вершины О
к. соседней вершине А на многоугольнике решений OABCDE.
Выразив линейную функцию через неосновные переменные на
этом шаге, получаем:
F = 2х,
2
=
3(5 - *5) = 15 + 2х, -
Значение линейной функции FI = ДАз) = 15. Изменение значения линейной функции легко определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в выражении для линейной
функции; в данном случае Д/j = 5-3 = 15, FI = F\ + A/J =
= 0 + 15 = 15.
Симплексный метод
71
Однако значение FI не является максимальным, так как повторяя рассуждения I шага, обнаруживаем возможность дальнейшего
увеличения линейной функции за счет переменной х\, входящей в
выражение для F с положительным коэффициентом. Система
уравнений (5.4) определяет наибольшее возможное значение для
х\ х, = min{oo;3/l;ll/2;oo} = 3. Второе уравнение является разрешающим, переменная хз переходит в неосновные, при этом
III
ш а г. Основные переменные: х\, х^, х$, х&
Неосновные переменные: *з, *5-
Как и на II шаге, выражаем новые основные переменные через
новые неосновные, начиная с разрешающего уравнения (его используем при записи выражения для Х[). После преобразований
получаем:
*3
х, = 5
Х4
Х
6
(5.5)
= 5 -(- 2х3 - 5х5 ,
= 12 -*- Зх3 -9х 5 .
Базисное решение АЗ - (3; 5; 0; 5; 0; 12) соответствует вершине В (3;5). Выражаем линейную функцию через неосновные
=
+
переменные: / = 2х\ + 3x2 2(3 - хз + 3xs) 3(5 - х$) = 21 -
- 2х3 + Зх5, /з = ДАз) = 21. Проверяем: Р3 - FI = 21 - 15 = 6 =
= А/2. Третье допустимое базисное решение тоже не является
оптимальным, поскольку при неосновной переменной х$ в выражении линейной функции через неосновные переменные содержится положительный коэффициент. Переводим х$ в основную переменную. При определении наибольшего возможного
значения для х$ следует обратить внимание на первое уравнение
в системе (5.5), которое не дает ограничений на рост xs, так как
свободный член и коэффициент при хз имеют одинаковые знаки. Поэтому х5 = min{oo;5;l;12/9} = 1. Третье уравнение является
разрешающим,
AF3 = 1 3 = 3.
и переменная
х$ переходит
в
неосновные;
Глава 5
72
IV ш а г. Основные переменные: х\, х^, х$, jcg.
Неосновные переменные: хз, JC4После преобразований получим:
=6+-х --х
2
2
1
_4--x3+-*4>
_i
2
1
5 ~ ! + Т Х 3 "Т* 4 "
6 =
3-1х 3 + 9*4
Базисное решение Х$ = (6; 4; 0; 0; 1; 3) соответствует вершине
С(6; 4) на рис. 5.2.
Линейная функция, выраженная через неосновные переменные, имеет вид: F = 24 - - х3 - -х4 . Это выражение не содержит
положительных коэффициентов при неосновных переменных,
поэтому значение F^ = F(X$) = 24 максимальное. Функцию F невозможно еще увеличить, переходя к другому допустимому б
Live Journal
Facebook
Twitter