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

Балашовский институт (филиал)

ГОУ ВПО «Саратовский государственный университет имени Н. Г. Чернышевского»

Учебное пособие

Введение в линейное программирование

Г. И. Горемыкина

М. А. Ляшко

Балашов 2011

УДК 517.1

ББК 22.14я73+22.143

Г67

Рецензенты:

Кандидат физико-математических наук, доцент, зав. кафедрой математического анализа

Вологодского государственного педагогического университета Г. Н. Шилова;

Кандидат физико-математических наук, доцент, зав. кафедрой физики и информационных технологий О. А. Кузнецов.

Горемыкина, Г. И.

Г67 Введение в линейное программирование : учеб. пособие для студентов физ.-мат. и эконом. фак-тов / Г. И. Горемыкина, М. А. Ляшко. -- Балашов : Николаев, 2011. -- 132 с.

ISBN 978-5-94035-

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

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

ISBN 978-5-94035 © Горемыкина Г. И., Ляшко М. А., 2011

Содержание

Предисловие

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

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

3. Симплексный метод

4. Решение задачи линейного программирования в Excel

5. Многокритериальная оптимизация

6. Введение в линейное программирование как учебный модуль в контексте модульно-рейтинговой системы обучения

Список рекомендуемой литературы

Предисловие

Учебное пособие содержит необходимый теоретический материал, примеры, задачи и упражнения по таким разделам линейной алгебры, как линейное программирование, симплексный метод и линейные модели, которые прекрасно иллюстрируют возможность применения математики в экономических исследованиях. За основу взята программа курса, который читается авторами на протяжении многих лет студентам математических и экономических специальностей БИСГУ и соответствует Государственному образовательному стандарту 2005 г., а также программа спецкурса на физико-математическом факультете. Эффективная обработка математических моделей реальных ситуаций невозможна без точного предписания, определяющего вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату. Применение вычислительной техники позволяет сделать такую обработку не только точной, но и быстрой, поэтому авторы сочли необходимым сопроводить пособие алгоритмами и программами представленных в нем методов, а также показать возможность использования табличного процессора Excel. Представленным в пособии разделам предшествует изучение в курсе алгебры векторов, матриц, определителей и линейных систем. Предполагается, что читатель уже владеет понятиями, умениями и навыками, приобретенными в процессе обучения по указанным темам. Понятия, выходящие за рамки линейной алгебры, снабжены в пособии определениями, а некоторые проиллюстрированы примерами.

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

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

Современные вычислительные среды (MathCAD, MATLAB, Excel) имеют встроенные инструменты решения оптимизационных задач, в том числе и задачи линейного программирования. Но табличный процессор Excel изучается как в школьном, так и в вузовском курсе информатики практически всех специальностей. Поэтому в § 4 для автоматизации вычислений в задаче линейного программирования авторы использовали именно это хорошо знакомое студентам приложение. Расширением математического программирования с единственной целевой функцией на случай нескольких целевых функций является многокритериальная оптимизация. В § 5 рассматривается указанная оптимизация при условии линейности целевых функций и системы ограничений. Особенностью пособия является то, что учебный модуль «Введение в линейное программирование» рассмотрен авторами в контексте модульно-рейтинговой системы обучения, приведены подробная методика расчета баллов, указано распределение нагрузки при освоении модуля, сформулированы требования к оформлению самостоятельной работы.

Материалом повышенной сложности авторы считают п. 4 § 2 (решение ЗЛП с тремя переменными), изложение которого на лекции или отработка на практическом занятии требуют много времени. Имея изображение на страницах пособия или подготовленную презентацию, можно обсудить со студентами решения предложенных трехмерных задач. Освоение теории машинной реализации симплекс-метода (п. 4 § 3) также потребует от студентов значительных усилий.

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

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

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

Подготовка пособия была распределена следующим образом: § 1, 2, 5 написаны Г. И. Горемыкиной, § 3 и 4 -- М. А. Ляшко, § 6 -- совместно. Работа по улучшению пособия будет продолжена. Авторы заранее благодарят всех, кто выскажет свои замечания и пожелания, касающиеся улучшения стиля изложения, а также устранения возможных неточностей и опечаток.

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

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

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

