Posobie1

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

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

Г. И. Горемыкина М. А. Ляшко

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

Учебное пособие для студентов физико-математических и экономических

факультетов

Балашов

2011

1

УДК 517.1

ББК 22.14я73+22.143

Г67

Рецензенты:

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

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

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

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

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

ISBN 978-5-94035-450-5

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

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

2

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

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

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

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

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

5

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

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

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

идополнительной, — может быть использован при написании курсовых

идипломных работ.

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

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 должны быть неотрицательны:

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

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

7

n

aij x j bi, i =1, 2, …, m.

j 1

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

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);

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

8

Рассмотрим математическую модель данной экономической ситуации. Обозначим через 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,

n

aij x j bi, i =1, 2,…, m;

j 1

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. При этом, конечно, xij 0 (i=1, 2,…, m; j = 1, 2,…, n). Тогда xi1 + xi2 +...+ xin — это общее количество груза, которое можно отправить из пункта Аi в пункты В1,…, Вn, а x1j+x2j+...+xmj — общее количество груза, которое можно принять в пункте Вj из пунктов

9

А1,…, Аm. Предположение о совпадении суммарных запасов груза и суммарных потребностей в нем приводит к системе линейных равенств

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

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

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

i 1

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

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

Замечание 3. Сделаем несколько уточнений. Рассмотренная задача на-

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

тах отправления невостребованным. Тогда вводят гипотетического (виртуального) (n + 1)-го получателя с готовностью принять груз указанного

10