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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


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

Информация:

Тип работы: курсовая работа. Добавлен: 22.10.2012. Сдан: 2012. Страниц: 8. Уникальность по antiplagiat.ru: < 30%

Описание (план):


?Министерство образования Республики Беларусь
 
Учреждение образования
«Мозырский государственный педагогический университет им. И.П.Шамякина»
 
кафедра информатики и МПИ
 
 
 
 
 
 
 
Курсовая работа
 
Моделирование экономических процессов
 
Выполнила
студентка 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

Bj

Bn
A1
с11

с1j

с1n
a1
x11
x1j
x1n







Ai
ci1

cij

cin
ai
xi1
xij
xin







Am
cm1

cmj

cmn
am
xm1
xmj
xmn
Потребности
b1

bj

bn
 

 
Теорема 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, то есть идет как бы по диагонали таблицы с севера на запад.
Метод минимального элемента. При использовании метода северо-западного угла на каждом шаге потребности первого из оставшихся пунктов назначения удовлетворялись за счет запасов первого из оставшихся пунктов отправления. Очевидно, выбор пунктов назначения и отправления целесообразно производить, ориентируясь на тарифы перевозок, а именно: на каждом шаге следует выбирать какую-нибудь клетку, отвечающую минимальному тарифу (если таких клеток несколько, то следует выбрать любую из них), и рассмотреть пункты назначения и отправления, соответствующие выбранной клетке. Сущность метода минимального элемента и состоит в выборе клетки с минимальным тарифом. Следует отметить, что этот метод, как правило, позволяет найти опорный план транспортной задачи, при котором общая стоимость перевозок груза меньше, чем общая стоимость перевозок при плане, найденном для данной задачи с помощью метода северо-западного угла. Поэтому наиболее целесообразно опорный план транспортной задачи находить методом минимального элемента.
Метод аппроксимации Фогеля. При определении опорного плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.
Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбце (строке).

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

 
Для определения оптимального плана транспортной задачи разработано несколько методов. Однако наиболее часто используется метод потенциалов.
Метод потенциалов. Общий принцип определения оптимального плана транспортной задачи методом потенциалов аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.
Для определения опорного плана транспортной задачи будем пользоваться одним из методов, рассмотренных в предыдущем параграфе. Эти методы гарантируют получение занятых в исходной таблице условий п + т — 1 клеток; в некоторых из них могут стоять нули. Полученный план следует проверить на оптимальность.
Теорема 2. Если для некоторого опорного плана (, ) транспортной задачи существуют такие числа ?1, ?2, …, ?m, ?1, ?2, …, ?n, что
при                                           (1.6)
при                                           (1.7)
для всех и , то — оптимальный план транспортной задачи.
Определение 3. Числа ?i и ?j (;) называются потенциалами соответственно пунктов назначения и пунктов потребления.
Сформулированная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы ?i и ?j (;). Эти числа находят из системы уравнений
                                                        (1.8)
где cij — тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.
Так как число заполненных клеток равно п + т - 1, то система (1.8) с п+ m неизвестными содержит п + т - 1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например ?1= 0, и найти последовательно из уравнений (1.8) значения остальных неизвестных. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа .
Если среди чисел (;) нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки , то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых , и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.
Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной так называемым циклом.
Определение 4. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья — вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое — в столбце. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Примеры некоторых циклов показаны на рисунке 1.1.
При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл. После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану — переместить грузы в пределах клеток, связанных циклом с данной свободной клеткой. Это перемещение производят по следующим правилам:
1.      Каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке — знак плюс, а всем остальным клеткам — поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);
2.      В данную свободную клетку переносят меньшее из чисел xij, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел xij, считается свободной.
 
 
 
 
 
 
 
 
Рисунок 1.1 Примеры циклов для решения транспортной задачи
 