1. Примеры задач линейного программирования

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

С и т у а ц и я 1. Фирма имеет одно предприятие, которое выпускает n видов продукции, затрачивая m видов ресурсов. Каждый вид продукции j характеризуется технологией Aj = (a1j,…, amj, cj) в виде набора {aij}, где aij -- количество единиц ресурса i, затрачиваемого на единицу продукта j, и cj -- прибыль, получаемая фирмой с каждой единицы продукта j. Известны также объемы ресурсов B = (b1,…, bm), которыми располагает предприятие. Руководство фирмы заинтересовано в получении оптимального варианта своего бизнеса по прибыли. Для этого предприятию нужно, грамотно распорядившись имеющимися ресурсами, выпустить такую комбинацию всех видов продукции, при которой прибыль оказалась бы наибольшей.

Составим математическую модель данной экономической ситуации. Обозначим через X = (x1,…, xn)T вектор производства, где xj -- объем выпуска продукции j. Вектор X часто называют еще планом производства. При этом координаты вектора X должны быть неотрицательны:

xj0, j =1, 2,…, n,

(иногда выпуск продукции j может быть ограничен dj, в этом случае имеет место двойное неравенство 0xjdj). Ограниченность ресурсов и линейная зависимость между расходами ресурсов и производством продукции приводит к системе линейных неравенств

bi, i =1, 2, …, m.

Прибыль от реализации произведенного продукта равна

L(X) = c1x1 + c2x2 + ... + cjxj + ... + cnxn.

План производства X = (x1,…, xn)T называется оптимальным по прибыли, если L(X) достигает наибольшего возможного значения при вышеописанных ограничениях. Поэтому, руководствуясь интересами фирмы, предприятие в качестве критерия экономической эффективности должно принять максимум прибыли:

L(X) = c1x1 + c2x2 + ... + cjxj + ... + cnxn max.

При этом следует найти не только само значение max L(X), но (что
не менее важно!) точки, в которых оно достигается, то есть получить оптимальный вектор производства X = (x1,…, xn)T.

Замечание 1. Возможно, что фирма решит использовать другую технологическую характеристику каждого вида продукции. Например, в описанной выше технологии Aj, не меняя экономической интерпретации a1j,…, amj, изменит экономическую интерпретацию последней константы: под cj будет понимать себестоимость каждой единицы продукта j. Это означает, что руководство фирмы заинтересовано в получении оптимального варианта своего бизнеса по себестоимости. Поэтому в качестве критерия экономической эффективности предприятие должно будет принять минимум себестоимости:

L(X ) = c1x1 + c2x2 + ... + cjxj + ... + cnxn min.

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

С и т у а ц и я 2. Научно-производственное объединение занимается разработкой и производством комплексных удобрений. На данный момент в своем распоряжении оно имеет n видов удобрений, каждое из которых содержит m элементов непосредственного питания растений. Такими элементами могут быть азот, фосфор, калий, магний, медь, марганец и др. Известно, что одна единица j-го вида удобрений (j = 1, 2,…, n) содержит aij единиц i-го (i = 1, 2,…, m) элемента непосредственного питания растений и имеет стоимость cj. Необходимо изготовить смешанное комплексное удобрение (тукосмесь), получаемое механическим смешением имеющихся удобрений. При этом тукосмесь должна иметь следующую «химико-экономическую» характеристику:

· содержание каждого i-го элемента питания не менее bi(i = 1, 2,…, m);

· наименьшую стоимость.

Рассмотрим математическую модель данной экономической ситуации. Обозначим через xj количество j-го удобрения, используемого при изготовлении тукосмеси. Конечно, xj ? 0 (j = 1, 2,…, n). Для каждого i-го
(i = 1, 2,…, m) элемента питания, согласно «химико-экономической» характеристике тукосмеси, имеет место следующее неравенство-ограничение: ai1x1 + ai2x2 + ... + ainxn ? bi. Стоимость комплексного удобрения составляет c1x1 + c2x2 + ... + cnxn. Эту величину необходимо минимизировать.

