Моделирование экономических процессов

Министерство образования Республики Беларусь

Учреждение образования

«Мозырский государственный педагогический университет им. И.П.Шамякина»

кафедра информатики и МПИ

Курсовая работа

Моделирование экономических процессов

Выполнила
студентка 4 курса 8 группы
инженерно-педагогического
факультета
 

Научный руководитель:
Полоз М.И.

Оценка научного руководителя:                           

              оценка, дата сдачи, подпись

Итоговая оценка:                            

Мозырь 2011

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

УСЛОВИЕ ЗАДАЧИ И ИСХОДНЫЕ ДАННЫЕ

ГЛАВА 1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

1.1              Математическая постановка задачи

1.2              Определение опорного плана транспортной задачи

1.3              Определение оптимального плана транспортной задачи

ГЛАВА 2 РЕШЕНИЕ ЗАДАЧИ МАТЕМАТИЧЕСКИ

ГЛАВА 3 РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ ЭЛЕКТРОННЫХ ТАБЛИЦ MICROSOFT EXCEL

ЗАКЛЮЧЕНИЕ

СПИСОК ИСОПЛЬЗОВАННЫХ ИСТОЧНИКОВ

ВВЕДЕНИЕ

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

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

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

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

Для достижения поставленной цели необходимо решить следующие задачи. Это:

1.      Математическая постановка задачи и описание методов решения (нахождение опорного плана, метод потенциалов);

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

УСЛОВИЕ ЗАДАЧИ И ИСХОДНЫЕ ДАННЫЕ

В пунктах Аi () производится однородная продукция в количествах а1 = 350, а2 = 750 и а3 = 300 единиц. Себестоимость единицы продукции в i-ом пункте равна 2, 4 и 3 ден. единиц. Готовая продукция поставляется в пункты Bj (), потребности которых составляют b1 = 200, b2 = 50, b3 = 600 и b4 = 400 единиц. Стоимости Cij перевозки единицы продукции из пункта Аi в пункт Bj заданы матрицей:

.

Требуется:

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

2.      Вычислить суммарные затраты fmin;

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

ГЛАВА 1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

1.1    Математическая постановка задачи

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления А1, А2, …, Ат, в п пунктов назначения В1, В2, ..., Вn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через cij тарифы перевозки единицы груза из i-гo пункта отправления в j-й пункт назначения, через ai — запасы груза в i-м пункте отправления, через bj— потребности в грузе в j-м пункте назначения, а через xij — количество единиц груза, перевозимого из i-гo пункта отправления в j-й пункт назначения. Тогда математическая постановка транспортной задачи состоит в определении минимального значения функции

                                          (1.1)

при условиях

()                                          (1.2)

()                                          (1.3)

.                                          (1.4)

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

Определение 1. Всякое неотрицательное решение систем линейных уравнений (1.2) и (1.3), определяемое матрицей (;), называется планом транспортной задачи.

Определение 2. План (;), при котором функция (1.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные транспортной задачи записывают в виде таблицы (табл. 1.1).

Очевидно, общее наличие груза у поставщиков равно , a общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, то есть

,                                           (1.5)

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

Таблица 1.1

Модель транспортной задачи

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

В случае превышения запаса над потребностью, то есть при

вводят фиктивный (n + 1)-й пункт назначения с потребностью

и соответствующие тарифы считают равными нулю:

().

Полученная задача является транспортной задачей, для которой выполняется равенство (1.5).

Аналогично, при вводят фиктивный (т + 1)-й пункт отправления с запасом груза и соответствующие тарифы полагают равными нулю:

().

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

Число переменных хij в транспортной задаче с т пунктами отправления и п пунктами назначения равно пт, а число уравнений в системах (1.2) и (1.3) равно п + т. Так как мы предполагаем, что выполняется условие (1.5), то число линейно независимых уравнений равно п + т - 1. Следовательно, опорный план транспортной задачи может иметь не более п + т - 1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности п + т - 1, то план является невырожденным, а если меньше — то вырожденным.

Для определения опорного плана существует несколько методов. Три из них — метод северо-западного угла, метод минимального элемента и метод аппроксимации Фогеля — рассматриваются ниже.

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

1.2    Определение опорного плана транспортной задачи

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

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

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

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

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

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