В результате указанных выше перемещений грузов в пределах клеток, связанных циклом с данной свободной клеткой, определяют новый опорный план транспортной задачи.
Описанный выше переход от одного опорного плана транспортной задачи к другому ее опорному плану называется сдвигом по циклу пересчета.
Следует отметить, что при сдвиге по циклу пересчета число занятых клеток остается неизменным, а именно — остается равным п + т — 1. При этом если в минусовых клетках имеется два (или более) одинаковых числа xij, то освобождают лишь одну из таких клеток, а остальные оставляют занятыми (с нулевыми поставками).
Полученный новый опорный план транспортной задачи проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа для всех свободных клеток. Если среди этих чисел не окажется положительных, то это свидетельствует о получении оптимального плана. Если же положительные числа имеются, то следует перейти к новому опорному плану. В результате итерационного процесса после конечного числа шагов получают оптимальный план задачи.
Из изложенного выше следует, что процесс нахождения решения транспортной задачи методом потенциалов включает пять этапов.
1.      Находят опорный план. При этом число заполненных клеток должно быть равным п + т — 1.
2.      Находят потенциалы ?i и ?j соответственно пунктов назначения и отправления.
3.      Для каждой свободной клетки определяют число ?ij. Если среди чисел ?ij нет положительных, то получен оптимальный план транспортной задачи; если же они имеются, то переходят к новому опорному плану.
4.      Среди положительных чисел ?ij () выбирают максимальное, строят для свободной клетки, которой оно соответствует, цикл пересчета и производят сдвиг по циклу пересчета.
5.      Полученный опорный план проверяют на оптимальность, то есть снова повторяют все действия, начиная с этапа 2.
В заключение отметим, что при определении опорного плана или в процессе решения задачи может быть получен вырожденный опорный план. Чтобы избежать в этом случае зацикливания, следует соответствующие нулевые элементы опорного плана заменить сколь угодно малым положительным числом ? и решать задачу как невырожденную. В оптимальном плане такой задачи необходимо считать ? равным нулю.


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

 
Обозначим через xij количество единиц продукции, перевозимого из i-гo пункта его получения на j-e предприятие. Тогда стоимость перевозки единицы продукции — cij, связанные с перевозкой единицы продукции из пункта Аi в пункт Bj. Условия доставки и вывоза необходимой и имеющейся продукции обеспечиваются за счет выполнения следующих неравенств:
                                                        (2.1)
При данном плане (, ) перевозок общая стоимость их составит
              (2.2)
Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (2.1), при котором целевая функция (2.2) принимает минимальное значение.
Мы имеем дело с открытой моделью транспортной задачи, в которой запасы продукции в пунктах потребления больше потребностей в этой продукции потребителей на 150 единиц:
.
Следовательно, 150 единиц продукции перевезены не будут. Поэтому введем фиктивный пункт назначения В5 с потребностью 150 единиц продукции и стоимостью перевозок равной 0 единиц.
Исходные данные задачи запишем в виде таблицы 2.1.
Найдем опорный план задачи с помощью метода минимального элемента. Для этого составим таблицу 2.2.
Минимальная стоимость перевозки с учетом себестоимости продукции, равная 5, находится в двух клетках для переменных x31 и х23 (клетки для переменных фиктивного пункта будем заполнять в последнюю очередь).
Таблица 2.1
Пункт отправления
Пункт назначения
Запасы
Себестоимость единицы продукции
В1
В2
В3
В4
В5
А1
4
5
8
6
0
350
2
А2
4
7
1
2
0
750
4
А3
2
6
4
7
0
300
3
Потребности
200
50
600
400
150
 
 
 
Положим x31=200 и x23=600, запишем эти значения в соответствующие клетки таблицы 2.2 и исключаем временно из рассмотрения столбцы В1 и В3. Загружаем клетку 2-2 — х24=150. Следовательно, строку А2 также временно выходит из рассмотрения. По индексам при поставках можно проследить за последовательностью загрузки клеток.
Таблица 2.2
Пункт отправления
Пункт назначения
Запасы
Себестоимость единицы продукции
В1
В2
В3
В4
В5
А1
4+2=6
5+2=7
8+2=10
6+2=8
0
350
2
+
504
 
2505
-        506
А2
4+4=8
7+4=11
1+4=5
2+4=6
0
750
4
 
 
6002
1503
 
А3
2+3=5
6+3=9
4+3=7
7+3=10
0
300
3
-      2001
 
 
 
+     1007
Потребности
200
50
600
400
150
 
 
 
В результате получим опорный план:
.
При данном плане перевозок общая стоимость перевозок с учетом себестоимости продукции составляет
Найденный опорный план проверяем на оптимальность — находим потенциалы пунктов отправления и назначения. Для определения потенциалов получаем систему
.
Полагая , находим
, , , , , ,.
Для каждой свободной клетки вычисляем число :
, , , , , , , .
Среди чисел положительных нет, значит, построенный план перевозок является оптимальным.
Следовательно, оптимальным является следующий план перевозок .
При таком плане перевозок общая стоимость перевозок с учетом себестоимости продукции составляет ден. единиц. Однако не выполняется дополнительное условие задачи: продукция пункта, в котором себестоимость ее производства наименьшая, распределяется полностью. Для нашей задачи таким является пункт А1. Значит, клетка 1-5 таблицы 2.2 должна быть пуста.
Для клетки 1-5 строим новый цикл и заполняем таблицу 2.3.
Таблица 2.3

и т.д.................


Пункт отправления
Пункт назначения
Запасы
Себестоимость единицы продукции
В1
В2
В3
В4
В5
А1
6
7
10
8
0
350

Перейти к полному тексту работы


Скачать работу с онлайн повышением уникальности до 90% по antiplagiat.ru, etxt.ru или advego.ru


Смотреть полный текст работы бесплатно


Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.