Таким образом, математическая модель предложенной экономической ситуации имеет следующий вид:

L(X) = c1x1 + c2x2 + ... + cjxj + ... + cnxn min,

bi, i =1, 2,…, m;

xj ? 0, j=1, 2,…, n.

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

С и т у а ц и я 3. На пунктах отправления А1,…, Аm находится соответственно a1,…, am единиц однородного груза. Его следует доставить получателям в пункты назначения В1,…, Вn , причем в каждый из которых -- соответственно b1,…, bn единиц этого груза. Стоимость перевозки единицы груза из пункта Аi в пункт Вj равна cij. Требуется составить такой план перевозок, который требовал бы минимальных затрат. При этом предполагается, что транспортные расходы пропорциональны перевозимому количеству груза (то есть перевозка k единиц груза требует расходов в размере kcij), а общий объем груза, готового к отправлению, совпадает с объемом груза, который готовы принять в пунктах назначения:



Замечание 2. Часто в качестве А1,…, Аm и В1,…, Вn выступают соответственно пункты производства и пункты потребления однородного продукта, а и интерпретируются тогда как суммарное количество произведенного и потребленного продукта.

Построим модель рассматриваемой экономической ситуации. План перевозок задается матрицей X = (xij), где xij -- число единиц груза, перевозимого из пункта Аi в пункт Вj. При этом, конечно, xij0 (i=1, 2,…, m;
j = 1, 2,…, n). Тогда xi1 + xi2 +...+ xin -- это общее количество груза, которое можно отправить из пункта Аi в пункты В1,…, Вn, а x1j+x2j+...+xmj -- общее количество груза, которое можно принять в пункте Вj из пунктов А1,…, Аm. Предположение о совпадении суммарных запасов груза и суммарных потребностей в нем приводит к системе линейных равенств

ai для i = 1, 2,…, m;

bj для j =1, 2,…, n.

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

Таким образом, математическая модель данной экономической ситуации имеет следующий вид:

L(X ) = min

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

= ai для i = 1, 2,…, m;

= bj для j = 1, 2,…, n.

xij0 для i = 1, 2,…, m и j =1, 2,…, n.

Как и в предыдущих случах, следует найти не только само значение min L(X), но и точки, в которых оно достигается, то есть получить оптимальную матрицу X = (xij) -- оптимальный план перевозок. Рассмотренная задача носит название транспортной задачи.

Замечание 3. Сделаем несколько уточнений. Рассмотренная задача называется закрытой (= сбалансированной) транспортной задачей. Так называют транспортные задачи, в которых общий объем груза, готового
к отправлению, совпадает с объемом груза, который готовы принять
в пунктах назначения: . Если же указанные объемы не совпадают, то транспортная задача называется открытой. При этом, если , то количество груза, равное -, остается в пунктах отправления невостребованным. Тогда вводят гипотетического (виртуального) (n + 1)-го получателя с готовностью принять груз указанного объема и считают транспортные расходы ci, n +1 равными 0 для всех i. Таким образом, при введении виртуального получателя транспортная задача становится сбалансированной: =, где bn+1 =-. Математическая модель такой экономической ситуации имеет вид:

L(X ) = min

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

= ai для i =1, 2,…, m;

= bj для j =1, 2,…, n, n + 1.

xij0 для i =1, 2,…, m и j =1, 2,…, n, n + 1.

Если же , то вводят гипотетический (виртуальный) пункт отправления Аm+1, содержащий am+1 единиц готового к отправке груза, и транспортные расходы cm+1,j считают равными 0 для всех j. Такое изменение начальных условий также приводит к тому, что транспортная задача становится сбалансированной: =. Математическую модель описанной ситуации предлагается составить самостоятельно.

Замечание 4. ЛПР могут руководствоваться, вырабатывая свою стратегию, принципом максимизации суммарного дохода от перевозок. Тогда транспортная ЗЛП задается следующими элементами:

