Оптимальное распределение ресурсов

 ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ РФ

ФГОУ СПО «Острогожский  аграрный техникум»

 

 

 

 

 

 

 

 

 

КУРСОВАЯ РАБОТА

 

по дисциплине: «МАТЕМАТИЧЕСКИЕ  МЕТОДЫ»

 

Тема: «ОПТИМАЛЬНОЕ РАСПРЕДЕЛЕНИЕ  РЕСУРСОВ»

 

 

 

 

 

Работу выполнила:

студентка группы  К-31

отделения

«Программное обеспечение

вычислительной техники  и

автоматизированных систем»

Корнилова Любовь Викторовна

 

 

Преподаватель:

Гончарова Ольга Николаевна

 

 

ОЦЕНКА__________

 

 

 

 

 

ОСТРОГОЖСК 2008

 

ЗАДАНИЕ 

Составить экономико-математическую модель транспортной задачи и автоматизировать ее средствами MS Excel.

Четыре предприятия данного  экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого  из предприятий соответственно равно 120,50,190 и 110 ед. Сырье сосредоточено  в трех местах его получения, а запасы соответственно равны 160,140,170ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей:

   С =    

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

 

 

 

 

 

 

 

 

СОДЕРЖАНИЕ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основные задачи выполнения работы:

1. углубить теоретические знания, полученные в процессе освоения дисциплины;
2. выработать практические навыки в решении задач транспортного типа и их анализа;
3. выработать умение самостоятельно разрабатывать математическую модель задач транспортного типа;
4. научиться применять на практике приемы и способы решения транспортных задач;
5. выработать умение логически грамотно иллюстрировать решение задачи транспортного типа с помощью таблиц.

 

 

 

 

 

 

 

 

 

 

 

ТЕОРЕТИЧЕСКАЯ  ЧАСТЬ

МАТЕМАТИЧЕСКАЯ ФОРМУЛИРОВКА ТРАНСПОРТНОЙ ЗАДАЧИ, ОСНОВНЫЕ ПОНЯТИЯ И  АЛГОРИТМ РЕШЕНИЯ

Общая постановка транспортной задачи

Общая постановка транспортной задачи состоит в определении  оптимального плана перевозок некоторого однородного груза из m пунктов отправления A₁,A₂,…,A_m в n пунктов назначения B₁,B₂,…,B_n .При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

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

a₁ + а₂ +…+ а_m = b₁ + b₂ + …+ b_n

Модель транспортной задачи называется открытой, если запасы не равны потребностям:     а₁ + a₂ +…+ a_m >(<) b₁ + b₂ +…+ b_n

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

                    

Пункты отправления	Пункты отправления				Запасы в пунктах  отправления
	В1	В2		Вn
A1	C11   X11	C12                         X12	…	C1n   X1n	а1
A2	С21   Х21	С22   Х22	…	С2n   Х2n	а2
. .			…
Am	Cm1     Xm1	Cm2     Xm2	…		am
Потребность в пунктах  потребления	b1	b2	…	bn

 

            Математическая модель задачи  будет выглядеть так:

 

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

 

ограничения по потреблению их –  по столбцам и представляют систему  уравнений (2).

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

Z_min(max) = c₁₁x₁₁+c₁₂x₁₂+…+c_mnx_mn         (3)

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

При для  решении транспортных задач, нам нужно воспользоваться:

 

1. Поиск допустимого решения

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

Для проверки правильности распределения ресурсов и удовлетворения потребностей необходимо суммировать объем перевозок, как по строкам, так и по столбцам. После этого план проверяется на оптимальность.

Условимся называть клетки матрицы, соответствующие положительным компонентам плана, занятыми (базисными), а остальные – свободными (небазисными). Число занятых клеток в опорном плане должно быть m + n-1. В случае, когда их оказывается меньше, одну из свободных клеток условно считают занятой и проставляют в ней перевозки х_ij=0. При этом надо следить за тем, чтобы условно занятая клетка не образовывала с другими занятыми клетками замкнутых контуров.

2. Проверка допустимого решения на оптимальность.

Для поверки плана  на оптимальность:

1) для занятых клеток рассчитывают потенциалы клеток U_i и V_j, которые определяются по формуле: U_i+V_j=C_ij и записывается в специальный столбец и строку.

Первый опорный план:

Задав одной из неизвестных U_i или V_j произвольное значение, например U₁=0, находим все U_i и V_j. Так, U₁+V₁=C₁₁, откуда V₁=C₁₁-U₁.

2) для свободных клеток рассчитывают величину: l_ij=C_ij - (U_i+V_j ), которая указывает экономию или перерасход по сравнению с предыдущим планом при перемещении единицы груза в данную точку.

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

3. Поиск решения более близкого к оптимальному.

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

В вершине свободной  клетки ставится знак “+”, в остальных  клетках – знаки “+” и ”-”  чередуются.

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

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

 

 

ПРАКТИЧЕСКАЯ  ЧАСТЬ

АВТОМАТИЗАЦИЯ ОПТИМАЛЬНОГО ПЛАНА ВЫПУСКА ПРОДУКЦИИ  СРЕДСТВАМИ MS EXCEL

Математическая  модель

Пусть х_ij-количество продукции, выпускаемого i-ым предприятием (i=1…,3) j-го вида сырья (j=1…,4).

Так как запасы сырья  на предприятиях соответственно равны 160,140 и 170, то мы можем составить систему ограничения относительно запасов:

        Зная, потребности в сырье каждого из предприятий 120,50,190 и 110, можно записать систему ограничения относительно потребности:

         

 Учитывая тарифы  перевозок, общая стоимость всей  перевозки равна:

           Z_min=7x₁₁+8x₁₂+x₁₃+2x₁₄+4x₂₁+5x₂₂+9x₂₃+8x₂₄+9x₃₁+2x₃₂+3x₃₃+6x₃₄        

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

160 +140 +170 =120 +50 +190 +110   – следовательно, это транспортная  задача с закрытой моделью.

Поиск допустимого  решения

Первый опорный план для решения транспортной задачи, составим методом северо-западного угла.

Сырье	Предприятия				Запасы
	1	2	3	4
1	7 120	8 40	1 X13	2 X14	160
2	4 X21	5 10	9 130	8 X24	140
3	9 X31	2 X32	3 60	6 110	170
Потребность	120	50	190	110	470