Расчет транспортной задачи на языке Borland Delphi 6.0.

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

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

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

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

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

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

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

Классификация идеальных моделей:

- вербальные (текстовые) модели;

- математические;

- информационные.

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

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

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

- дискрептивные (описательные) модели;

- оптимизационные;

- многокритериальные;

- игровые;

- имитационные модели.

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

1. Этапы компьютерного моделирования

Этапы и цели компьютерного моделирования:

- Определение целей моделирования:

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

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

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

- Разделение входных параметров по степени важности, влияния их изменений на входные параметры. Такой процесс называется ранжированием (разделением по рангам).

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

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

- Разработка алгоритма и составление программы для ЭВМ.

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

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

Этапы построения математической модели:

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

- введение обозначений;

- составление системы ограничений, которые должны удовлетворять введенные величины;

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

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

2. Теория по решению транспортных задач

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

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

При решении транспортных задач используют таблицы следующего вида.

Таблица 1 - Пример таблицы в общем виде, использующейся при решении задачи

Mi Nj	№1	№2	№3
M 1	с11 x11	с12 x12	с13 x13
M 2	с21 x21	с22 x22	с23 x23
M 3	с31 x31	с32 x32	с33 x33
M4	с41 x41	с42 x42	с43 x43

Mi - мощность i-го поставщика;

Nj - спрос j-го потребителя;

Cij - показатель затрат.

Транспортные задачи бывают двух видов: открытого и закрытого. К задачам первого вида относятся задачи, в которых Mi Nj, к задачам второго вида относятся задачи, в которых Mi Nj.

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

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

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

Находим первое допустимое базисное решение, при этом применяют способы:

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

- способ наименьших затрат.

При способе северо-западного угла заполнение таблицы начинается с клетки 11.

Таблица 2 - Пример заполнения таблицы при расчете методом северо-западного угла

Mi Nj	30	50	20
20	2 20	3	4
30	3 10	2 20	3
40	2	5 30	2 10
Mi Nj	30	50	20
10	4	1	6 10

x11=min (20,30)=20, при этом первый поставщик полностью разгружен, из таблицы выбывает первая строка;

x21=min (30,10)=10;

x22=min (20,50)=20;

x32=min (40,30)=30;

x33=min (10,20)=10;

x43=min (10,10)=10.

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

Для исследования первого допустимого базисного решения на оптимальность применяется метод потенциалов.

моделирование транспортный задача затраты

Таблица 3 - Пример заполнения таблицы при расчете методом потенциалов

Ui Vj	V 1	V 2	V 3
U 1	с11 x11	с12 x12	с13 x13
U 2	с21 x21	с22 x22	с23 x23
U 3	с31 x31	с32 x32	с33 x33
U4	с41 x41	с42 x42	с43 x43

Для того чтобы некоторый опорный план транспортной задачи был оптимальным, необходимо и достаточно, чтобы ему соответствовала система чисел V1, V2…Vn; U1, U2…Um таких, что Vj+Uicij для всех клеток и VjUi=cij для заполненных клеток. Числа Vj, Ui называют потенциалами.

Алгоритм метода потенциалов:

- Проверяем балансовое равенство Mi = Nj. Если оно выполняется, имеем закрытую транспортную задачу. В противном случае задача открытого типа, в которой Mi > Nj. Для получения закрытой транспортной задачи вводят фиктивного потребителя с нулевыми показателями затрат и спроса. Поставки фиктивному потребителю означают невыполненный груз. Если Mi < Nj, то для получения закрытой транспортной задачи нужно ввести фиктивного поставщика с нулевыми показателями затрат и мощности. Поставки фиктивного поставщика означают неудовлетворенный спрос.

- Находим первый опорный план и значение F(x1).

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

- Находим оценки пустых клеток. Оценка клетки ij: ij=Cij-Vi+Ui. Если для всех клеток ij0, то опорный план является оптимальным. В противном случае допустимое базисное решение не является оптимальным и можно найти новый опорный план.

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

- Находим x₀ - величину груза, передаваемого по циклу.

- После пересчёта по циклу получаем новый опорный план. Находим F(x2).

- Действия пунктов 3-7 повторяем до тех пор, пока не будет получен оптимальный план.

Замечания к алгоритму:

- если в оптимальном плане оценка пустой клетки равна нулю, то оптимальное решение не единственное;

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

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

В хозяйстве имеется три склада, где хранится 600 тонн (т) минеральных удобрений, в том числе на первом складе - 200 т, на втором - 150 т, на третьем - 250 т. На полях четырех с6евооборотов, удаленных на различные расстояния от этих складов, ведется посев озимых с одновременным внесением минеральных удобрений. Потребность в минеральных удобрениях для озимых первого севооборота составила 100 т, для второго - 150 т, для третьего - 150 т и для четвертого - 75 т. Общая потребность в минеральных удобрениях составила 475 т, то есть на 125 т меньше, чем имеется их в наличии. Минимизировать общую сумму транспортных затрат.

Транспортные издержки перевозки удобрений со складов на поля приведены в таблице 4.

Таблица 4 - Транспортные издержки перевозки удобрений со складов на поля

Склад	Севооборот
	1	2	3	4
1	4	2	3	1
2	3	6	2	5
3	6	3	4	2

4. Математическое решение ЗЛП

Пусть xij - количество минеральных удобрений, отправляемых со склада i на поля j-го севооборота.

Возможность поставки со складов:

x11+x12+x13+x14=200

x21+x22+x23+x24=150

x31+x32+x33+x34=250

Спрос на полях севооборотов:

x11+x21+x31=100

x12+x22+x32=150

x13+x23+x33=150

x14+x24+x34=75

Прямые ограничения: xij?0 (i = 1..3, j = 1..4)

