Кремер н ш исследование операций. Литература по линейному, математическому программированию и исследованию операций

Лунгу К. Н. Линейное программирование. Руководство к решению задач. - М.: ФИЗМАТЛИТ, 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

Книги по собственно линейному программированию

	Ашманов С. А. Линейное программирование. - М.: Наука. Главная редакция физико-математической литературы, 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

	Калихман И. Л., Войтенко М. А. Динамическое программирование в примерах и задачах: Учеб. пособие.-М.: Высш. школа, !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 Мб) или страница с последней версией См. также раздел

Другие книги схожей тематики:

См. также в других словарях:

Эту страницу предлагается объединить с Наука управления. Пояснение причин и обсуждение на странице Википедия:К объединению/18 декабря 2012 … Википедия

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

Виктор Васнецов. Витязь на распутье. 1878 Теория принятия решений область исследования, вовлекающая понятия и методы математики, статистики … Википедия

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

Логистика стратегическое управление (менеджмент) закупкой, снабжением, перевозками и хранением материалов, деталей и готового инвентаря (техники и проч.). Понятие включает в себя также управление соответствующими потоками информации, а также… … Википедия

Логистика стратегическое управление (менеджмент) закупкой, снабжением, перевозками и хранением материалов, деталей и готового инвентаря (техники и проч.). Понятие включает в себя также управление соответствующими потоками информации, а также… … Википедия

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

Шаг 1. Выбирайте книги в каталоге и нажимаете кнопку «Купить»;

Шаг 2. Переходите в раздел «Корзина»;

Шаг 3. Укажите необходимое количество, заполните данные в блоках Получатель и Доставка;

Шаг 4. Нажимаете кнопку «Перейти к оплате».

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

Внимание! Просим не менять способ оплаты по заказам. Если Вы уже выбрали какой-либо способ оплаты и не удалось совершить платеж, необходимо переоформить заказ заново и оплатить его другим удобным способом.

Оплатить заказ можно одним из предложенных способов:

1. Безналичный способ:
   • Банковская карта: необходимо заполнить все поля формы. Некоторые банки просят подтвердить оплату – для этого на Ваш номер телефона придет смс-код.
   • Онлайн-банкинг: банки, сотрудничающие с платежным сервисом, предложат свою форму для заполнения. Просим корректно ввести данные во все поля.
     Например, для " class="text-primary">Сбербанк Онлайн требуются номер мобильного телефона и электронная почта. Для " class="text-primary">Альфа-банка потребуются логин в сервисе Альфа-Клик и электронная почта.
   • Электронный кошелек: если у Вас есть Яндекс-кошелек или Qiwi Wallet, Вы можете оплатить заказ через них. Для этого выберите соответствующий способ оплаты и заполните предложенные поля, затем система перенаправит Вас на страницу для подтверждения выставленного счета.

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

1. Общие понятия и определения в и сследование операций

Следует усвоить основные понятия и определения исследования операций.

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

Замечание 1

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

Замечание 2

Если в одних задачах исследования операций оптимальным является решение, при котором выбранный критерий эффективности принимает максимальное или минимальное значение, то в других задачах это вовсе не обязательно. Так, в задаче оптимальным можно считать, например, такое количество торговых точек и персонала в них, при котором среднее время обслуживания покупателей не превысит, например, 5 мин, а длина очереди в среднем в любой момент окажется не более 3 человек (1, стр. 10-11).

Эффективность производственно-коммерческой деятельности в значительной степени определяется качеством решений, повседневно принимаемым менеджерами разного уровня. В связи с этим большое значение приобретают задачи совершенствования процессов принятия решений, решить которые позволяет исследование операций. Термин «исследование операций» впервые начал использоваться в 1939-1940 гг. в военной области. К этому времени военная техника и ее управление принципиально усложнилось вследствие научно-технической революции. И поэтому к началу Второй мировой войны возникла острая необходимость проведения научных исследований в области эффективного использования новой военной техники, количественной оценки и оптимизации принимаемых командованием решений. В послевоенный период успехи новой научной дисциплины были востребованы в мирных областях: в промышленности, предпринимательской и коммерческой деятельности, в государственных учреждениях, в учебных заведениях.

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

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

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

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

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

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