двумя конечными множествами {А1,…, Аm} и {В1,…, Вn}, экономическая интерпретация элементов которых совпадает с интерпретацией соответствующих элементов в рассмотренной выше минимизационной транспортной задаче;

неотрицательными векторами (a1,…, am) и (b1,…, bn), координаты которых ai и bj определяют количество единиц груза, готового к отправлению и получению в пунктах Ai и Bj соответственно;

матрицей C = (cij), где cij -- доход от перевозки единицы груза из пункта Ai в пункт Bj.

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

L(X ) = max.

2. Некоторые особенности транспортной задачи

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

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

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 min (max)

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

x11 + x12 + x13 = 110,

x21 + x22 + x23 = 100,

x11 + x21 = 60,

x12 + x22 = 80,

x13 + x23 = 70,

x11 0, x120, x130, x210, x220, x230.

Решение. 1) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины:

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 min.

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

Вариант 1 примера 1. Фирма имеет два склада и трех оптовых покупателей. Конкретные данные о загруженности каждого из складов (в тоннах), потребности каждого покупателя (в тоннах) и стоимости перевозки (усл. ед. за 1 т) приведены в таблице 1.

Таблица 1

	Стоимость перевозок к покупателям	Наличие груза
	B1	B2	B3
Склады	A1	4	8	9	110
	A2	7	3	5	100
Потребности	60	80	70

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

Неформальные пояснения к решению варианта 1. Экономической интерпретацией переменной xij является количество товара, поставляемого со склада Ai покупателю Bj, а величина L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 трактуется как общая стоимость всех перевозок. Общий объем запасов на складах совпадает с общим объемом запросов покупателей:

= 110 + 100 = 210 (т), = 60 + 80 + 70 = 210 (т).

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

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

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

2) Теперь рассмотрим случай, когда в качестве критерия экономической эффективности выступает максимум указанной величины:

L(X) = 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23 max.

Вариант 2 примера 1. Мастерская имеет два станка, каждый из которых может выполнять три операции по обработке деталей (порядок выполнения операций не важен). Продолжительность выполнения первой операции составляет 60 часов, второй -- 80, третьей -- 70. Время работы первого и второго станков равно соответственно 110 и 100 часам. Производительность за час (в количестве деталей) первого станка при выполнении первой операции равна 4, при выполнении второй -- 8, третьей -- 9. Аналогичная производительность второго станка равна соответственно 7, 3 и 5. Составить план временнуй загрузки станков по выполнению каждой операции, при котором можно было бы обработать наибольшее количество деталей.

Сформулированная задача носит название задачи об использовании производственного оборудования (мощностей).

Неформальные пояснения к решению варианта 2. Обозначив через A1 и A2 первый и второй станки, а через B1, B2 и B3 первую, вторую и третью операции соответственно, условия данной задачи удобно записать в виде таблицы 2 (сравните с соответствующей таблицей варианта 1).

Таблица 2

	Производительность станков при выполнении операций	Время работы станков
	B1	B2	B3
Станки	A1	4	8	9	110
	A2	7	3	5	100
Продолжительность выполнения операции	60	80	70

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

Обозначим через xij количество часов, которое требуется при выполнении на i-м станке j-й операции. При этом, конечно, xij0 (i = 1, 2, j = 1, 2, 3). Тогда xi1 + xi2 + xi3 -- общее количество часов, которое требуется при
выполнении на i-том станке каждой из трех операций, а x1j +x2j -- суммарная продолжительность выполнения j-й операции на каждом из двух станков. Это приводит к системе линейных равенств

x11 + x12 + x13 = 110,

x21 + x22 + x23 = 100,

x11 + x21 = 60,

x12 + x22 = 80,

x13 + x23 = 70.

Заметим, что суммарная продолжительность выполнения операций совпадает с суммарным временем работы станков: 60 + 80 + 70 = 110 + + 100 (ч). Обозначим через cij производительность i-го станка при выполнении j-й операции. Тогда количество деталей, обработанных на i-м станке при выполнении j-й операции, будет равно cijxij. Общее же количество деталей, обработанных на двух станках при выполнении трех указанных операций, составит= 4x11 + 8x12 + 9x13 + 7x21 + 3x22 + 5x23. В условиях решаемой задачи в качестве критерия экономической эффективности нужно принять максимум этой величины.

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

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

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

