Транспортная задача перевозки неоднородного груза

КОМПЛЕКСНАЯ КУРСОВАЯ РАБОТА

БАРНАУЛ 2012

Содержание

Содержание.. 2

Введение.. 3

Сущность математического метода.. 5

1     Характеристика метода перевозки  неоднородного груза. 5

2     Аналитическое решение задачи  перевозки неоднородного груза  11

Анализ и уточнение требований к программе.. 15

1     Анализ процесса обработки информации и выбор структур данных для ее хранения. 15

4     Разработка основных алгоритмов решения задачи. 17

Проектирование интерфейса пользователя.. 19

1     Граф состояния интерфейса. 19

2     Формы ввода-вывода информации. 20

Контрольный пример. 22

Заключение.. 26

Список литературы... 27

Приложение A.. 28

Введение

Тема курсовой работы – транспортная задача перевозки неоднородного груза. 

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

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

Основы линейного программирования были заложены советским математиком Л.В. Канторовичем в конце 30-х годов.

В 1949 г. Л.В.Кантоновичем и М,К. Гавуриным предложен новый точный метод для решения транспортной задачи – метод потенциалов. В последующие годы вклад в развитие теории линейного программирования внесли ученые многих стран мира.

Цель данной работы заключается в создании программного продукта для решения задач по теме: «Транспортная задача перевозки неоднородного груза».

Задачи курсовой работы:

-  изучить теоретический материал по данной теме;

-  изучить методы решения задач;

-  создать алгоритм для решения данной задачи;

-  создать программу для решения задач данного класса.

Программа будет разработана в среде Delphi.

Системные требования: Win 98/SE/2000/ME/XP, 256 RAM.

Сущность математического метода

1                  Характеристика метода перевозки  неоднородного груза

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

Пусть, например, имеются два поставщика – А₁и А₂ и два потребителя В₁и В₂.

У каждого поставщика имеется груз двух сортов (например, бурый уголь и антрацит, цемент марок 500 и 600 и т.д.). Обозначим ресурсы 1-го поставщика по каждому из сортов груза через а¹₁ и a¹¹₁ и аналогично, 2-го поставщика – через а¹₂ и a¹¹₂.

В дальнейшее мы будем рассматривать не два, а как бы четыре поставщика, ресурсы которого соответственно равны а¹₁,  а¹¹₁, а¹₂  и  а¹¹₂. Теперь перейдем к анализу потребностей каждого потребителя. Очевидно, в условиях данной задачи эти потребности у каждого потребителя могут быть трех видов.

1  Потребности только на первый сорт груза. Обозначим их соответственно для 1-го потребителя через b¹₁и для второго через b¹₂.

2  Потребности  только на второй сорт груза (соответственно b¹¹₁и  b¹¹₂).

3  Взаимозаменяемые потребности на любой из сортов груза (соответственно b¹¹¹₁и b¹¹¹₂).

Будем полагать, что b¹¹¹₁и b¹¹¹₂означают потребности 1-го и 2-го потребителя, выраженные в единицах первого сорта груза.

Вместо каждого из двух потребителей В₁ и В₂ будем в дальнейшем рассматривать три потребителя с потребностями b¹, b¹¹ и  b¹¹¹.

Занесем все перечисленные исходные данные и, кроме того, коэффициенты затрат C_ik на перевозку единицы груза в таблицу №1.

Оформление таблицы в методичке

Таблица 1

Будем полагать, что коэффициенты затрат от сорта перевозимого груза, а определяются только тем, «откуда» и «куда» он перевозится_.

Пусть p - единицы груза первого сорта могут быть замены при удовлетворении 3-й категории потребностей q – единиц второго сорта. Тогда отношение  назовем коэффициентом взаимозаменяемости. Он показывает, сколько единиц груза второго сора могут заменить