Минимизация стоимостей перевозок

Московский Государственный Колледж

Информационных Технологий

Курсовой проект

По предмету

” Языки программирования и разработка

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

На тему :

” Минимизация стоимостей перевозок “

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

студент группы П-407 Преподаватели

Чубаков А. С. Капустина Р. Н.

Токарев С. Б.

1998 г.

КР. 2203 81 – 21

ВВЕДЕНИЕ

Развитие современного общества характеризуется повышением технического

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

Решение экстремальных экономических задач можно разбить на три этапа :

1. Построение экономико – математической задачи.

2. Нахождение оптимального решения одним из математических методов.

3. Промышленное внедрение в народное хозяйство.

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

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

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

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

В трудах зарубежных ученых Робертса, Ланга и др.

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

КР. 2203 81 – 21

2. ЭКОНОМИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

Производственное предприятие имеет в своем составе три филиала которые производят однородную продукцию

Соответственно в количествах, равных 50 , 30 и 10 единиц. Эту продукцию получают четыре потребителя, расположенных в разных

Местах. Их потребности соответственны равны 30 , 30 , 10 и 20 единиц. Тарифы перевозов единицы продукции от каждого филиалов соответствующим потребителям задаются матрицей :

1 2 4 1

Сij = 2 3 1 5

3 2 4 4

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

КП. 2203 81 – 21

2.МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

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

Имеется:

m (i=1,2,…,m) – филиалы.

Ai – количество единиц продукции “i” филиала.

n (j=1,2,…,n) – потребители

Bj – потребности “j” потребителя

Cij – стоимость перевозки 1 условной единицы продукции

от “i” филиала к “j” потребителю

Ограничения:

1. Балансовое ограничение.

Предполагается, что сумма всех запасов (ai) равна сумме всех заявок (bj):

2. Ресурсное ограничение.

Суммарное количество груза, направленного из каждого пункта отправления во все пункты назначения должно быть равно запасу груза в данном пункте. Это даст m – условий равенств:

или

3. Плановое ограничение.

Суммарное количество груза, доставляемого в каждый пункт назначения изо всех пунктов отправления должно быть равно заявке (bj) поданной данным пунктом. Это даст нам n – условий равенств:

КП. 2203 81 – 21

или

4. Реальность плана перевозок.

Перевозки не могут быть отрицательными числами:

5. Требуется составить такой план перевозок, при котором все заявки были бы выполнены и при этом общая стоимость всех перевозок была бы минимальна, поэтому целевая функция или критерий эффективности:

КП. 2203 81 – 21

3.ВЫБОР МЕТОДА РЕАЛИЗАЦИИ ПРОДУКЦИИ.

ОБОСНОВАНИЕ ВЫБОРА МЕТОДА.

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

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

Которые в силу некоторых особенностей своей структуры допускают решение более

Простыми методами. К ним относится транспортная задача.

Распределительный метод решения транспортной задачи обладает одним

Недостатком :

Нужно отыскивать циклы для всех свободных клеток и находить их цены. От этой

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

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

Выделять циклы с отрицательной ценой и определять их цены.

В отличии от общего случая ОЗЛП с произвольными ограничениями и

Минимизированной функцией, решение транспортной задачи всегда существует.

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

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

Определение значений x­­­­i, j начинается с левой верхней клетки таблицы. Находим значения x1,1 из соотношения x11 = min{a1 ,b1 }.

Если ai < b1 то x11 =a1 , строка i=1 исключается из дальнейшего рассмотрения, а потребность первого потребителя b1 уменьшается на величину a1 .

Если a1 >b1 , то x11 =b1 , столбец j=1 исключается из дальнейшего рассмотрения, а наличие груза у первого поставщика a1 уменьшается на величину b1 .

Если a1 =b1 , то x11 =a1 =b1 , строка i=1 и столбец j=1 исключаются из дальнейшего рассмотрения.

Данный вариант приводит к вырождению исходного плана.

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

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

m + n -1.

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

Чтобы ее решить, необходимое сбалансировать. Достигается это следующим образом:

Когда еai >еbj это транспортная задача с избытком запасов.

Еxij <= ai (i=1,m)

КП. 2203 81 – 21

Еxij =bj (j=1,n)

Здесь вводим фиктивного потребителя Bф и приписываем ему заявку bф =еai – еbj. Вводим фиктивный сотолбец, т. е Ciф =0 (i =1,m). Все стоимости будут равны нулю, это значит, что грузы ciф останутся невостребованными, т. е введением фиктивного потребителя, мы свели транспортную задачу с неправильным балансом к задаче с правильным балансом.

Если сумма подданных заявок превышает наличные запасы

Еbj >еa­i, то такая задача называется – транспортная задача с избытком запаса. Эту задачу можно свести к обычной задаче с правильным балансом, если ввести фиктивный пункт отправления Aф, приписав ему фиктивный запас aф =еbj – еai. Добавляем фиктивную строку, где Cфi = 0 ( j=1,n).

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

R=еai : еbj и каждый запас bj умножаем на этот коэффициент. Таким образом задача сведена к транспортной задаче с правильным балансом.

Построенный выше исходный план можно довести до оптимального с помощью метода потенциалов.

Каждому поставщику Ai поставим в соответствии некоторые числа ai, называемые потенциалом, а каждому потребителю Bj – число bj.