L(X) = min(max)

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

= 1 для i =1, 2,…, n; = 1 для j =1, 2,…, n.

xij для i =1, 2,…, n и j =1, 2,…, n.

Решение. 1) Сначала рассмотрим случай, когда в качестве критерия экономической эффективности выступает минимум указанной величины.

Вариант 1 примера 2. Автомобильный завод планирует построить станции A1,…, An для технического обслуживания производимых им машин. Для строительства он выбрал города B1,…, Bn. Вырабатывая стратегию строительства, ЛПР решили руководствоваться принципом минимизации суммарных затрат на строительство указанных станций. Затраты на строительство станции Ai в городе Bj составляют cij. Необходимо определить оптимальную стратегию ЛПР.

Неформальные пояснения к решению варианта 1. Обозначим

xij = .

Конечно, при такой интерпретации переменных

= 1 для i =1, 2,…, n;

= 1 для j =1, 2,…, n,

а -- суммарные затраты на строительство станций, в минимизации которых заинтересованы ЛПР.

2) Рассмотрим случай, когда в качестве критерия экономической эффективности выступает максимум указанной величины:

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

дает разрешение и обязывает франчайзи заниматься в течение франшизы определенным бизнесом, используя специфическое наименование, принадлежащее франчайзеру;

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

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

требует от франчайзи регулярно в течение всего периода франшизы выплачивать франчайзеру определенные денежные суммы в оплату франшизы или товаров, услуг, предоставляемых франчайзером франчайзи;

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

Часто франшизой называют и саму сеть предприятий, связанных с головной компанией сходными франчайзинговыми договорами, использующих одинаковые торговую марку, стиль, условия, методы и формы продаж товаров или оказание услуг [Рудашевский В. Д., Фурщик М. А. Оптимальная стратегия развития франчайзинговой системы // Экономика и мат. методы. 1998. Т. 34. Вып. 2]. франчайзер Франчайзер -- организатор дела, владелец генеральной лицензии, ноу-хау, главный консультант и оптовый поставщик (см. там же). решил организовать торговую точку. Для этого ему потребовалось ввести n новых штатных единиц для выполнения n видов работ. В результате объявленного конкурса было принято n сотрудников. Производительность i-го сотрудника при выполнении j-го вида работ равна cij. Необходимо распределить людей по видам работ таким образом, чтобы их суммарная производительность была бы максимальной.

Неформальные пояснения к решению варианта 2. Обозначим

xij=

Тогда -- суммарная производительность сотрудников, в максимизации которой заинтересован франчайзер. При этом

= 1 для i =1, 2,…, n;

= 1 для j =1, 2,…, n.

Задачи, математические модели которых описаны в примере 2, являются частными случаями транспортной задачи и носят название задач
о сопоставлении (или назначениях).

3. Формулировка общей задачи линейного программирования

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

Требуется найти значения действительных переменных x1, x2,…, xn, при которых целевая функция (показатель эффективности)

L(X ) = c1x1 + c2x2 + ... + cjxj + ... + cnxn + c

принимает экстремальное значение при ограничениях:

xk 0,

где aij, bi, cj, c -- заданные постоянные величины, i = 1, 2,…, m, j = 1, 2,…, n, .

Заметим, что знак «» в ограничительных условиях выбран условно (для определенности), так как, например, неравенство ai1x1+...+ ainxn bi всегда можно заменить на эквивалентное ему неравенство -(ai1x1+...+ainxn)-bi, а уравнение ai1x1+...+ainxn = bi -- на систему неравенств ai1x1+...+ainxnbi и ai1x1+...+ ainxnbi. Стоит, однако, отметить, что на практике сведение уравнений к неравенствам, как правило, осуществляют другим способом (см., например, решение транспортной задачи). Если все ограничительные условия, накладываемые на элементы решения, кроме требования xj0, являются уравнениями, то в этом случае задачу линейного программирования называют канонической задачей линейного программирования (сокращенно КЗЛП). Ее примером может служить опять же транспортная задача. Заметим, что любая задача линейного программирования может быть приведена к канонической.

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

Формулировку общей задачи линейного программирования (сокращенно ОЗЛП) можно записать более компактно:

L(X) =+ c max (min)

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

i, i = 1, 2,…, m, xk 0, .

4. Геометрическая интерпретация ЗЛП

Рассмотрим задачу линейного программирования по нахождению максимума (минимума) целевой функции L(X) = c1x1 +...+ cnxn + c на допустимом множестве , заданном с помощью системы линейных ограничений (нестрогих неравенств или уравнений).

Напомним некоторые определения.

Выпуклой линейной комбинацией элементов X1,…, Xk из пространства Rn называют элемент X этого же пространства вида

X =1X1+…+kXk, где все i 0 и 1+…+k = 1.

Множество M Rn называется выпуклым, если M = или вместе с любыми двумя элементами X1 и X2 содержит и их произвольную выпуклую линейную комбинацию. Геометрически выпуклость множества M Rn означает, что вместе с любыми двумя своими точками оно содержит и весь отрезок, их соединяющий (рис. 2).

Замечание 5. Такая геометрическая интерпретация выпуклости объясняется тем, что любая точка отрезка является выпуклой линейной комбинацией его концов. Действительно, если точки X, X1, X2 определяются в Rn соответственно координатами (x1,…, xn), (x11,…, x1n), (x21,…, x2n) и X -- произвольная точка отрезка X1X2, то x1 = x11+(1)x21,…, xn = x1n + (1)x2n, 0 1. В сокращенном виде это запишется так:

X = X1+ (1)X2, 0 1.

Примерами выпуклых множеств в R3 служат куб, шар, точка. Примером выпуклого множества в Rn может служить плоскость. Еще два примера выпуклых множеств в Rn описывает

Теорема 1. а) Множество решений системы ограничений задачи линейного программирования является выпуклым множеством;