Решение, которое оказывается наиболее выгодным для всей организации, называется оптимальным, а решение, наиболее выгодное одному или нескольким подразделениям, будет субоптимальным.

В качестве примера типичной задачи организационного управления, где сталкиваются противоречивые интересы подразделений, рассмотрим задачу управления запасами предприятия.

Производственный отдел стремится выпускать как можно больше продукции при наименьших затратах. Поэтому он заинтересован в возможно более длительном и непрерывном производстве, т. е. в выпуске изделий большими партиями, ибо такое производство снижает затраты на переналадку оборудования, а следовательно и общие производственные затраты. Однако выпуск изделий большими партиями требует создания больших объемов запасов материалов, комплектующих изделий и т. д.

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

Финансовый отдел, стремясь минимизировать объем капитала, необходимого для функционирования предприятия, пытается уменьшить количество «связанных» оборотных средств. Поэтому он заинтересован в уменьшении запасов до минимума. Как видим, требования к размерам запасов у разных подразделений организации оказываются различными. Возникает вопрос, какая стратегия в отношении запасов будет наиболее благоприятной для всей организации. Это типичная задача организационного управления. Она связана с проблемой оптимизации функционирования системы в целом и затрагивает противоречивые интересы ее подразделений.

Основные особенности исследования операций:

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

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

3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами (денежные средства, машинное время) или уровнем современной науки. Например, для многих комбинаторных задач, в частности задач календарного планирования при числе станков п > 4, оптимальное решение при современном развитии математики оказывается возможным найти лишь простым перебором вариантов. Тогда приходится ограничиваться поиском «достаточно хорошего», или субоптимального решения. Поэтому исследование операций один из его создателей -- Т. Саати -- определил как «...искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».

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

Каждое операционное исследование проходит последовательно следующие основные этапы:

1) описание задачи планирования,

2) построение математической модели,

3) нахождение решения,

4) проверка и корректировка модели,

5) реализация найденного решения на практике.

Описание задачи планирования:

· Задачи сетевого планирования и управления

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

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

· Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точек заказа) и размеров заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но, с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.

· Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.

· Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.

· Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.

· Задачи планировки и размещения состоят в определении числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.

· Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов (1, стр.15).

2. Математическая форма моде ли

Моделирование - процесс исследования реальной системы, включающий построение модели, изучение ее свойств и перенос полученных сведений на моделируемую систему.

Модель - это некоторый материальный или абстрактный объект, находящийся в определенном объективном соответствии с исследуемым объектом, несущий о нем определенную информацию и способный его замещать на определенных этапах познания.

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

В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л. В. Канторович, Н. П. Бусленко, Е. С. Вентцель, Н. Н. Воробьев, Н. Н. Моисеев, Д. Б. Юдин и многие другие. Особо следует отметить роль академика Л. В. Канторовича, который в 1939 г., занявшись планированием работы агрегатов фанерной фабрики, решил несколько задач: о наилучшей загрузке оборудования, раскрое материалов с наименьшими потерями, о распределении грузов по нескольким видам транспорта и др. Л. В. Канторович сформулировал новый класс условно-экстремальных задач и предложил универсальный метод их решения, положив начало новому направлению прикладной математики -- линейному программированию.

Значительный вклад в формирование и развитие исследования операций внесли зарубежные ученые Р. Акоф, Р. Беллман, Г. Данциг, Г. Кун, Дж. Нейман, Т. Саати, Р. Черч мен, А. Кофман и др. (1, стр. 17)

Этапы построения математических моделей :

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

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

2. Формализация операций

На основе содержательного описания определяется и анализируется исходное множество характеристик объекта, выделяются наиболее существенные из них. Затем выделяют управляемые и неуправляемые параметры, вводят символьные обозначения. Определяется система ограничений, строится целевая функция модели. Таким образом, происходит замена содержательного описания формальным (символьным, упорядоченным).

3. Проверка адекватности модели

Исходный вариант модели необходимо проверить по следующим аспектам:

1) все ли существенные параметры включены в модель?

2) нет ли в модели несущественных параметров?