Для каждой независимой клетки, т. е для каждой независимой переменной рассчитываются так называемые косвенные... тарифы ( Cўij ) по формуле

Cўij = ai + bj. А для заполненных клеток, т. е базисных переменных Cўij =Cij.

Проверяем полученный план на оптимальность. Если для каждой независимой клетки выполняется условие Cўij – Cij <=0 , то такой план является оптимальным. Если хотя бы в одной свободной клетке Cўij > Cij, то следует приступить к улучшению плана.

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

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

В каждой клетки цикла, начиная со свободной, проставляются поочередно знаки

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

КП. 2203 81 – 21

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

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

F = ее Cij – cij min.

Метод потенциалов обеспечивает монотонное убывание значений целевой функции и позволяет за конечное число шагов найти его минимум.

КР. 2203 81 – 21

5.КРАТКАЯ ХАРАКТЕРИСТИКА ЭВМ И ЕГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

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

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

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

Программы. работающие на компьютеры можно разделить на три категории :

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

Картинок, обработку информационных массивов и т. д.

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

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

КР. 2203 81 – 21

6.ОБОСНОВАНИЕ ВЫБОРА ЯЗЫКА

В 1992 году фирма Borland International выпустила два пакета программирования, основанные на использовании языка Паскаль – Borland Pascal 7.0 и Turbo Pascal 7.0. Система программирования Turbo Pascal, разработанная американской корпорацией Borland

Остается одной из самых популярных систем программирования в мире. Этому способствует, с одной стороны, простота лежащего в ее основе языка программирования Паскаль, а с другой – труд и талант сотрудников Borland во главе с идеологом и создателем Turbo Pascal Андерсом Хейлсбергом, приложившим немало усилий к ее совершенствованию. Придуманный швейцарским ученым Никласом Виртом как средство для обучения студентов программированию, язык Паскаль стараниями А. Хейлсберга превратилась в мощною современною профессиональную систему программирования, которой по плечу любые задачи – от создания простых программ, предназначенных для решения несложных вычислительных задач, до разработки сложнейших реляционных систем управления базами данных. Появление Windows и инструментальных средств Borland Pascal with Object и Delphi для разработки программ в среде Windows лишний раз показало, какие поистине не исчерпывающие возможности таит он в себе : и Borland Pascal, и используемый в Delphi язык Object Pascal основываются на Турбо Паскале и развивают его идеи.

Пакет Turbo Pascal включает в себя как язык программирования – одно из расширений языка Паскаль для ЭВМ типа IBM, так и среду, предназначенную для написания, отладки и запуска программ.

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

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

КР. 2203 81 – 21

7.РЕШЕНИЕ ЗАДАЧИ ТЕСТА ДЛЯ НАПИСАНИЯ И ОТЛАДКИ ПРОГРРАММЫ.

B1

B2

B3

B4

a­i

Ai

A1

1 1

30

2 2

20

0 4

4 1

50

0

A2

2 2

3 3

10

1 1

10

5 5

10

30

1

A3

1 3

2 2

0 4

4 4

10

10

0

Заявки

bj

30

30

10

20

90

Bj

1

2

0

4

1,2 1,4

10

2,2 2,4

B1

B2

B3

B4

Ai

Ai

A1

1 1

30

2 2

10

0 4

1 1

10

50

0

A2

2 2

3 3

20

1 1

10

2 5

30

1

A3

4 3

5 2

3 4

4 4

10

10

3

Bj

30

30

10

20

90

Bj

1

2

0

1

1,1 1,4

10

3,1 3,4

КР. 2203 81 – 21

B1

B2

B3

B4

ai

Ai

A1

1 1

20

2 2

10

0 4

1 1

20

50

0

A2

2 2

3 3

20

1 1

10

2 5

30

1

A3

3 3

10

4 2

2 4

3 4

10

2

bj

30

30

10

20

90

B­j

1

2

0

1

1,1 1,2

10

3,1 3,2

B1

B2

B3

B4

ai

Ai

A1

1 1

30

-1 2

-3 4

1 1

20

50

0

A2

5 2

3 3

20

1 1

10

5 5

30

4

A3

4 3

2 2

10

0 4

4 4

E

10+E

3

Bj

30

30

10

20+E

90+E

Bj

1

-1

-3

1

1,1 1,2

10

2,1 2,2

КР. 2203 81 – 21

B1

B2

B3

B4

ai

Ai

A1

1 1

10

2 2

20

0 4

1 1

20

50

0

A2

2 2

20

3 3

1 1

10

2 5

30

1

A3

1 3

2 2

10

0 4

1 4

10

0

Bj

30

30

10

20

90

Bj

1

2

0

1

F­min =1-10 +2-20 +2-10 +1-10 +2-20 +20*1 = 140

Найден оптимальный план перевозок, равный 140.

КР. 2203 81 – 21

8.АНАЛИЗ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ

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

Cўij -Cij <=0

Так же суммарная стоимость перевозок груза с каждой последующей итерацией уменьшалась и оказалась равной 140 рублям.

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

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

Вектор полученных результатов:

10 20 0 20

C= 20 0 10 0

0 10 0 0

КП. 2203 81 – 21

ЗАКЛЮЧЕНИЕ

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

Эта задача сводится к транспортной задаче.

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


Зараз ви читаєте: Минимизация стоимостей перевозок