б) Множество решений задачи линейного программирования является выпуклым множеством.

Таким образом, геометрическая интерпретация задачи линейного программирования заключается в следующем:

найти максимум (минимум) линейной функции на выпуклом множестве.

Ограниченное множество решений системы ограничений ЗЛП называют выпуклым многогранником, а неограниченное -- выпуклой многогранной областью. В R2 -- это выпуклые многоугольники или выпуклые многоугольные области (см., например, рис. 3).

Функция L(x1, x2…, xn) называется ограниченной сверху (снизу) на множестве M Rn, если существует число К такое, что для всех (x1, x2,…, xn) из множества М выполняется неравенство L(x1, x2,…, xn) ? К (L(x1, x2,…, xn) ? К). Функция, ограниченная и сверху, и снизу, называется ограниченной.

Будем говорить, что целевая функция ЗЛП ограничена, если в задаче на максимум она ограничена на допустимом множестве сверху, а в задаче на минимум -- снизу.

Теорема 2. Если в задаче линейного программирования допустимое множество отлично от пустого и целевая функция ограничена, то существует по крайней мере одно оптимальное решение.

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

У выпуклого множества, изображенного на Рис. 4, точки X и W являются его вершинами, а точки Y и Z -- нет. Действительно, каждая из двух последних точек является выпуклой линейной комбинацией других его точек: Y, например, является выпуклой линейной комбинацией точек Y1 и Y2, а Z -- выпуклой линейной комбинацией Z1 и Z2 (см. замечание 5). У X и W таких точек нет.

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

Эта теорема дает возможность разработать алгоритм, позволяющий решить ЗЛП методом перебора вершин. Для чего

первое, что необходимо сделать, -- это определить все угловые точки допустимого множества;

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

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

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

Графический метод, как правило, применяется при решении ЗЛП, система ограничений которых содержит две (реже три) переменных. Одно из достоинств этого метода указано в § 1. К числу других следует отнести простоту и наглядность, а также то, что с его помощью становятся прозрачными идеи, заложенные в основе других методов решения ЗЛП.