3) правильно ли отражены связи между параметрами?

4) правильно ли определены ограничения на значения параметров?

Главным путем проверки адекватности модели исследуемому объекту выступает практика. После предварительной проверки приступают к реализации модели и проведению исследований. Полученные результаты моделирования подвергаются анализу на соответствие известным свойствам исследуемого объекта. По результатам проверки модели на адекватность принимается решение о возможности ее практического использования или о проведении корректировки.

4. Корректировка модели

На этом этапе уточняются имеющиеся сведения об объекте и все параметры построенной модели. Вносятся изменения в модель, и вновь выполняется оценка адекватности.

5. Оптимизация модели

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

Типы моделей:

В самом общем случае математическая модель задачи имеет вид:

max Z=F(x, y) (1.1)

при ограничениях

где Z=F(x, y) - целевая функция (показатель качества или эффективность) системы; х -- вектор управляемых переменных; у -- вектор неуправляемых переменных; Gi(x, y)-- функция потребления i-го ресурса; bi -- величина i-го ресурса (например, плановый фонд машинного времени группы токарных автоматов в станко-часах).

Определение 1. Любое решение системы ограничений задачи называется допустимым решением.

Определение 2. Допустимое решение, в котором целевая функция достигает своего максимума или минимума называется оптимальным решением задачи.

Для нахождения оптимального решения задачи в зависимости от вида и структуры целевой функции и ограничений используют те или иные методы теории оптимальных решений (методы математического программирования).

1. Линейное программирование, если F(x, y), -- линейны относительно переменных х.

2. Нелинейное программирование, если F(x, y) или -- нелинейны относительно переменных х.

3. Динамическое программирование, если целевая функция F(x, y) имеет специальную структуру, являясь аддитивной или мультипликативной функцией от переменных х.

F(x)=F(x1, x2, …, xn) -- аддитивная функция, если F(x1, x2, …, xn)=, и функция F(x1, x2, …, xn) -- мультипликативная функция, если F(x1, x2, …, xn)=.

4. Геометрическое программирование, если целевая функция F(x) и ограничения представляют собой функции вида

Математическая модель задачи в этом случае записывается в виде

при условиях

где I=(m0, m0+1, …, n0); I[k]= (mk, mk+1, …, nk); mk+1=nk+1; m0=1; n0=n.

5. Стохастическое программирование, когда вектор неуправляемых переменных у случаен.

В этом случае математическая модель задачи (1.1--1.2) будет иметь

maxMyE=My{f(x, y)}

при ограничениях

или вероятностных ограничениях

где My -- математическое ожидание по у; Р{gi (х)Ј b} -- вероятность того, что выполняется условие gi (х)Ј b.

6. Дискретное программирование, если на переменные xj наложено условие дискретности (например, целочисленности): xj -- целое, j=1,2,…,n1Јп.

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

Из перечисленных выше методов математического программирования наиболее развитым и законченным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций.

3. Линейное программирование

Несмотря на требование линейности целевой функции и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи, задачи теории расписаний и т. д.

Основные теоремы линейного программирования

В основе методов решения задач линейного программирования лежат следующие теоремы.

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

Теорема 2.1. Если целевая функция принимает максимальное значение в некоторой точке допустимого множества R, то она принимает это значение в крайней точке R (вершине выпуклого многогранника). Если целевая функция принимает максимальное значение более, чем в одной крайней точке, то она принимает это же значение в любой их выпуклой комбинации.

Из теоремы 2.1 следует, что при отыскании оптимального решения достаточно просмотреть только крайние точки допустимого множества решений R.

Теорема 2.2. Каждое допустимое базисное решение соответствует крайней точке R.

Справедлива также следующая теорема, обратная к теореме 2.2. Теорема 2.3. Если -- крайняя точка допустимого множества решений R, то соответствующее решение x0 -- является допустимым базисным решением системы ограничений задачи линейного программирования.

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

Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2, ..., аi, ..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2, ..., q).

Эффективность выпуска единицы k-го изделия характеризуется показателем сi, удовлетворяющим условию линейности.

Определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.

4. Нелинейное программирование