Введем целевую функцию: F(x) = 4x₁₁+2x₁₂+3x₁₃+x₁₄+3x₂₁+ … +2x₃₄>min.

Решение транспортной задачи методом северо-западного угла

Для решения задачи необходимо заполнить таблицу 5.

Таблица 5 - Решение задачи методом северо-западного угла

	100	150	150	75	125
200	4 100	2 100	3	1	0
150	3	6 50	2 100	5	0
250	6	3	4 50	2 75	0 125

Заполнение данной таблицы начинается с клетки 11.

x11=min (200,100)=100, потребность поля первого севооборота полностью удовлетворена, из таблицы выбывает первый столбец;

x12=min (200-100,150)=100, первый склад полностью разгружен, из таблицы выбывает первая строка;

x22=min (150,150-100)=50, потребность поля второго севооборота полностью удовлетворена, из таблицы выбывает второй столбец;

x23=min (150-50,150)=100, второй склад полностью разгружен, из таблицы выбывает вторая строка;

x33=min (250,150-100)=50, потребность поля третьего севооборота полностью удовлетворена, из таблицы выбывает третья строка;

x34=min (250-50,75)=75, потребность поля четвертого севооборота полностью удовлетворена, из таблицы выбывает четвертый столбец.

Чтобы из таблицы выбыла третья строка, введем нулевую поставку.

Затраты на перевозку равны:

F(x) = 400+200+300+200+200+150 = 1450 у. е.

Данное решение является базисным, так как мы имеем шесть заполненных клеток. Исследуем первое допустимое базисное решение на оптимальность. Для этого применим метод наименьших затрат.

Решение транспортной задачи методом наименьших затрат

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

Таблица 6 - Расчет задачи методом наименьших затрат

	100	150	150	75
200	4	2 125	3	1 75
150	3	6	2 150	5
250	6 100	3 25	4	2

Заполнение данной таблицы начнем с клетки 14, так как показатель затрат в ней равен 1:

x14=min (200,75)=75, из таблицы выбывает столбец.

Затем переходим в клетку 12, так как показатель затрат в ней равен 2, получаем:

x12=min (200-75,150)=125, из таблицы выбывает первая строка.

Аналогичным образом рассчитываем все значения таблицы.

x23=min (150,150)=150, из таблицы выбывает и вторая строка, и третий столбец;

x32=min (250,150-125)=25, из таблицы выбывает второй столбец;

x31=min (250-25,100)=100, из таблицы выбывает первый столбец.

Таким образом, получаем, что затраты на перевозку равны:

F(x) = 2*125+75+2*150+25*3+100*6 = 1300 у. е.

Исследуем первое допустимое базисное решение на оптимальность. Для этого применим метод потенциалов.

Решение задачи методом потенциалов

Первое допустимое базисное решение необходимо исследовать на оптимальность, для этого необходимо построить систему потенциалов. Для заполненных клеток Cij = Vj - Ui, при этом один из потенциалов считается равным нулю.

Таблица 7 - Исследование первого допустимого базисного решения на оптимальность с помощью метода потенциалов

	V1 = 4	V2 = 2	V3 = -2	V4 = -4	V5 = -6
U1 = 0	4 100	2 100	3	1	0
U2 = -4	3	6 50	2 100	5	0
U3 = -6	6	3	4 50	2 75	0 125

Найдем оценки пустых клеток:

?13 = 3+2+0 = 5;

?14 = 1+4+0 = 5;

?15 = 0+6+0 = 6;

?21 = 3-4-4 = -5;

?24 = 5+4-4 = 5;

?25 = 0+6-4 = 2;

?31 = 6-4-6 = -4;

?32 = 3-2-6 = -5.

Первый опорный план не является оптимальным, так как ?31<0 и ?32<0.

Найдем новый опорный план. Для этого в клетку 21 нужно передать поставку, для чего строим цикл пересчета клетки 21:

После пересчета полученные данные сведем в таблицу 8.

Таблица 8 - Новое распределение поставок после пересчета по циклу

	V1 = 4	V2 = 2	V3 = 3	V4 = 1	V5 = -1
U1 = 0	4 50	2 150	3	1	0
U2 = 1	3 50	6	2 100	5	0
U3 = -1	6	3	4 50	2 75	0 125

Найдем оценки пустых клеток:

?13 = 3-3+0 = 0;

?14 = 1-1+0 = 0;

?15 = 0+1+0 = 1;

?22 = 6-2+1 = 5;

?24 = 5-1+1 = 5;

?25 = 0+1+1 = 2;

?31 = 6-4-1 = 1;

?32 = 3-2-1 = 0.

Для всех пустых клеток ?ij>0, следовательно, второй опорный план является оптимальным.

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

F(x) = 4*50+2*150+3*50+2*100+4*50+2*75 = 1200 у. е.

5. Алгоритм программы

6 Листинг программы

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

Заключение

В ходе курсовой работы была решена транспортная задача не только математическим путем, но и была написана программа для решения задач данного типа на языке Borland Delphi 6.0.

В моей курсовой работе передо мной была поставлена задача минимизировать затраты на перевозку минеральных удобрений со складов на поля севооборотов. Для этого задача была решена тремя методами: методом северо-западного угла, методом наименьших затрат и методом потенциалов. Самые большие затраты были получены при решении задачи методом северо-западного угла, они составили 1450 у. е. Далее я решила задачу методом наименьших затрат, что помогло уменьшить затраты до 1300 у. е. Наименьший же результат удалось получить при решении методом потенциалов, затраты при этом составили 1200 у. е. Это и есть оптимальное решение.

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

Литература

1 Б. Банди, Основы линейного программирования. - М: Радио и связь, 1989

2 Лекционный материал

Размещено на Allbest.ru