1. Алгоритм решения ЗЛП с двумя переменными

Требуется решить задачу в следующей формулировке. Найти значения действительных переменных x1, x2, при которых целевая функция

L(X) = c1x1 + c2x2 + c

принимает экстремальное значение при ограничениях:

Прежде, чем перейти к описанию указанного алгоритма, напомним одно понятие. Линией уровня функции f(x1, x2) называется множество всех точек пространства R2, в которых функция принимает некоторое постоянное значение. Согласно этому определению, для целевой функции L(X) = c1x1 + c2x2+ c произвольная линия уровня L0 -- это прямая с вектором нормали (c1, c2).

Теорема 4. Значения целевой функции L(X) в точках линии уровня L0 возрастают, если линию уровня перемещать в направлении вектора нормали и убывают, если линию уровня перемещать в направлении, противоположном направлению вектора нормали.

Сформулированные теоремы позволяют представить алгоритм решения ЗЛП графическим методом:

Шаг 1. Находят область допустимых решений системы ограничений:

1.1. Если ОДР = , то задача неразрешима. Конец.

1.2. Если ОДР, то переходят к п. 2.

Шаг 2. Строят вектор (c1, c2).

Шаг 3. Проводят линию уровня L0 так, чтобы она имела с ОДР общие точки.

Шаг 4. Перемещают линию уровня по направлению вектора для задачи на максимум и в направлении, противоположном , для задачи на минимум. Перемещение производится до линии уровня, которая является границей полуплоскости, целиком содержащей ОДР:

Если такой линии не существует, то:

4.1.1. Lmax= +? при решении ЗЛП с максимизационным критерием;

4.1.2. Lmin= -? при решении ЗЛП с минимизационным критерием.

В обоих случаях задачу считают неразрешимой. Конец.

Если же указанная линия уровня существует, то точка, в которой целевая функция достигает максимального (минимального) значения, находится на этой прямой, обозначаемой L0+ (L0-):

4.2.1. Если линия уровня не параллельна ни одной из сторон ОДР, то это -- угловая точка ОДР.

4.2.2. Если линия уровня параллельна одной из сторон ОДР, то в этом случае возможны варианты: эта точка --

а) угловая точка ОДР или

б) любая точка соответствующей стороны.

Переходят к пункту 5.

Шаг 5. Находят координаты точек экстремума и значение целевой функции в них:

5.1. Если задача имеет единственное решение (случаи 4.2.1, 4.2.2а), то находят координаты точки экстремума и значение целевой функции в ней. Конец.

5.2. Если же имеет место случай 4.2.2б, то, говорят, что задача имеет альтернативный оптимум, и ее общее решение находится по формуле опт = X1+(1)X2, где 0л1, X1, X2 -- оптимальные решения в угловых точках ОДР (если такие, конечно, имеются). Конец.

Из рисунка, построенного в соответствии с указанным алгоритмом, всегда видно, разрешима ЗЛП или нет, а также существуют ли у ОДР вершины (см., например, рис. 5 и комментарии к нему). ОДР без угловых точек может быть только двух видов: полуплоскостью (рис. 3б) или областью, ограниченной двумя параллельными прямыми (рис. 3в). Как правило, в задачах реальной экономики отсутствие вершины -- явление, редко встречающееся.

Комментарии к рис. 5:

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

а) Максимального значения целевая функция достигает в точке А, минимального -- в точке В. Записывают это обычно следующим образом: Lmax= L(A), Lmin= L(B).

б) Максимального значения целевая функция достигает в любой точке отрезка AB, минимального -- в точке D.

в) В любой точке луча, отмеченного на рисунке, целевая функция принимает максимальное значение. Из рисунка видно, что прямой L0-, характеристическим свойством которой является свойство «быть границей полуплоскости, целиком содержащей ОДР», не существует, поэтому Lmin= -?, и задача на минимум неразрешима.