В данной главе описываются оптимизационные задачи нелинейного программирования (НЛП), математические модели которых содержат нелинейные зависимости от переменных. Источники нелинейности относятся в основном к одной из двух категорий:

1) реально существующие и эмпирически наблюдаемые нелинейные соотношения, например: непропорциональные зависимости между объемом производства и затратами; между количеством используемого в производстве компонента и некоторыми показателями качества готовой продукции; между затратами сырья и физическими параметрами (давление, температура и т.п.) соответствующего производственного процесса; между выручкой и объемом реализации и др.;

2) установленные (постулируемые) руководством правила поведения или задаваемые зависимости, например: формулы или правила расчета с потребителями энергии или других видов услуг; эвристические правила определения страховых уровней запаса продукции; гипотезы о характере вероятностного распределения рассматриваемых в модели случайных величин; различного рода договорные условия взаимодействия между партнерами по бизнесу и др.

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

Основные понятия НЛП:

* целевую функция;

* ограничения;

* допустимый план;

* множество допустимых планов;

* модель нелинейного программирования;

* оптимальный план.

Необходимо уметь:

* определять, является ли функция выпуклой;

* строить функцию Лагранжа задачи НЛП;

* проверять оптимальность полученных решений.

Модели НЛП

В общем виде задача НЛП описывается с помощью следующей модели нелинейного программирования:

исследование операция моделирование математический

где х = (x1, х2, ..., хn) -- вектор переменных задачи.

Задача (1)--(3) называется задачей нелинейного программирования в стандартной форме на максимум.

Может быть сформулирована также задача НЛП на минимум.

Вектор х = (x1, х2, ..., хn), компоненты хj которого удовлетворяют ограничениям (2) и (3), называется допустимым решением или допустимым планом задачи НЛП.

Совокупность всех допустимых планов называется множеством допустимых планов.

Допустимое решение задачи НЛП, на котором целевая функция (1) достигает максимального значения, называется оптимальным решением задачи НЛП.

Возможное местонахождение максимального значения функции F(x) при наличии ограничений (2) и (3) определяется следующим общим принципом. Максимальное значение F(x), если оно существует, может достигаться в одной или более точках, которые могут принадлежать следующим множествам:

Внутренняя точка множества допустимых планов, в которой все первые частные производные

Точка границы множества допустимых планов};

Точка множества допустимых планов, в которой функция F(x) недифференцируема}.

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

Эффективность алгоритма может даже существенно зависеть от постановки задачи, например от изменения масштабов измерения тех или иных переменных. Поэтому алгоритмы разрабатываются для каждого класса (типа) задач. Программы, ориентированные на решение определенного класса задач, как правило, не гарантируют правильность решения любых задач данного класса, и оптимальность решения рекомендуется проверять в каждом конкретном случае.

В экономических приложениях рассматриваются следующие классы задач НЛП.

На рисунке приводится классификация задач и методов нелинейного программирования.

Рисунок. Классификация задач и методов нелинейного программирования

Большинство существующих методов в нелинейном программировании можно разделить на два больших класса:

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

2. Недостаток: трудно получить свойство глобальной сходимости.

3. Задачи с ограничениями в виде равенств.

4. Метод замены переменных (МЗП)

5. Двойственные методы - методы, использующие понятие двойственности. В этом случае легко получить глобальную сходимость.

6. Недостаток: не дают решения исходной задачи в ходе решения - оно реализуемо лишь в конце итерационного процесса.

o Метод множителей Лагранжа (ММЛ)

o Методы штрафов

o Метод множителей

o Методы линеаризации для задач условной оптимизации

o Алгоритм Франка-Вульфа

o Метод допустимых направлений Зойтендейка

o Метод условного градиента

o Метод проекции градиента

o Сепарабельное программирование.

o Квадратичное программирование

1. Оптимизация нелинейной функции с ограничениями на неотрицательность значений переменных:

где х = (х1, х2,..., хn) -- вектор переменных задачи.

Пусть F(x) -- дифференцируемая функция.

Необходимые условия того, что в точке х0 достигается максимум функции F(x):

Это означает, что:

