«Г.Г. Арунянц МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ ПРОЦЕССОВ Практикум Калининград, 2009 УДК 330.4(076.5) ББК 65в631я73 А79 Арунянц Г.Г. Моделирование экономических процессов: практикум. – Калининград: Балтийский институт А79 ...»

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

8. Экономическая интерпретация.

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

9. Прогнозирование неизвестных значений зависимой переменой.

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

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

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

В самом общем виде задача математически записывается так:

где X = ( x1, x2,..., xn ) ;

W – область допустимых значений переменных х1, х2,..., хn;

f(Х) – целевая функция.

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

Методы решения оптимизационных задач зависят как от вида целевой функции f(X), так и от строения допустимого множества W. Если целевая функция в задаче является функцией п переменных, то методы решения называют методами математического программирования.

В математическом программировании принято выделять следующие основные задачи в зависимости от вида целевой функции f(X) и от области – задачи линейного программирования, если f(X) и W линейны;

– задачи целочисленного программирования, если ставится условие целочисленности переменных xt, х2,..., хп;

– задачи нелинейного программирования, если форма f(X) носит нелинейный характер.

5.1. Задачи линейного программирования Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

При этом система линейных уравнений (5.3) и неравенств (5.4), (5.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(X) называется целевой функцией или критерием оптимальности.

В частном случае, если I =, то система (5.3) - (5.4) состоит только из линейных неравенств, а если I=M, то из линейных уравнений.

Если математическая модель задачи линейного программирования имеет вид:

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

Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации;

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

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

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на –1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

Пример. Приведение к канонической форме задачи линейного программирования:

Решение. Введем в каждое уравнение системы ограничений выравнивающие переменные х4, х5, X6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные х4, x6 вводятся в левую часть со знаком "+", а во второе уравнение вводится х со знаком "–".

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на – 1:

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

5.2. Примеры построения экономико-математических моделей задач линейного программирования Рассмотрим процесс построения математических моделей задач линейного программирования на примерах.

Пример 5.1. Определение оптимального ассортимента продукции.

Предприятие изготавливает два вида продукции – П1, и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья – А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П2 дан в табл. 5.1.

Опыт работы показал, что суточный спрос на продукцию П1 никогда не превышает спроса на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. в сутки.

Оптовые цены единицы продукции равны: 3 д.е. – для П1 и 4 д.е. для П2.

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

Процесс построения математической модели для решения поставленной задачи начинается с ответов на следующие вопросы (Таха Х.

Введение в исследование операций: В 2-х кн. – М.: Мир, 1985):

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

2. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?

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

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

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

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

Доход от реализации х1 единиц продукции П1 и х2 единиц продукции П2 составит F = 3 x1 + 4 x2.

Таким образом, мы приходим к следующей математической задаче:

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

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

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

Пример 5.2. Использование мощностей оборудования.

Предприятие имеет т моделей машин различных мощностей. Задан план по времени и номенклатуре: Т – время работы каждой машины;

продукции j-го вида должно быть выпущено не менее Nj единиц.

Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i-й машины по выпуску j-го вида продукции bij и стоимость единицы времени, затрачиваемого i-й машиной на выпуск j-го вида продукции сij.

Другими словами, задача для предприятия состоит в следующем:

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

По условию задачи машины работают заданное время Т, поэтому данное ограничение можно представить в следующем виде:

следующим образом:

Задача решается на минимум затрат на производство:

Необходимо также учесть неотрицательность переменных xij 0.

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

Пример 5.3. Минимизация дисбаланса на линии сборки.

Промышленная фирма производит изделие, представляющее собой сборку из m различных узлов. Эти узлы изготавливаются на n заводах.

Из-за различий в составе технологического оборудования производительность заводов по выпуску j-го узла неодинакова и равна bij.

Каждый i-й завод располагает максимальным суммарным ресурсом времени в течение недели для производства m узлов, равного величине Ti.

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

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

Пусть xij – недельный фонд времени (в часах), выделяемый на заводе i для производства узла j. Тогда объемы производства узла j будут следующими:

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

Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод i.

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

Максимизируем xij 0 для всех i и j.

Эта модель не является линейной, но ее можно привести к линейной форме с помощью простого преобразования. Пусть Y – количество изделий:

Этому выражению с математической точки зрения эквивалентна следующая формулировка: максимизировать Z = Y при ограничениях xij 0 для всех i и j; Y Пример 5.4. Задача составления кормовой смеси, или задача о диете [8].

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

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

Решение.

Введем условные обозначения:

xi – количество i-го сырья в смеси;

т – количество видов сырья;

п – количество ингредиентов в сырье;

аij – количество ингредиента j, содержащегося в единице i-го вида сырья;

bij – минимальное количество ингредиента, содержащегося в единице смеси;

сi - стоимость единицы сырья i;

q - минимальная общая масса смеси, используемая фирмой.

Задача может быть представлена в виде при следующих ограничениях:

на общий расход смеси:

на питательность смеси:

на неотрицательность переменных:

Пример 5.5. Задача составления жидких смесей.

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

Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m видов. Обозначим подлежащее определению количество литров i-го химического компонента, используемого для получения j-го продукта, через хij. Будем предполагать, что Первая группа ограничений относится к объемам потребляемых химических компонентов:

где Si – объем i-го химического компонента, которым располагает фирма в начале планируемого периода.

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

где Dj – минимальный спрос на продукцию у в течение планируемого периода.

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

где r – некоторая заданная константа.

Обозначив через Рij доход с единицы продукции xij, запишем целевую функцию:

Пример 5.6. Задача о раскрое или о минимизации обрезков.

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

Например, продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины L. По специальным заказам потребителей фирма поставляет рулоны других размеров, для этого производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров могут включать т видов шириной li (i = 1, m). Известна потребность в нестандартных рулонах каждого вида, она равна li. Возможны n различных вариантов построения технологической карты раскроя рулонов стандартной ширины L на рулоны длиной li.

Обозначим через aij количество рулонов i-го вида, получаемых при раскрое единицы стандартного рулона по j-му варианту. При каждом варианте раскроя на каждый стандартный рулон возможны потери, равные Рj. К потерям следует относить также избыточные рулоны нестандартной длины li, получаемые при различных вариантах раскроя yij, j = 1, n.

В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при j-м варианте раскроя. Определим переменную следующим образом: xj - количество стандартных рулонов, разрезаемых по варианту j, j = 1, n.

Целевая функция минимум отходов при раскрое Ограничение на удовлетворение спроса потребителя Пример 5.7. Многосторонний коммерческий арбитраж (Таха X.

Введение в исследование операций: В 2-х кн. – М.: Мир, 1985).

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

Представим себе коммерсанта (условно назовем его N), имеющего возможность реализовать многосторонний коммерческий арбитраж.

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

При трансакции x1 продажа единицы валютного номинала (ценных бумаг) II позволяет приобрести r11 единиц валютного номинала I. При трансакции x7 взамен единицы валютного номинала I можно получить r единиц валютного номинала III и r67 единиц валютного номинала VI.

Остальные трансакции расшифровываются аналогично. Значения rij могут быть дробными. Заметим, что при любой трансакции xi (i = 1, 2, 3, 4, 5) каждый из валютных номиналов можно обменять на валютный номинал I.

Следует обратить внимание на правило выбора знака перед показателями в табл. 5.2. Чтобы отличать куплю от продажи, будем соответственно использовать знаки "плюс" и "минус" перед показателями, характеризующими данную трансакцию.

Размер транcакции Рассмотрим идеализированный случай, когда все трансакции коммерсанта N выполняются одновременно. Ограничения определяются единственным требованием – трансакция возможна лишь при условии, если коммерсант N располагает наличными ценными бумагами. Другими словами, количество проданных ценных бумаг не должно превышать количество приобретенных. Данные ограничения имеют вид Пусть целевая функция представляет собой чистый доход, выраженный в единицах валютного номинала I, т.е. задача состоит в том, чтобы Пример 5.8. Транспортная задача.

Имеются три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их cij, i = 1,3; j = 1,4. Запасы грузов у поставщиков равны c ij, i = 1,3; j = 1,4. Известны потребности каждого потребителя b j, j = 1,4. Будем считать, что суммарные потребности равны суммарным запасам:

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

Введем переменные хij – количество груза, перевозимого от i-го поставщика j-му потребителю.

Ограничения задачи выглядят следующим образом:

· потребности всех потребителей должны быть удовлетворены полностью:

или в общем виде:

· груз поставщика должен быть вывезен полностью:

или в общем виде:

· условие неотрицательности переменных:

перевозку:

Количество поставщиков и потребителей в общем случае может быть произвольным ( 2 ).

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

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

2. Линейная функция может стремиться как к максимуму, так и к минимуму.

3.Переменные в задачах всегда неотрицательны.

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

5.3. Графические методы решения задач линейного Графический способ решения задач линейного программирования целесообразно использовать для:

– решения задач с двумя переменными, когда ограничения выражены неравенствами;

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

переменными:

· целевая функция:

· ограничения:

Каждое из неравенств (5.35) - (5.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ai1 x1 + ai 2 x2 = bi ; (i = 1, m); x1 - 0; x2 = 0. В том случае, если система неравенств (5.35) - (5.36) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых решений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств.

Областью допустимых решений системы неравенств (5.35)-(5.36) может быть:

– выпуклый многоугольник;

– выпуклая многоугольная неограниченная область;

– пустая область;

– единственная точка.

Целевая функция (5.34) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z.

Вектор C = (c1; c2 ) с координатами с1 и с2, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор – направление убывания Z.

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

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

Для определения данной вершины построим линию уровня перпендикулярную вектору С = (с1; с2), и будем передвигать ее в направлении вектора C = (c1; c2 ) до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяют оптимальный план данной задачи.

Заканчивая рассмотрение геометрической интерпретации задачи (5.34)-(5.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 5.1-5.4. Рис. 5.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 5.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ.

На рис. 5.3 изображен случай, когда максимум недостижим, а на рис.

5.4 – случай, когда система ограничений задачи несовместима.

Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора C = (c1; c2 ), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения.

Для практического решения задачи линейного программирования (5.34)-(5.36) на основе ее геометрической интерпретации необходимо следующее.

1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (5.35)-(5.36) знаков неравенств на знаки равенств.

2. Найти полуплоскости, определяемые каждым из ограничений задачи.

3. Определить многоугольник решений.

4. Построить вектор C = (c1; c2 ).

5. Построить прямую Z = c1 x1 + c2 x 2 = 0, проходящую через начало координат и перпендикулярную вектору С.

6. Передвигать прямую Z = c1 x1 + c2 x2 в направлении вектора С, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов.

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

Пример 5.9. Рассмотрим решение задачи об ассортименте продукции (Пример 5.2) геометрическим способом.

Построим многоугольник решений (рис. 5.5). Для этого в системе координат Х10Х2 на плоскости изобразим граничные прямые:

Взяв какую-либо точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство.

Полуплоскости, определяемые неравенствами, на рис. 5.5 показаны стрелками. Областью решений является многоугольник OABCD.

Для построения прямой Z = 3x + 4 x2 = 0 строим вектор-градиент C = (3;4) и через точку 0 проводим прямую, перпендикулярную ему.

Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора C. Из рис. 5.5 следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L1 и L3. Для определения ее координат решим систему уравнений:

Оптимальный план задачи х1 = 2,4; x2=1,4. Подставляя значения х1 и х2 в линейную функцию, получим: Z max = 3 2,4 + 4 1,4 = 12,8.

Рис. 5.5. Решение задачи линейного программирования Полученное решение означает, что объем производства продукции П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д.е.

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

исключения x1 и x4:

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

Построим многоугольник решений и линейную функцию в системе координат Х20Х3 (рис. 5.6). Согласно рис. 5.6, линейная функция принимает максимальное значение в точке А, которая лежит на пересечении прямых L2 и Х2=0. Ее координаты (0;0,23).

Рис. 5.6. Геометрическая интерпретация решения задачи Максимальное значение функции Для отыскания оптимального плана исходной задачи подставляем в преобразованную систему х 2 и x 3. Окончательно получаем X=(1,078;

0; 0,23; 0,001).

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

Рассмотрим систему ограничений и линейную форму вида:

Используя метод Жордана – Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения:

x1, x2,..., xr – базисные переменные;

xr +1, xr +2,..., xn - свободные переменные.

По последней системе ограничений и целевой функции Z построим табл. 5.3.

Свободные неизвестные Базисные неизвестные Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.

Алгоритм симплекс-метода сводится к следующему.

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

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

3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.

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

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

6. Элемент табл. 5.4, соответствующий разрешающему элементу табл. 5.3, равен обратной величине разрешающего элемента.

7. Элементы строки табл. 5.4, соответствующие элементам разрешающей строки табл. 5.3, получаются путем деления соответствующих элементов табл. 5.3 на разрешающий элемент.

Свободные неизвестные Базисные неизвестные 8. Элементы столбца табл. 5.4, соответствующие элементам разрешающего столбца табл. 5.3, получаются путем деления соответствующих элементов табл. 5.3 на разрешающий элемент и берутся с противоположным знаком.

9. Остальные элементы вычисляются по правилу прямоугольника:

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

Тогда искомый элемент из табл. 5.4 будет равен соответствующему элементу табл. 5.3 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе – произведение элементов из двух неиспользованных вершин прямоугольника.

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

11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).

Пример 5.11. Решение задачи симплекс-методом:

Приведем задачу к виду, допускающему применение симплексалгоритма:

Подставим в выражение Zmax величины х3, х4, х5:

По алгоритму целевая функция должна стремиться к минимуму:

Составим симплекс-таблицу:

Свободные неизвестные Базисные неизвестные Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен +6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной х4 и столбца -х1.

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

Свободные неизвестные Базисные неизвестные В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Z min = -9; X = (0;0;2;1;1); Z max = - Z min = 9.

5.5. Задания для самостоятельной работы по построению математических моделей задач линейного программирования Задание 5.1. Автотранспортному предприятию (АТП) необходимо освободить из-под груза складские помещения клиента. Вывоз груза следует осуществить в два рейса колоннами автомобилей. Условия перевозки требуют, чтобы в составе каждой колонны, предназначенной для вывоза груза в первый район, было 8 автомобилей ЗИЛ-131 и автомобилей ЗИЛ-130; в колоннах второго рейса 8 автомобилей ЗИЛ- и 16 – МАЗ-500. Каждая из колонн может сделать за сутки одинаковое количество поездок. Парк подвижного состава АТП состоит из автомобилей ЗИЛ-131 грузоподъемностью 3 т, 48 автомобилей ЗИЛ- грузоподъемностью 4 т, 48 автомобилей МАЗ-500 грузоподъемностью 7,5 т.

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

Задание 5.2. Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:

Число пассажиров Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?

Задание 5.3. Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 т. Овощехранилища имеют соответственно 20, 20, 15 и 25 т.

Тарифы (в д.е. за 1 т) указаны в следующей таблице:

Овощехранилища транспортные расходы.

Задание 5.4. Имеются два склада готовой продукции: А1 и А2 с запасами однородного груза 200 и 300 т. Этот груз необходимо доставить трем потребителям: В1, В2 и В3 в количестве 100, 150, 250 т соответственно. Стоимость перевозки 1т груза из склада А1 потребителям В1, В2 и В3 равна 5, 3, 6 д.е., а из склада А2 тем же потребителям – 3, 4, д.е. соответственно.

транспортные расходы.

Задание 5.5. При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице:

Питательные Количество единиц питательных веществ на 1 кг Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е.

Составьте дневной рацион питательности, имеющий минимальную стоимость.

Задание 5.6. Хозяйство располагает следующими ресурсами:

площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции П1, П2, П3, П4. Организация производства характеризуется следующей таблицей:

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

Задание 5.7. Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 т, проволоки – 18 т. На один трансформатор первого вида расходуется 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуется 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е.

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

Задание 5.8. Совхоз отвел три земельных массива размером 5000, 8000, 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей ниже таблице.

За 1 ц ржи совхоз получает 2 д.е., за 1 ц пшеницы – 2,8 д.е., за 1 ц кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 т ржи, 158000 т пшеницы и 30000 т кукурузы?

I II III

Задание 5.9. Три типа самолетов следует распределить между четырьмя авиалиниями. Данные об организации процессов перевозок приведены в таблице.

самолета

I II III IV I II III IV

Распределите самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных затратах перевезти по каждой из четырех авиалиний соответственно не менее 300, 200, 1000, 500 ед. груза.

Задание 5.10. Имеются четыре оперативные базы и три цели. В силу различия в типах самолетов и высоте полета масса бомб, доставляемых с любой базы к любой цели, определяется по следующей таблице:

I II III

Дневная интенсивность каждой базы составляет 150 самолетовылетов в день. На каждую цель необходимо организовать 200 самолетовылетов в день. Определите план вылетов с каждой базы к каждой цели, дающий максимальную общую массу бомб, доставляемых к целям.

Задание 5.11. Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед.

– вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:

Продукт Составьте наиболее дешевую смесь.

Задание 5.12. В институте проводится конкурс на лучшую стенгазету. Одному студенту дано следующее поручение:

· купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.;

· красок нужно купить не менее трех коробок, блокнотов - столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е.

В каком количестве студент должен купить указанные предметы, чтобы общее число предметов было наибольшим?

Задание 5.13. Заводы № 1, 2, 3 производят однородную продукцию в количестве соответственно 500, 400 и 510 единиц. Себестоимость производства единицы продукции на заводе № 1 составляет 25 д.е., на заводе № 2 – 20 д.е., на заводе № 3 – 23 д.е. Продукция отправляется в пункты А, В, С, потребности которых равны 310, 390 и 450 единицам.

Стоимости перевозок 1 ед. продукции заданы матрицей Составьте оптимальный план перевозок продукции при условии, что коммуникации между заводом № 2 и пунктом А не позволяют пропускать в рассматриваемый период более 250 единиц продукции.

Задание 5.14. Цех выпускает три вида деталей – А, В, С. Каждая деталь обрабатывается тремя станками. Организация производства в цехе характеризуется следующей таблицей:

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

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

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

Задание 5.16. На предприятии для производства запасных частей для автомобилей используются три вида ресурсов. Выпускаются три вида запасных частей. Организация производства на предприятии характеризуется следующей таблицей.

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

Задание 5.17. Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозку одного двигателя из районов к мастерским следующие:

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

Задание 5.18. Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е.

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

Задание 5.19. Планируется нанесение удара по некоторому объекту тремя различными видами оружия: оружием А – в течение 3 мин., оружием Б – в течение 5 мин., оружием В – в течение 4 мин. Возможности средств обеспечения стрельбы таковы, что при применении оружия А в течение 3 мин., оружия Б в течение 2 мин., оружия В в течение 4 мин.

общее количество залпов не должно превышать 15. При применении оружия А в течение 2 мин. и оружия В в течение 3 мин. общее количество залпов не должно превышать 8 ед. Кроме того, для преодоления противодействия противника необходимо, чтобы количество залпов оружием В за 1 мин. было больше, чем 5 ед.

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

Задание 5.20. Имеется 5 ракет и 5 целей. Вероятность поражения цели каждой из ракет задана в следующей таблице:

Распределите ракеты по целям так, чтобы математическое ожидание числа пораженных целей было максимальным.

Задание 5.21. Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов.

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

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

Задание 5.22. Предприятию задана месячная программа на изготовление четырех типов изделий в количествах соответственно 5000, 2000, 3000 и 1800 шт. На предприятии имеются три группы станков с различной производительностью. Суммарное допустимое время для каждой группы станков составляет соответственно 800, 1000, 1500 час.

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

№ группы станков

I II III IV I II III IV

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

Задание 5.23. Звероферма выращивает черно-бурых лисиц и песцов.

На звероферме имеется 10 000 клеток. В одной клетке могут быть либо лисы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е.

Какое количество лисиц и песцов нужно держать на ферме, чтобы получить наибольшую прибыль?

Задание 5.24. Найдите оптимальное распределение трех видов механизмов, имеющихся в количествах 45, 20 и 35, между четырьмя участками работ, потребности которых соответственно равны 10, 20, 30, при следующей матрице производительности:

Задание 5.25. Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 т зерна. Зерно необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 т каждому. Расстояние от элеватора до хлебозаводов указано в следующей таблице:

Элеваторы Затраты на перевозку 1 т продукта на 1 км составляют 25 д.е.

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

Задание 5.26. Из двух сортов бензина образуются две смеси – А и В.

Смесь А содержит бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е.

Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензина 50 т 1-го сорта и 30 т 2-го сорта.

Задание 5.27. Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн га. Данные об урожайности зерновых культур приведены в следующей таблице:

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

Задание 5.28. На строительство четырех объектов кирпич поступает с трех заводов. Заводы имеют на складах соответственно 50, 100 и 50 тыс.

шт. кирпича. Объекты требуют соответственно 50, 70, 40, 40 тыс. шт.

кирпича. Тарифы (в д.е./тыс. шт.) приведены в следующей таблице:

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

Задание 5.29. Для полива различных участков сада, на которых растут сливы, яблони, груши, служат три колодца. Колодцы могут дать соответственно 180, 90 и 40 ведер воды. Участки сада требуют для полива соответственно 100, 120 и 90 ведер воды. Расстояния (в метрах) от колодцев до участков сада указаны в следующей таблице:

Как лучше организовать полив?

Задание 5.30. На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех типов:

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

I II III IV

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

5.6. Задания для самостоятельной работы по решению задач линейного программирования графическим методом Задание 5.42.

Задание 5.43.

Задание 5.44.

Задание 5.45.

Задание 5.46.

Задание 5.47.

Задание 5.49.

Задание 5.52.

Задание 5.53.

5.7. Задания для самостоятельной работы по решению задач линейного программирования симплекс-методом [4] Решение всех заданий осуществить с использованием встроенной графики Word.

5.8. Примеры решения задач линейного программирования Электронные таблицы, или, как их еще называют, табличные процессоры – это удобное средство проведения расчетов и анализа результатов. Они предназначены для работы с большими таблицами чисел, в основном, для организации относительно несложных расчетов с большим количеством идентичных данных, например, бухгалтерского учета. Значительное число задач в экономике составляют задачи распределения ресурсов и так называемые транспортные задачи. Наиболее часто математической моделью таких задач является задача линейного программирования. Ниже приводятся примеры решения таких задач с использованием среды MS Excel. Освоение основных приемов использования стандартных механизмов Excel при решения указанных задач, заключенного в надстройке "Поиск решения", позволит успешно решать большинство приведенных выше заданий с использованием этих технологий.

5.8.1. Решение задачи распределения ресурсов Значительное число задач в экономике составляют задачи распределения ресурсов. Наиболее часто математической моделью таких задач является задача линейного программирования.

Суть задачи о распределении ресурсов Предположим, имеются какие-либо ресурсы (сырье, рабочая, сила, оборудование):

в количествах, соответственно:

единиц ресурсов.

С помощью ресурсов R1, R2, …, Rm могут производиться различные товары Для производства одной единицы товара Tj необходимо aij единиц ресурса Ri (i = 1, 2, …, m; j = 1, 2, …, n), где m – количество ресурсов, n – количество видов продукции.

Каждая единица ресурса Ri стоит di рублей (i = 1, 2, …, m). Каждая единица товара может быть реализована по цене сj (j = 1, 2, …, n).

Количество произведенных единиц должно быть ограничено спросом, т.к. рынок не может поглотить больше, чем kj единиц товара T (j = 1, 2, …, n).

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

Введем некоторые обозначения:

x1, x2, …, xn – количества товаров T1, T2, …, Tn, запланированных к производству.

Условия спроса налагают на эти величины следующие ограничения:

Нельзя израсходовать ресурсов больше, чем имеется в наличии.

Следовательно, получаем ограничения по использованию ресурсов:

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

Теперь необходимо выразить прибыль L в зависимости от элементов решения x1, x2, …, xn, т.е. планируемых объемов производства продукции.

Для этого сначала необходимо определить себестоимость товара.

Себестоимость sj единицы товара Tj будет равна:

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

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

Прибыль от реализации одного какого-либо вида продукции qi будет рассчитываться по формуле:

где ci – продажная (отпускная) цена какого-либо вида продукции, si – себестоимость вида продукции; i = 1, 2, …, n; n – кол-во видов продукции.

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

Общая прибыль от реализации всех видов продукции составит:

где qi – прибыль от реализации единицы продукции; xi – объем производства данного вида продукции.

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

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

Пример решения В Excel имеется стандартный механизм разрешения подобных задач, заключенный в надстройке "Поиск решения". Для его использования необходимо активировать данную надстройку: Сервис ® Надстройки … Далее активировать элемент списка Поиск решения, как это показано на рис. 5.7, и нажать OK. После этого опция Поиск решения станет доступна в меню Сервис.

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

Балтийский институт 95 Моделирование эконом. процессов.

Какие же формулы должны быть введены в ячейки, отмеченные черным цветом? Это формулы, рассчитывающие соответствующие значения математических выражений, рассмотренных выше:

1. В ячейку E8 должна быть введена формула, рассчитывающая целевую функцию (ЦФ). Целевая функция, как было рассмотрено выше, для задачи распределения ресурсов представляет собой сумму произведений переменных "прибыль от реализации единицы продукции" (qi) на объем производства данной продукции (xi), т.е.

L = q1x1 + q2x2 + … + qnxn.

Так как qi - коэффициенты целевой функции, представленные в ячейках диапазона B8:D8, а xi – объемы производства, которые будут после решения задачи представлены в ячейках B5:D5, то формула расчета целевой функции должна рассчитывать сумму произведений ячеек B5:D на B8:D8.

Для расчета суммы произведений диапазонов ячеек предусмотрена математическая функция Excel "СУММПРОИЗВ".

= СУММПРОИЗВ(Список перемножаемых диапазонов) Для расчета целевой функции необходимо в ячейку E8 ввести формулу Теперь необходимо ввести ограничения использования ресурсов – систему неравенств-ограничений, исходные данные которой должны быть представлены в секции "Ограничения".

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

Так как объемы производства представлены в диапазоне ячеек B5:D5, а количество ресурса, необходимое для производства единицы продукции, представлено в диапазонах B12:D12 (для ресурса "Ресурс1"), B13:D13 (для ресурса "Ресурс2"), B14:D14 (для ресурса "Ресурс3"), то в ячейках E12:E14 соответственно должны быть формулы:

т.е. суммы произведений соответствующих ячеек.

После ввода формул в ячейки форма примет следующий вид (рис.

5.9):

Балтийский институт 97 Моделирование эконом. процессов.

экономики и финансов Практикум. Калининград, 2009.

Если включить режим отображения формул (Сервис ® Параметры … ® Вид ® Параметры окна ® Формулы ® Ok), то форма примет следующий вид (рис. 5.10):

Отключить режим отображения формул можно аналогичным способом.

После ввода формул необходимо ввести исходные данные задачи.

Исходные данные Имеются три вида продукции, объемы производства обозначены соответственно x1, x2, x3. Для производства требуются три ресурса (например, труд, сырье, финансы). Использование каждого ресурса для единицы каждого вида продукции выражается коэффициентами при переменных x1, x2, x3 в следующей системе неравенств:

где первое неравенство – ограничение по ресурсу1, второе – по ресурсу2, третье – по ресурсу3. Правая часть неравенств отражает ограничение по использованию данного ресурса для производства.

Целевая функция выглядит следующим образом:

Из условия задачи видно, что значения коэффициентов при переменных первого уравнения необходимо ввести в ячейки B12, C12, D соответственно. Значения коэффициентов второго уравнения необходимо ввести в ячейки B13, C13, D13 формы, коэффициенты третьего уравнения – в ячейки B14, C14, D14.

Правую часть неравенств уравнений необходимо ввести соответственно для первого уравнения – в ячейку G12, для второго – в ячейку G13, третьего – G14.