г) Lmax= +?, следовательно, ЗЛП с максимизационным критерием неразрешима. Минимальное значение целевая функция принимает в любой точке прямой L0-, одновременно являющейся стороной ОДР.

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

точка на прямой L0+ (или L0-);

отрезок на прямой L0+ (или L0-);

луч, все точки которого принадлежат прямой L0+ (или L0-);

прямая L0+ (или L0-).

Первый случай соответствует п. 4.2.1 и 4.2.2а, последние три -- п. 4.4.2б. Иллюстрацией может служить снова Рис. 5.

Итак, графический метод решения ЗЛП действительно позволяет избежать полного перебора вершин: если из рисунка видно, что некоторая угловая точка является единственной точкой пересечения линии уровня с ОДР, то нет необходимости вычислять координаты остальных вершин, так как указанная точка -- единственное оптимальное решение.

2. Иллюстративные примеры

Пример 1. Найти значения переменных x1, x2, при которых функция L(X) = 3x1 + 4x2 принимает экстремальные значения при условии, что:

x10, x20.

Решение. Введем на плоскости прямоугольную систему координат Ox1x2 (это позволит применить алгоритм графического метода).

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

Шаг 1. Для того чтобы найти множество точек, координаты которых удовлетворяют первым трем неравенствам системы ограничений, нужно построить граничные прямые

-x1 + x2 = 3,

5x1 + 3x2 = 97,

x1 + 7x2 = 74,

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

Более подробно. Находим точки пересечения прямой (1) с осями Ox1 и Ox2. Ими являются соответственно точки (-3; 0) и (0; 3). По этим точкам строим прямую (1). Затем подставляем координаты точки отсчета в неравенство -x1 + x23. Они ему удовлетворяют: 0 + 03. Следовательно, геометрическим местом точек, координаты которых удовлетворяют неравенству x1 + x23, является полуплоскость, содержащая точку O(0; 0) (рис. 7).

Замечание 6. Более общо. Для того чтобы узнать, какую полуплоскость описывает неравенство a1x1 + a2x2 b (знак неравенства выбран произвольно -- для определенности), нужно:

1) Построить прямую a1x1 + a2x2 = b.

2) Определить, по какую сторону от нее располагается точка O(0; 0) (или любая другая, не принадлежащая данной прямой):

· если координаты выбранной точки удовлетворяют данному неравенству, то полуплоскость, в которой находится эта выбранная точка, является искомой,

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

Множества точек, координаты которых удовлетворяют двум оставшимся неравенствам, изображены на рис. 6.

Из условий x10, x20 следует, что геометрический образ ОДР должен располагаться в первой четверти плоскости Ox1x2. Поэтому нас интересует только то, что находится в первой четверти. Пересечением полученных полуплоскостей является изображенный на рис. 8 треугольник ABD, представляющий собою область допустимых решений.

Шаг 2. Строим вектор (3; 4) (рис. 9).

Шаг 3. Линия уровня L0 задается уравнением 3x1+ 4x2 = const. На рис. 9 построена линия уровня, соответствующая значению 79.

Шаг 4. Сначала найдем значения переменных x1, x2, при которых целевая функция принимает максимальное значение. Поэтому перемещаем L0 по направлению вектора до линии уровня, являющейся границей полуплоскости, целиком содержащей ОДР (треугольник ABD). Такой линией является прямая L0+, проходящая через точку В. Следовательно, максимального значения целевая функция достигает в точке В (точке выхода из ОДР), координаты которой определяются как пересечение прямых (1) и (2).

Шаг 5. Решая систему

получим x1 = 11, x2 = 14. Таким образом, целевая функция имеет максимальное значение в точке (11; 14), при этом Lmax= 3·11+ 4·14 = 89.

1. Теперь найдем значения переменных x1, x2, при которых целевая функция минимизируется. Система ограничений -- прежняя. Следовательно, ОДР та же, что и максимизационной задаче. Поэтому решение начнем с шага 4. Перемещаем линию уровня в направлении, противоположном вектору . Из рисунка видно, что наименьшее значение L(X) на ОДР достигается в точке A -- точке пересечения прямых (1) и (3).