Если F(x) вогнутая функция (для задачи минимизации -- выпуклая), то эти условия являются также достаточными.

Функция F(x) с числовыми значениями, определенная на выпуклом множестве точек К, называется вогнутой, если для любой пары точек х1, х2 и для всех чисел l, 0 Ј l Ј 1, выполняется неравенство

то функция F(x) называется выпуклой. Если имеют место строгие неравенства, то говорят, что функция строго вогнута или строго выпукла.

Данное определение вогнутости (выпуклости) годится для любого типа функции. Практически, однако, применять его трудно.

Для дважды дифференцируемой функции F(x) имеет место следующий критерий. Дифференцируемая функция F(x) строго вогнута в некоторой окрестности точки если выполняются следующие условия:

т.е. если знаки этих определителей чередуются указанным образом.

Здесь -- частная производная второго порядка, вычисленная в точке х0.

Матрица размера п ґ п, составленная из элементов, называется матрицей Хессе (Hesse). По значениям ее главных миноров можно судить о выпуклости или вогнутости функции. Функция F(x) строго выпукла в малой окрестности точки х0, если все главные миноры ее матрицы Хессе строго положительны. Если имеют место нестрогие неравенства (і), то функция в окрестности точки х0 выпукла. Если при этом главные миноры матрицы Хессе от х не зависят, то функция всюду (строго) выпукла.

Весьма распространены относящиеся к данному типу модели квадратичного программирования, в которых целевая функция F(x) является квадратичной функцией переменных х1, х2, ..., хn. Существует большое число алгоритмов решения такого типа задач, в которых функция F(x) вогнутая (для задач минимизации -- выпуклая).

2. Модели выпуклого программирования. К такого рода моделям относятся задачи НЛП (1)--(3), в которых F(x) -- вогнутая (выпуклая) функция, a gi(x) -- выпуклые функции. При данных условиях локальный максимум (минимум) является и глобальным.

Пусть F(x) и gi(x), i= 1,..., т, -- дифференцируемые функции.

Необходимые и достаточные условия оптимальности решения -- выполнение условий Куна -- Таккера.

Рассмотрим задачу НЛП (1)--(3) и функцию Лагранжа

Условия Куна -- Таккера оптимальности решения х0 для задачи максимизации F(x) имеют вид

где -- частная производная функции Лагранжа по переменной хj при х = х0 и l = l0. Пусть максимальное значение F(x) равно F(x0) = F0. Числа связаны с F0 следующими соотношениями:

Из этих соотношений видно, что числа характеризуют реакцию значения F0 на изменение значения соответствующего bi. Например, если < 0, то при уменьшении bi (в пределах устойчивости) значение F0 увеличится, а = 0 указывает на несущественность соответствующего ограничения gi(х) Ј bi, которое может быть без ущерба для оптимального решения из системы ограничений исключено.

3. Сепарабельное программирование. Специальный случай выпуклого программирования при условии, что F(x) и все gi(х) -- сепарабельные функции, т.е.

Задачи данного вида сводятся к задачам линейного программирования.

4. Дробно-нелинейное программирование. Максимизировать (минимизировать) функцию

F(x) = F1(x)/F2(x).

В частном случае, когда в числителе и знаменателе -- линейные функции (так называемая задача дробно-линейного программирования), задача сводится к линейной.

5. Невыпуклое программирование. Функция F(x) и (или) какие-либо gi(x) не выпуклы. Надежных методов решения задач такого типа пока не существует (3, стр. 74-77)

Как пример, рассмотрим нелинейную модель оптимального распределения ресурсов:

Описание задачи распределения ресурсов

Задача распределения ресурсов рассматривается для n предприятий. Центр осуществляет управление этими промышленными предприятиями, выпускающими однотипную продукцию. Обозначим через Рi объем продукции, выпускаемой предприятием i, i=1,. ..,n. Результат функционирования центра определяется результатами функционирования отдельных производителей, т.к. центр сам не производит продукции.

Считаем, что величина продукции, произведенной i-м предприятием, определяется объемом фондов Fi и количеством рабочей силы Li, согласие производственной функции Кобба- Дугласа:

Где i=1,..,n (4)

