Оптимизация транспортировки продукции

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА  РФ

 

Иркутская Государственная  Сельскохозяйственная Академия

 

 

 

 

 

 

 

 

 

 

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

на  тему:

 

 

«Оптимизация транспортировки продукции»

 

 

 

 

 

 

 

                                                                        

 

 

 

                                                                          ВЫПОЛНИЛА:

                                                                                       студентка 4 курса, 5 гр.                                                                           

                                                                                                  агрономического ф-та

                                                                     Петров Г.И.

                                                                         ПРОВЕРИЛА:

                                                                    Баранова Т.С

 

 

 

 

 

 

 

 

Иркутск 2012

 

Содержание

Введение 

1. Основные понятия линейного  программирования………………………………….4

     1.1 Постановка задачи………………………………………………………………..5

     1.2 Методы решения транспортной задачи ………………………………………..7

2. Построение оптимизационной транспортной  модели ……………………………12

3. Анализ решения задачи……………………………………………………………...13

Заключение 

Список используемой литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Линейное  программирование - наиболее разработанный  и широко применяемый раздел математического  программирования. Это объясняется  следующим:

- математические модели очень большого числа экономических задач линейны относительно искомых переменных;

- эти типы задач в настоящее время наиболее изучены;  

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

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

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

Цель:

- изучить  понятие линейного программирования;

- научиться  решать транспортные задачи с  помощью программы Excel

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Основные  понятия линейного программирования

 

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

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

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

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

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

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

•    Задачи линейного программирование, если они линейны;

•    Задачи целочисленного программирования, если ставится

условие целочисленности  переменных

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

Любую задачу линейного программирования  можно  свести  к задаче

линейного программирования в канонической форме. Для этого  в общем

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

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

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

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

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

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

переменными.

 

1. Постановка задачи

 

Под термином «транспортные задачи» понимается широкий круг задач

не только транспортного характера. Общим  для них является, как правило, распределение ресурсов, находящихся  у т производителей (поставщиков), по п потребителям этих ресурсов.

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

•    прикрепление потребителей ресурса к производителям;

•    привязка пунктов отправления к  пунктам назначения;

•    взаимная привязка грузопотоков прямого  и обратного направления;

•    отдельные      задачи       оптимальной      загрузки       промышленного оборудования;

•   оптимальное    распределение    объемов    выпуска    промышленной продукции  между заводами-изготовителями и  др.

Рассмотрим  экономико-математическую модель прикрепления пунктов отправления к пунктам  назначения. Имеются т пунктов отправления груза и

объёмы отправления  по каждому пункту ®\ •> @2'"®т Известна потребность в   грузах   ^р^2'"А,    каждому   из   пунктов   назначения.   Задана   матрица стоимостей доставки по каждому варианту С-^1 -\,т,] = \,п.  Необходимо

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

в   каждый  ]-й   пункт   назначения   (до   потребителя) транспортными  издержками.

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

отправляемых  грузов | 2-,^а> \ равен суммарному объему потребности в этих

1=1

грузах по пунктам назначения

Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой.

Когда в исходных условиях дана открытая задача, то её необходимо привести к закрытой форме. В случае если:

•    Потребности   по   пунктам   назначения   превышают  запасы   пунктов отправления, то вводится фиктивный  поставщик с недостающим объёмом  отправления;

•    Запасы поставщиков превышают потребности  потребителей, то   вводится   фиктивный   потребитель   с   необходимым   объёмом потребления.

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

•    Распределению подлежат однородные ресурсы;

•    Условия задачи описываются только уравнениями;

•    Все переменные выражаются в одинаковых единицах измерения;

•    Во всех уравнениях коэффициенты при  неизвестных равны единице;

•  Каждая неизвестная встречается только в двух уравнениях системы ограничений.

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

 

2. Методы решения транспортной задачи

 

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

 

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

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

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

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

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

Методы определения  оптимального плана. Алгоритм метода потенциалов. Наиболее распространенным методом  решения транспортных задач является метод потенциалов.

Решение задачи методом потенциалов включает следующие этапы:

1  Разработку начального плана (опорного решения);

2   Расчёт  потенциалов;

3   Проверку  плана на оптимальность;

4   Поиск  максимального звена неоптимальности  (если условие п, 3

не было достигнуто);

5   Составление  контура перераспределения ресурсов;

6   Определение       минимального       элемента       в       контуре перераспределения  и перераспределение ресурсов  по контуру;

7   Получение  нового плана.

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

•    Метод северо-западного угла;

•    Метод минимальной стоимости;

•    Метод двойного предпочтения и т.д.

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

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

Венгерский  метод

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