В выражении (4) di и ki характеристики предприятия i (i=1,.. .,n), удовлетворяющие условиям: di > 0 , i=1,...,n.

Пусть wi - ставка заработной платы на предприятии i. Тогда доля дохода предприятия i в общей сумме прибыли объединения определится так:

Gi =ci*Pi-wi*Li , i=1,. . .,n.

Если величина фондов предприятия фиксирована, то объем продукции Pi однозначно определяется количеством рабочей силы.

Центр влияет на работу предприятий распределением дополнительного ресурса, который полностью находиться в его распоряжении. Если предприятие i получит дополнительный ресурс в количестве Vi, то оно сможет произвести продукцию в объеме

Задача центра состоит в распределении имеющегося в его распоряжении ресурса В, т. е. в определении оптимальных значений величин Vi, i =1,...,n, обеспечивающих максимум суммарной прибыли объединения в целом.

Математическая форма модели

В данной задаче считаем, что используется схема централизованного планирования, в рамках которой центр рассчитывает оптимальное распределение ресурсов, оптимальные величины рабочей силы при заданных параметрах модели. Конкретно центр изменяет Vi и Li, i = 1,...,n, из условий:

z = max (G1 + G2 + ,..., + Gn) (6)

Vi, Vimin, Li 0,i=1,...,n (7)

Анализ чувствительности модели как способ восстановления финансового равновесия.

Основой сохранения и восстановления финансового равновесия предприятия и снижения уровня риска является анализ чувствительности предложенной модели. Анализ чувствительности состоит из следующих этапов:

1. Выбор ключевого показателя, т.е. такого параметра, относительно которого и рассчитывается чувствительность проекта (чаще всего это чистый приведенный доход и внутренняя норма доходности).

2. Выбор факторов, которые влияют на эти показатели.

3. Расчет значений ключевых показателей на разных этапах реализации проекта (поиск, проектирование, строительство, эксплуатация).

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

Часто во время анализа чувствительности определяется точка безубыточности проекта, т.е. определяется тот объем выпуска продукции, при котором предприятие выходит из зоны убытка.

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

Недостатки метода анализа чувствительности:

1. Метод не рассчитан на все случайное и возможное обстоятельства.

2. Метод не уточняет вероятность реализации альтернативных проектов.

Анализ чувствительности оптимального решения

Анализ чувствительности выполняется уже после получения оптимального решения задачи линейного программирования (ЛП). Его цель -- определить, приведет ли изменение коэффициентов исходной задачи к изменению текущего оптимального решения, и если да, то, как эффективно найти новое оптимальное решение (если оно существует).

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

1. Текущее базисное решение остается неизменным.

2. Текущее решение становится недопустимым.

3. Текущее решение становится неоптимальным.

4. Текущее решение становится неоптимальным и недопустимым.

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

Список литературы

1. «Исследование операций в экономике» учебное пособие для Вузов, 3-е издание, переработанное и дополненное, под ред. Н.Ш.Кремера, М.: Юрайт, 2013.

2. T.В. Алесинская « Основы логистики. Общие вопросы логистического управления» .Учебное пособие. Таганрог: Изд-во ТРТУ, 2005.

3. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения. Учебное пособие, М, Инфра-М, 2003 г.

4. Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. -М.: Мир,1984.

5. Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991.

6. Попов Ю.Д. Линейное и нелинейное программирование. Учебное пособие. - Киев, 1988.

7. Зайченко Ю.П. Исследование операций. Учебное пособие для студентов вузов. - Киев: Вища школа. Головное издательство, 1979

8. Таха Х.. Введение в исследование операций: в 2-х книгах. - М.: Мир, 1985.

9. Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1997.

10. Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

11. Данко. Высшая математика в примерах и задачах.

12. Алексеев В. М., Голеев В. М., Тихомиров В. М. Сборник задач по оптимизации: Теория, примеры, задачи. М., Наука, 1984.

13. Берман Г. Н. Сборник задач по курсу математического анализа. М., Наука, 1985.

14. Ильин В.А.., Позняк Э.Г. Линейная алгебра. М., Наука, 1983.

15. Ильин В.А.., Позняк Э.Г. Основы математического анализа. М., Наука, Ч.1,2, 1980.

16. Клетеник Д..В. Сборник задач по аналитической геометрии. М., Наука, 1984.

17. Кудрявцев Л.Д.. Курс математического анализа. М., Высш. шк., Т. 1-3, 1988.

18. Кудрявцев Л.Д.. Краткий курс математического анализа. М., Наука, 1989.

19. Кудрявцев Л.Д.., Кутасов А..Д., Чехлов В.И., Шабунин М.И. Сборник задач по математическому анализу. Предел. Непрерывность. Дифференцируемость. М., Наука, 1984.

20. Кремер Н. Ш., Путко Б. А.., Тришин И.М., Фридман М. Ф. Высшая математика для экономистов. М., Банки и биржи, ЮНИТИ, 1998.

21. Гмурман В.Е. Теория вероятностей и математическая статистика. Учебное пособие для вузов. М., Высш. шк., 1999.

22. Ниворожкина Л.И., Морозова З.А. Основы статистики с элементами теории вероятностей для экономистов. Руководство для решения задач. Ростов н/Д., Феникс., 1999.

23. Данко П.Е. Высшая математика в упражнениях и задачах. Ч.2. М., Высш. шк., 1997.

24. Чистяков В.П. Курс теории вероятностей. М., Наука., 1987.

25. Севастьянов Б. А. Курс теории вероятностей и математической статистики. М., Наука., 1982.

26. Севастьянов Б.А., Чистяков В.П., Зубков А.М. Сборник задач по теории вероятностей. М., Наука., 1980.

27. Вентцель Е.С Исследование операций. Задачи. Принципы. Методология, 1980.

28. Горелик В.А., Ушаков И.А. Исследование операций. - М.: Машиностроение, 1986.

29. Исследование операций/ Под редакцией М.А. Войтенко и Н.Ш. Кремера.-М.: Экономическое образование, 1992.

30. Карасев А.И., Аксютин З.М., Савельева Т.И. Математические методы и модели в планировании М.: Экономика, 1987.

31. Исследование операций / Н. Н. Писарук. Минск: БГУ, 2013.272 c.

Размещено на Allbest.ru

...

Подобные документы

Графическое решение задач линейного программирования. Решение задач линейного программирования симплекс-методом. Возможности практического использования математического программирования и экономико-математических методов при решении экономических задач.

курсовая работа , добавлен 02.10.2014


Понятие и типы моделей. Этапы построения математической модели. Основы математического моделирования взаимосвязи экономических переменных. Определение параметров линейного однофакторного уравнения регрессии. Оптимизационные методы математики в экономике.

реферат , добавлен 11.02.2011


Изучение экономических приложений математических дисциплин для решения экономических задач: использование математических моделей в экономике и менеджменте. Примеры моделей линейного и динамического программирования как инструмента моделирования экономики.

курсовая работа , добавлен 21.12.2010


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

курсовая работа , добавлен 17.02.2010


Математическая формализация оптимизационной проблемы. Геометрическая интерпретация стандартной задачи линейного программирования, планирование товарооборота. Сущность и алгоритм симплекс-метода. Постановка транспортной задачи, последовательность решения.

учебное пособие , добавлен 07.10.2014


Теоретические основы экономико-математических методов. Этапы принятия решений. Классификация задач оптимизации. Задачи линейного, нелинейного, выпуклого, квадратичного, целочисленного, параметрического, динамического и стохастического программирования.

курсовая работа , добавлен 07.05.2013


Общая постановка задачи линейного программирования (ЛП). Приведение задачи ЛП к стандартной форме. Теоремы двойственности и их использование в задачах ЛП. Транспортная задача и её решение методом потенциалов. Интерполирование табличных функций.

курсовая работа , добавлен 31.03.2014


Цель работы: изучить и научиться применять на практике симплекс - метод для решения прямой и двойственной задачи линейного программирования. Математическая постановка задачи линейного программирования. Общий вид задачи линейного программирования.

реферат , добавлен 28.12.2008


Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.

дипломная работа , добавлен 06.08.2013


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

И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 невозможно еще увеличить, переходя к другому допустимому б