close

Вход

Забыли?

вход по аккаунту

?

Курсовая трансп БГТУ ГОТОВАЯ

код для вставкиСкачать

Содержание
Введение3
1. Постановка задачи4
1.1 Формулировка задания4
1.2 Математическая модель задачи5
2. Выбор метода решения7
3. Численное решение8
3.1 Метод северо-западного угла8
3.2 Метод минимального элемента
3.3 Метод потенциалов
3.3 Метод апроксимации Фогеля
4. Программная реализация
4.1 Описание процедур и функций
4.1 Текст программы
Заключение28
Список используемой литературы...............................................29
Введение
Одной из типичных задач линейного программирования является транспортная задача, задача об экономном плане перевозок однородного груза от поставщика к потребителю.
Задачи линейного программирования широко применяются для решения различных экономических задач. Они используются для производственных расчетов на множестве предприятий. С развитием компьютерной техники линейное программирование стало просто незаменимым в экономике. Решая задачи линейного программирования можно спроектировать работу не только отдельно взятого цеха, но и всего предприятия или даже отрасли. Это позволяет сэкономить множество средств и ресурсов, а так же распределить экономические ресурсы таким образом, что доход от производства станет максимальным.
С помощью линейного программирования можно описать довольно широкий круг задач как экономических, так и технических. Поэтому данная задача может иметь не только теоретическое, но также и прикладное значение в экономической сфере. 1. Постановка задачи
1.1 Формулировка задания
В трех хранилищах горючего ежедневно хранится 175, 125, 140 т бензина. Этот бензин ежедневно получают четыре заправочные станции в количествах, равных соответственно 180, 110, 60 и 40 т. Тарифы перевозок 1т. бензина с хранилищ к заправочным станциям задаются матрицей.
;
Необходимо составить такой план перевозок бензина, при котором общая стоимость перевозок является минимальной.
1.2 Математическая модель задачи
Для оформления математической модели задачи требуется воспользоваться данными таблицы, которая называется матрицей планирования.
Матрица планированияПотребителиB1B2B3BnПоставщики bj aib1b2b3bnA1a1x11
c11x12
c12x13
c13x1n
c1nA2a2x21
c21x22
c22x23
c23x2n
c2nAmamxm1
cm1xm2
cm2xm3
cm3xmn
cmn Таблица 1
Так как i-ому поставщику к j-ому потребителю запланировано к перевозке xij единиц груза, а стоимость перевозки одной единицы груза составляет cij денежных единиц, то стоимость перевозки составит xij cij, а стоимость всего плана выразится двойной суммой:
Система ограничений выводится из следующих условий задачи:
* все грузы должны быть вывезены, т.е.
* все потребности должны быть удовлетворены, т.е.
Таким образом математическая модель транспортной задачи имеет следующий вид:
Найти наименьшее значение линейной функции
При ограничениях
2. Выбор метода решения
Так как транспортная задача является специальной задачей линейного программирования, то для ее решения существует ряд специальных методов. А именно: метод северо-западного угла, метод минимальной стоимости, метод аппроксимации Фогеля, метод потенциалов и метод дифференциальных рент.
В данной работе рассмотрено решение транспортной задачи тремя методами:
* методом северо-западного угла;
* методом минимальной стоимости;
* методом потенциалов.
3. Численное решение
3.1 Метод северо-западного угла
Обозначим номера хранилищ через i , а номера заправочных станций через j. Количество бензина привезенного из хранилища i на заправочную станцию j xij.
Тогда должны выполнятся следующие условия:
Минимизируемся функция затрат имеет вид:
Получили так называемую открытую задачу, если бы было равенство, то задача была бы закрытая или сбалансированная. В нашей ситуации, когда запасы превышают на 50 т необходимо ввести фиктивного потребителя (заправочная станция), потребность которого будет равна этому излишку.
Кроме того необходимо учесть что количество перевозимого бензина не может быть отрицательным:
Поиск оптимальных затрат
Построим первоначальный опорный план методом "северо-западного угла".
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5А19
1757
5
3
0
175А21
52
1104
106
0
125А38
10
12
501
400
50140Потребности180110604050440
Принцип заполнения таблицы состоит в том, что, начиная с крайней левой верхней ячейки (принцип северо-западного угла), количество грузов вписывается в таблицу так, чтобы потребности полностью удовлетворялись или груз полностью вывозился.
Построим систему потенциалов. - потенциалы, соответствующие поставщикам, - потенциалы, соответствующие потребителям.
Полагаем V1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V1 = 9 U1 = 9
U2 + V1 = 1 U2 = 1
U2 + V2 = 2 V2 = 1
U2 + V3 = 4 V3 = 3
U3 + V3 = 12 U3 = 9 V4 = -8
U3 + V5 = 0 V5 = -9
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=0V2=1V3=3V4=-8V5=-9А1U1=99
1757
5
3
0
175А2U2=11
52
1104
106
0
125А3U3=98
10
12
501
400
50140Потребности180110604050440
Проверим критерий оптимальности : Ui + Vj dij для свободных клеток.
U1 + V2 = 10>7 на 3
U1 + V3 = 12>5 на 7
U1 + V4 = 1<3
U1 + V5 = 0=0
U2 + V4 = -7<6
U2 + V5 = -8<0
U3 + V1 = 9>8 на 1
U3 + V2 = 10=10
f = 2480
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это - ячейка (1 , 3)
Перебросим в ячейку (1 , 3) 10 единиц груза из ячейки (2 , 3).
Чтобы компенсировать недостаток во второй строке, перебросим те же 10 единиц груза из ячейки (1 , 1) в ячейку (2 , 1).
Таким образом, получаем следующего вида таблицу.
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=9V2=10V3=5V4=-6V5=-7А1U1=09
165 7
5
103
0
175А2U2=-81
152
1104
6
0125А3U3=78
10
12
501
400
50140Потребности180110604050440
Получаем новую таблицу, для которой повторяем расчет потенциалов:
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V1 = 9 V1 = 9
U1 + V3 = 5 V3 = 5
U2 + V1 = 1 U2 = -8
U2 + V2 = 2 V2 = 10
U3 + V3 = 12 U3 = 7
U3 + V4 = 1 V4 = -6
U3 + V5 = 0 V5 = -7
Проверим критерий оптимальности : Ui + Vj dij для свободных клеток.
U1 + V2 = 10>7 на 3
U1 + V4 = -6 < 3
U1 + V5 = -7<0
U2 + V3 = -3<4
U2 + V4 = -14<6
U2 + V5 = -15<0
U3 + V1 = 16>8 на 8
U3 + V2 = 17>10 на 7
f = 2410
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это - ячейка (3 , 1)
Перебросим в ячейку (3 , 1) 50 единиц груза из ячейки (3 , 3).
Чтобы компенсировать недостаток в первой строке, перебросим те же 50 единиц груза из ячейки (1 , 1) в ячейку (1 , 3).
Таким образом, получаем следующего вида таблицу.
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=9V2=10V3=5V4=2V5=1А1U1=09
1157
5
603
0
175А2U2=-81
152
1104
6
0
125А3U3=-18
5010
12
1
400
50140Потребности180110604050440
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V1 = 9 V1 = 9
U1 + V3 = 5 V3 = 5
U2 + V1 = 1 U2 = -8
U2 + V2 = 2 V2 = 10
U3 + V1 = 8 U3 = -1
U3 + V4 = 1 V4 = 2
U3 + V5 = 0 V5 = 1
Проверим критерий оптимальности : Ui + Vj dij для свободных клеток.
U1 + V2 = 10>7 на 3
U1 + V4 = 2 < 3
U1 + V5 = 1>0 на 1
U2 + V3 = -3<4
U2 + V4 = -6<6
U2 + V5 = -7<0
U3 + V2 = 9<10
U3 + V3 = 4<12
f = 2010
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это - ячейка (1 , 2)
Перебросим в ячейку (1 , 2) 110 единиц груза из ячейки (2 , 2).
Чтобы компенсировать недостаток во второй строке, перебросим те же 110 единиц груза из ячейки (1 , 1) в ячейку (2 , 1).
Таким образом, получаем следующего вида таблицу.
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=9V2=7V3=5V4=2V5=1А1U1=09
57
1105
603
0
175А2U2=-81
1252
4
6
0
125А3U3=-18
5010
12
1
400
50140Потребности180110604050440
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V1 = 9 V1 = 9
U1 + V2 = 7 V2 = 7
U1 + V3 = 5 V3 = 5
U2 + V1 = 1 U2 = -8
U3 + V1 = 8 U3 = -1
U3 + V4 = 1 V4 = 2
U3 + V5 = 0 V5 = 1
Проверим критерий оптимальности : Ui + Vj dij для свободных клеток.
U1 + V4 = 2<3
U1 + V5 = 1>0
U2 + V2 = -1<2
U2 + V3 = -3<4
U2 + V4 =-6<6
U2 + V5 =-7<0
U3 + V2 =6<10
U3 + V3 =4<12
f = 1680
Из тех условий, где критерий не выполняется, выбираем то условие, где разница максимальна. Это - ячейка (1 , 5)
Перебросим в ячейку (1 , 5) 5 единиц груза из ячейки (1 , 1).
Чтобы компенсировать недостаток в первом столбце, перебросим те же 5 единиц груза из ячейки (3 , 5) в ячейку (3 , 1).
Таким образом, получаем следующего вида таблицу.
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=8V2=7V3=5V4=1V5=0А1U1=09
7
1105
603
0
5175А2U2=-71
1252
4
6
0
125А3U3=08
5510
12
1
400
45140Потребности180110604050440
Полагаем U1=0, а далее Ui + Vj = dij для занятых клеток таблицы.
U1 + V2 = 7 V2 = 7
U1 + V3 = 5 V2 = 5
U1 + V5 = 0 V5 = 0
U2 + V1 = 1 U2 = -7
U3 + V1 = 8 U3 = 0
U3 + V4 = 1 V4 = 1
U3 + V5 = 0 V5 = 0
Проверим критерий оптимальности : Ui + Vj dij для свободных клеток.
U1 + V1 = 8<9
U1 + V4 = 1<3
U2 + V2 = 0<2
U2 + V3 = -2<4
U2 + V4 =-6<6
U2 + V5 =-7<0
U3 + V2 =7<10
U3 + V3 =5<12
Критерий выполнен, значит, полученное решение оптимально.
Найдем минимальную стоимость перевозок.
3.2 Метод минимального элемента
Опорный план будет иметь следующий вид :
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=5V2=7V3=5V4=-2V5=0А1U1=09
7
1105
603
0
5175А2U2=-41
1252
4
6
0
125А3U3=38
5510
12
1
400
45140Потребности180110604050440 f = 1810
Аналогичным образом, получаем таблицу для оптимального решения.
Пункты
поставкиПункты потребленияЗапасыВ1В2В3В4В5V1=8V2=7V3=5V4=1V5=0А1U1=09
7
1105
603
0
5175А2U2=-71
1252
4
6
0
125А3U3=08
5510
12
1
400
45140Потребности180110604050440 f = 1675
3.3 Метод потенциалов
Метод потенциалов был применен в процессе расчетов в пункте 3.1, когда производился расчет по методу северо-западного угла и находился оптимальный план перевозок.
3.4 Метод апроксимации Фогеля
Найдем начальное решение методом Фогеля. Если начальное решение окажется оптимальным, то задача решена. Если начальное решение окажется неоптимальным, используя метод потенциалов, будем последовательно получать решение за решением, причем каждое следующее, как минимум, не хуже предыдущего. И так, до тех пор, пока не получим оптимальное решение.
Для разрешимости транспортной задачи необходимо, чтобы суммарные запасы продукции у поставщиков равнялись суммарной потребности потребителей. Проверим это условие.
В нашем случае, запасы поставщиков - 440 единиц продукции больше, чем потребность потребителей - 390 на 50 единиц. Введем в рассмотрение фиктивного потребителя B5, с потребностью в продукции равной 50. Стоимость доставки единицы продукции от всех поставщиков к данному потребителю примем равной нулю.
Маршруты доставки продукции от поставщиков к фиктивному потребителю B5 мы будем рассматривать в последнюю очередь. Не факт, но, скорее всего, это позволит получить более рентабельное начальное решение.
1) В каждой строке, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами. 2) В каждой столбце, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 1. В данном столбце выберем ячейку A2B1, как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика A2 к потребителю B1, как минимум, на 7 ден.ед. меньше чем от остальных поставщиков к потребителю B1.
Запасы поставщика A2 составляют 125 единиц продукции. Потребность потребителя B1 составляет 180 единиц продукции. От поставщика A2 к потребителю B1 будем доставлять min = { 125 , 180 } = 125 единиц продукции.
Разместим в ячейку A2B1 значение равное 125 Мы полностью израсходoвали запасы поставщика A2. Вычеркиваем строку 2 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
3) В каждой строке, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
4) В каждой столбце, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
Опять из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 3. В данном столбце выберем ячейку A1B3, как обладающую наименьшим тарифом.
Объясняем почему?
Стоимость доставки единицы продукции от поставщика A1 к потребителю B3, как минимум, на 7 ден.ед. меньше чем от остальных поставщиков к потребителю B3 . Запасы поставщика A1 составляют 175 единиц продукции. Потребность потребителя B3 составляет 60 единиц продукции. От поставщика A1 к потребителю B3 будем доставлять min = { 175 , 60 } = 60 единиц продукции.
Разместим в ячейку A1B3 значение равное 60 Мы полностью удовлетворили потребность потребителя B3. Вычеркиваем столбец 3 таблицы, т.е исключаем его из дальнейшего рассмотрения.
5) В каждой строке, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
В каждой столбце, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает строка 3. В данной строке выберем ячейку A3B4, как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика A3 к потребителю B4, как минимум, на 7 ден.ед. меньше чем к другим потребителям .
Запасы поставщика A3 составляют 140 единиц продукции. Потребность потребителя B4 составляет 40 единиц продукции. От поставщика A3 к потребителю B4 будем доставлять min = { 140 , 40 } = 40 единиц продукции.
Разместим в ячейку A3B4 значение равное 40 Мы полностью удовлетворили потребность потребителя B4. Вычеркиваем столбец 4 таблицы, т.е исключаем его из дальнейшего рассмотрения.
6) В каждой строке, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
В каждой столбце, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 2. В данном столбце выберем ячейку A1B2, как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика A1 к потребителю B2, как минимум, на 3 ден.ед. меньше чем от остальных поставщиков к потребителю B2 .
Запасы поставщика A1 составляют 115 единиц продукции. Потребность потребителя B2 составляет 110 единиц продукции. От поставщика A1 к потребителю B2 будем доставлять min = { 115 , 110 } = 110 единиц продукции.
Разместим в ячейку A1B2 значение равное 110 Мы полностью удовлетворили потребность потребителя B2. Вычеркиваем столбец 2 таблицы, т.е исключаем его из дальнейшего рассмотрения.
7) В каждой строке, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
В каждой столбце, найдем разность между двумя ячейками (доступными для выбора) с наименьшими тарифами.
Из полученных разностей выберем наибольшую.
Наибольшей разностью обладает столбец 1. В данном столбце выберем ячейку A3B1, как обладающую наименьшим тарифом.
Почему?
Стоимость доставки единицы продукции от поставщика A3 к потребителю B1, как минимум, на 1 ден.ед. меньше чем от остальных поставщиков к потребителю B1 .
Запасы поставщика A3 составляют 100 единиц продукции. Потребность потребителя B1 составляет 55 единиц продукции. От поставщика A3 к потребителю B1 будем доставлять min = { 100 , 55 } = 55 единиц продукции.
Разместим в ячейку A3B1 значение равное 55 Мы полностью удовлетворили потребность потребителя B1. Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.
8) Запасы поставщика A1 составляют 5 единиц продукции. Потребность потребителя B5 составляет 50 единиц продукции. От поставщика A1 к потребителю B5 будем доставлять min = { 5 , 50 } = 5 единиц продукции.
Разместим в ячейку A1B5 значение равное 5 Мы полностью израсходoвали запасы поставщика A1. Вычеркиваем строку 1 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
9) Запасы поставщика A3 составляют 45 единиц продукции. Потребность потребителя B5 составляет 45 единиц продукции. От поставщика A3 к потребителю B5 будем доставлять 45 единиц продукции.
Разместим в ячейку A3B5 значение равное 45 Мы полностью израсходoвали запасы поставщика A3. Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.
Заполненные нами ячейки будем называть базисными, остальные - свободными.
Для решения задачи методом потенциалов, количество базисных ячеек (задействованных маршрутов) должно равняться m + n - 1, где m - количество строк в таблице, n - количество столбцов в таблице.
Количество базисных ячеек (задействованных маршрутов) равно 7, что и требовалось.
Мы нашли начальное решение, т.е израсходовали все запасы поставщиков и удовлетворили все потребности потребителей. S0 = 7 * 110 + 5 * 60 + 0 * 5 + 1 * 125 + 8 * 55 + 1 * 40 + 0 * 45 = 1675 ден. ед.
Общие затраты на доставку всей продукции, для начального решения , составляют 1675 ден. ед. .
Дальнейшие наши действия будут состоять из шагов, каждый из которых состоит в следующем: Находим потенциалы поставщиков и потребителей для имеющегося решения.
Находим оценки свободных ячеек. Если все оценки окажутся неотрицательными - задача решена. Выбираем свободную ячейку (с отрицательной оценкой), выбор которой, позволяет максимально снизить общую стоимость доставки всей продукции на данном шаге решения.
Находим новое решение, как минимум, не хуже предыдущего.
Вычисляем общую стоимость доставки всей продукции для нового решения.
Шаг 1
ПРОИЗВЕДЕМ ОЦЕНКУ ПОЛУЧЕННОГО РЕШЕНИЯ.
Каждому поставщику Ai ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.
Каждому потребителю Bj ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.
Для базисной ячеки (задействованного маршрута), сумма потенциалов поставщика и потребителя должна быть равна тарифу данного маршрута. (ui + vj = cij, где cij - тариф клетки AiBj) Посколько, число базисных клеток - 7, а общее количество потенциалов равно 8, то для однозначного определения потенциалов, значение одного из них можно выбрать произвольно.
Примем u3 = 0.
v1 + u3 = c31 v1 + u3 = 8v1 = 8 - 0 = 8
v4 + u3 = c34 v4 + u3 = 1v4 = 1 - 0 = 1
v5 + u3 = c35 v5 + u3 = 0v5 = 0 - 0 = 0
v5 + u1 = c15 v5 + u1 = 0u1 = 0 - 0 = 0
v1 + u2 = c21 v1 + u2 = 1u2 = 1 - 8 = -7
v2 + u1 = c12 v2 + u1 = 7v2 = 7 - 0 = 7
v3 + u1 = c13 v3 + u1 = 5v3 = 5 - 0 = 5
Найдем оценки свободных ячеек следующим образом (в таблице они располагаются в нижнем левом углу ячейки):
= c11 - ( u1 + v1 ) = 9 - ( 0 + 8 ) = 1
∆14= c14 - ( u1 + v4 ) = 3 - ( 0 + 1 ) = 2
∆22 = c22 - ( u2 + v2 ) = 2 - ( -7 + 7 ) = 2
∆23 = c23 - ( u2 + v3 ) = 4 - ( -7 + 5 ) = 6
∆24 = c24 - ( u2 + v4 ) = 6 - ( -7 + 1 ) = 12
∆25 = c25 - ( u2 + v5 ) = 0 - ( -7 + 0 ) = 7
∆32 = c32 - ( u3 + v2 ) = 10 - ( 0 + 7 ) = 3
∆33 = c33 - ( u3 + v3 ) = 12 - ( 0 + 5 ) = 7
Все оценки свободных ячеек положительные, следовательно, найдено оптимальное решение.
Ответ: X опт = 0 110 60 0 5 125 0 0 0 0 55 0 0 40 45 Smin = 7 * 110 + 5 * 60 + 0 * 5 + 1 * 125 + 8 * 55 + 1 * 40 + 0 * 45 = 1675
Общие затраты на доставку всей продукции, для оптимального решения, составляют 1675 ден. ед.
4. Программная реализация
4.1 Описание процедур и функций
Процедура TForm1.CalcNorthWest( data: TData; var plan: TData) выполняет расчет опорного плана методом северо-западного угла. Результатом выполнения данной процедуры является массив, представляющий опорный план.
Процедура TForm1.Dump(data: TData; fl: integer) отвечает за вывод в компонент Memo1 исходных данных, планов, матриц оценок клеток.
Функция TForm1.CalcSum(data, plan: TData): integer вычисляет решение транспортной задачи, т.е. общую стоимость по уже рассчитанному плану.
Процедура TForm1.CalcMinEl( data: TData; var plan: TData ) выполняет расчет опорного плана методом наименьшей стоимости. Результатом выполнения данной процедуры является массив, представляющий опорный план. Процедура TEqSolve.Solve выполняет решение системы уравнений, содержащей потенциалы строк и столбцов.
Процедура TForm1.CalcPotential(data: TData; var plan, x: TData) формирует систему уравнений, содержащую потенциалы строк и столбцов, после чего вызывает процедуру TEqSolve.Solve и выводит полученные значения в компонент Memo1.
4.1 Текст программы
unit p1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, Math, ComCtrls, ExtCtrls;
type
TData = class
public
Width, Height: integer;
Arr: array [0..99, 0..99] of integer;
Left, Top: array[0..99] of integer;
constructor Create;
procedure Reset;
procedure Assign( data: TData );
procedure AssignLT( data: TData );
function NoNulls: integer;
function Min: integer;
end;
TEquation = record
p1, p2: integer;
sum: integer;
solved: boolean;
end;
TVar = record
v: integer;
solved: boolean;
end;
TEqSolve = class
public
Eq: array [0..100] of TEquation;
fV: array [0..100] of TVar;
fEqCount, fVarCount, fH: integer;
function GetU( index: integer ): TVar;
function GetV( index: integer ): TVar;
procedure AddEq( p1, p2, s: integer );
constructor Create( h, v_c: integer );
procedure Solve;
property U[index: integer]: TVar read GetU;
property V[index: integer]: TVar read GetV;
end; {}
TForm1 = class(TForm)
PageControl1: TPageControl;
TabSheet1: TTabSheet;
Button3: TButton;
StringGrid1: TStringGrid;
Button2: TButton;
StringGrid2: TStringGrid;
StringGrid3: TStringGrid;
StringGrid4: TStringGrid;
Label1: TLabel;
Label2: TLabel;
Label3: TLabel;
Label4: TLabel;
Label5: TLabel;
Label6: TLabel;
TabSheet2: TTabSheet;
Memo1: TMemo;
Button1: TButton;
Button4: TButton;
Label7: TLabel;
Label8: TLabel;
Label9: TLabel;
procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);
procedure FormCreate(Sender: TObject);
procedure Button2Click(Sender: TObject);
procedure Button3Click(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button4Click(Sender: TObject);
private
{ Private declarations }
public
fData: TData;
{ Public declarations }
function Check( data: TData ): boolean;
procedure CalcNorthWest( data: TData; var plan: TData );
procedure CalcMinEl( data: TData; var plan: TData );
procedure CalcPotential( data: TData; var plan, x: TData );
procedure Dump( data: TData; fl: integer );
function CalcSum( data, plan: TData ): integer;
procedure ShiftPlan( var data, plan, potential: TData );
end;
var
Form1: TForm1;
implementation
{$R *.dfm}
procedure TForm1.StringGrid1KeyPress(Sender: TObject; var Key: Char);
begin
if (StringGrid1.Col = 1) and (StringGrid1.Row = 1) then
begin
Key := #0;
exit;
end;
if (Key < '0') or (Key > '9') then
Key := #0;
end;
procedure TForm1.FormCreate(Sender: TObject);
begin
memo1.Clear;
StringGrid1.ColCount := 7;
StringGrid1.RowCount := 6;
StringGrid1.Cells[1,0] := 'Потребители';
StringGrid1.Cells[0,1] := 'Поставщики';
StringGrid1.Cells[1,1] := 'груз \ спрос';
StringGrid1.Cells[2,0] := 'B1';
StringGrid1.Cells[3,0] := 'B2';
StringGrid1.Cells[4,0] := 'B3';
StringGrid1.Cells[5,0] := 'B4';
StringGrid1.Cells[6,0] := 'B5';
StringGrid1.Cells[0,2] := 'A1';
StringGrid1.Cells[0,3] := 'A2';
StringGrid1.Cells[0,4] := 'A3';
StringGrid1.Cells[0,5] := 'A4';
end;
procedure TForm1.Button2Click(Sender: TObject); // кнопка "вычислить"
function GetInt( x, y: integer ): integer;
begin
Result := StrToInt( StringGrid1.Cells[ x, y ] );
end;
var
index, index2, s, old_s: integer;
data, plan, potential: TData;
begin
Label7.Caption:='Решение:';
Label8.Caption:='Решение:';
Label9.Caption:='Решение:';
Memo1.Lines.Clear;
// Прочитать данные из грида
data := TData.Create;
data.Width := StringGrid1.ColCount-2;
data.Height := StringGrid1.RowCount-2;
for index := 0 to data.Height-1 do
for index2 := 0 to data.Width-1 do
data.Arr[index2,index] := GetInt( index2+2, index+2 );
for index := 0 to data.Width-1 do
data.Top[index] := GetInt( index+2, 1 );
for index := 0 to data.Height-1 do
data.Left[index] := GetInt( 1, index+2 );
plan := TData.Create;
potential := TData.Create;
Memo1.Lines.Add( 'Исходные данные:' );
Dump( data, 7 );
Memo1.Lines.Add( '');
Memo1.Lines.Add( '***Метод северо-западного угла.***' );
Memo1.Lines.Add( '');
Memo1.Lines.Add( 'Опорный план:' );
CalcNorthWest( data, plan );
Dump( plan, 1 );
Memo1.Lines.Add( 'Решение(общая стоимость): ' + IntToStr( CalcSum(data, plan) ) ); {}
Memo1.Lines.Add( '');
Memo1.Lines.Add( '***Метод наименьшей стоимости.***' );
Memo1.Lines.Add( '');
Memo1.Lines.Add( 'Опорный план:' );
CalcMinEl( data, plan );
Dump( plan, 1 );
Memo1.Lines.Add( 'Решение(общая стоимость): ' + IntToStr( CalcSum(data, plan) ) ); {}
Memo1.Lines.Add( '');
Memo1.Lines.Add( '***Метод потенциалов.***' );
Memo1.Lines.Add( '');
old_s := 0;
while (true) do
begin
Memo1.Lines.Add( 'Вычисление потенциалов;' );
CalcPotential( data, plan, potential );
Memo1.Lines.Add( '');
Memo1.Lines.Add( 'Матрица оценок:' );
Dump( potential, 1 ); {}
if (potential.Min >= 0) then
begin
for index:=0 to plan.Height-1 do
for index2:=0 to plan.Width-1 do
StringGrid4.Cells[index2,index]:=inttostr(plan.Arr[index2,index]);
Memo1.Lines.Add( '');
Memo1.Lines.Add( 'Вычисления завершены.' );
Memo1.Lines.Add( 'Полученный план оптимален.' );
label9.Caption:=label9.Caption+ ' ' + IntToStr( CalcSum(data, plan) );
break;
end;
ShiftPlan( data, plan, potential );
s := CalcSum(data, plan);
Memo1.Lines.Add( '');
Memo1.Lines.Add( 'Полученный план:' );
Dump( plan, 1 );
Memo1.Lines.Add( 'Решение(общая стоимость): ' + IntToStr(s) );
Memo1.Lines.Add( '');
if (old_s = s) then
begin
label9.Caption:=label9.Caption+ ' ' + IntToStr( CalcSum(data, plan) );
break
end
else
old_s := s;
end;
end;
{ TData }
procedure TData.Assign(data: TData); //?
var
index, index2: integer;
begin
AssignLT( data );
for index := 0 to Height-1 do
for index2 := 0 to Width-1 do
Arr[index2,index] := data.Arr[index2,index];
end;
procedure TData.AssignLT(data: TData); //?
var
index: integer;
begin
Reset;
Width := data.Width;
Height := data.Height;
for index := 0 to Width-1 do
Top[index] := data.Top[index];
for index := 0 to Height-1 do
Left[index] := data.Left[index];
end;
constructor TData.Create;
begin
Reset;
end;
function TForm1.Check(data: TData): boolean;
var
s, index: integer;
begin
s := 0;
for index := 0 to data.Width-1 do
s := s + data.Top[index];
for index := 0 to data.Height-1 do
s := s - data.Left[index];
Result := s = 0;
end;
procedure TForm1.CalcNorthWest( data: TData; var plan: TData); // вычислить методом северно западного угла
var
index, index2, t: integer;
begin
index := 0;
index2 := 0;
plan.AssignLT( data );
while (index < plan.Height) and (index2 < plan.Width) do
begin
t := min( plan.Left[index], plan.Top[index2] );
plan.Arr[index2,index] := t;
plan.Top[index2] := plan.Top[index2]-t;
plan.Left[index] := plan.Left[index]-t;
if (plan.Top[index2] = 0) then
index2 := index2+1;
if (plan.Left[index] = 0) then
index := index+1;
end;
for index:=0 to plan.Height-1 do
for index2:=0 to plan.Width-1 do
StringGrid2.Cells[index2,index]:=inttostr(plan.Arr[index2,index]);
label7.Caption:=label7.Caption+ ' ' + IntToStr( CalcSum(data, plan) );
end;
procedure TForm1.Dump(data: TData; fl: integer); //вывод матрицы в мемо
function i2s( i: integer ): string;
var
r: string;
begin
r := IntToStr( i );
while( length(r) < 3 ) do
r := ' ' + r;
Result := r;
end;
var
index, index2: integer;
s: string;
begin
// top
if ((fl and 2) <> 0) then
begin
s := ' ';
for index := 0 to data.Width-1 do
s := s + i2s( data.Top[index] );
Memo1.Lines.Add( s );
end;
if ((fl and 5) = 0) then
exit;
for index := 0 to data.Height-1 do
begin
// left
if ((fl and 4) <> 0) then
s := i2s( data.Left[index] )
else
s := '';
// arr
if ((fl and 1) <> 0) then
for index2 := 0 to data.Width-1 do
s := s + i2s( data.Arr[index2,index] );
Memo1.Lines.Add( s );
end;
end;
procedure TForm1.Button3Click(Sender: TObject); // кнопка №77
procedure c( x, y: integer; s: string );
begin
StringGrid1.Cells[ x, y ] := s;
end;
begin
StringGrid1.ColCount := 7;
StringGrid1.RowCount := 6;
// top
c( 2, 1, '19' );
c( 3, 1, '19' );
c( 4, 1, '19' );
c( 5, 1, '19' );
c( 6, 1, '4' );
// left
c( 1, 2, '20' );
c( 1, 3, '20' );
c( 1, 4, '20' );
c( 1, 5, '20' );
// mid
c( 2, 2, '15' );
c( 3, 2, '1' );
c( 4, 2, '22' );
c( 5, 2, '19' );
c( 6, 2, '1' );
c( 2, 3, '21' );
c( 3, 3, '18' );
c( 4, 3, '11' );
c( 5, 3, '4' );
c( 6, 3, '3' );
c( 2, 4, '26' );
c( 3, 4, '19' );
c( 4, 4, '23' );
c( 5, 4, '26' );
c( 6, 4, '25' );
c( 2, 5, '21' );
c( 3, 5, '10' );
c( 4, 5, '3' );
c( 5, 5, '19' );
c( 6, 5, '27' );
end;
function TForm1.CalcSum(data, plan: TData): integer; //вычисление суммы затрат
var
index, index2, s: integer;
begin
s := 0;
for index := 0 to data.Height-1 do
for index2 := 0 to data.Width-1 do
s := s + data.Arr[index2,index] * plan.Arr[index2, index];
Result := s;
end;
function TData.Min: integer; //нахождение минимального элемента массива
var
index, index2, m: integer;
begin
m := MaxInt;
for index := 0 to Height-1 do
for index2 := 0 to Width-1 do
if (m > Arr[index2,index]) then
m := Arr[index2,index];
Result := m;
end;
function TData.NoNulls: integer; // вроде нахождение количества ненулевых элементов
var
index, index2, c: integer;
begin
c := 0;
for index := 0 to Height-1 do
for index2:= 0 to Width-1 do
if (Arr[index2,index] > 0) then
inc(c);
Result := c;
end;
procedure TForm1.CalcMinEl( data: TData; var plan: TData );
var
index, index2, x_m, y_m, v_m, s, v: integer;
begin
s := 0;
plan.AssignLT( data );
for index := 0 to plan.Width-1 do
s := s + data.Top[index];
while (s > 0) do
begin
v_m := MaxInt;
x_m := -1;
y_m := -1;
for index := 0 to plan.Height-1 do
for index2 := 0 to plan.Width-1 do
if ((v_m > data.Arr[index2,index]) and
(plan.Arr[index2,index] = 0) and
(plan.Top[index2] > 0) and (plan.Left[index] > 0)) then
begin
v_m := data.Arr[index2,index];
x_m := index2;
y_m := index;
end;
if (v_m = MaxInt) then
break;
v := min( plan.Top[ x_m ], plan.Left[ y_m ] );
plan.Top[ x_m ] := plan.Top[ x_m ] - v;
plan.Left[ y_m ] := plan.Left[ y_m ] - v;
plan.Arr[ x_m, y_m ] := v;
s := s - v;
for index:=0 to plan.Height-1 do
for index2:=0 to plan.Width-1 do
StringGrid3.Cells[index2,index]:=inttostr(plan.Arr[index2,index]);
end;
label8.Caption:=label8.Caption+ ' ' + IntToStr( CalcSum(data, plan) );
end;
procedure TData.Reset;
begin
FillChar( Left, sizeof(Left), 0 );
FillChar( Top, sizeof(Top), 0 );
FillChar( Arr, sizeof(Arr), 0 );
end;
procedure TEqSolve.AddEq( p1,p2,s : integer );
begin
Eq[ fEqCount ].p1 := p1;
Eq[ fEqCount ].p2 := p2 + fH;
Eq[ fEqCount ].sum := s;
Eq[ fEqCount ].solved := false;
// вывод уравнений
Form1.Memo1.Lines.Add( 'u' + IntToStr(p1+1) + ' + v' + IntToStr(p2+1) +
' = ' + IntToStr( s ) ); {}
inc( fEqCount );
end;
constructor TEqSolve.Create( h, v_c: integer );
begin
FillChar( Eq, sizeof(Eq), 0 );
FillChar( fV, sizeof(fV), 0 );
fEqCount := 0;
fVarCount := v_c;
fH := h;
end;
function TEqSolve.GetU(index: integer): TVar;
begin
Result := fV[index];
end;
function TEqSolve.GetV(index: integer): TVar;
begin
Result := fV[index+fH];
end;
procedure TEqSolve.Solve;
var
non_solved, index, c: integer;
ceq: ^TEquation;
begin
FillChar( fV, sizeof(fV), 0 );
non_solved := fVarCount-1;
fV[0].v := 0;
fV[0].solved := true;
while (non_solved > 0) do
begin
c := 0;
for index := 0 to fEqCount-1 do
begin
ceq := @Eq[index];
if (ceq.solved) then continue;
if (fV[ ceq.p1 ].solved) then
begin
fV[ ceq.p2 ].v := ceq.sum - fV[ ceq.p1 ].v;
fV[ ceq.p2 ].solved := true;
inc(c);
ceq.solved := true;
end
else if (fV[ ceq.p2 ].solved) then
begin
fV[ ceq.p1 ].v := ceq.sum - fV[ ceq.p2 ].v;
fv[ ceq.p1 ].solved := true;
inc(c);
ceq.solved := true;
end;
end; // for
if (c = 0) then
exit;
end;
end;
procedure TForm1.CalcPotential(data: TData; var plan, x: TData);
function to_sign( v: integer ): integer;
begin
if (v = 0) then
Result := 1
else
Result := -1;
end;
var
index, index2, t: integer;
solve: TEqSolve;
s: string;
begin
// Создать систему уравнений и решить ее
solve := TEqSolve.Create( plan.Height, plan.Height + plan.Width );
for index := 0 to plan.Height-1 do
for index2 := 0 to plan.Width-1 do
if (plan.Arr[index2,index] > 0) then
solve.AddEq( index, index2, data.Arr[index2,index] );
index := 0;
index2 := 0;
while (solve.fEqCount < plan.Height + plan.Width-1) do
begin
inc(index2);
if (index2 = plan.Width) then
begin
index2 := 0;
inc( index );
if (index = plan.Height) then
break; // wtf ?
end;
if (plan.Arr[index2,index] = 0) then
solve.AddEq( index, index2, data.Arr[index2,index] );
end; {}
solve.Solve;
s := 'u: ';
for index := 0 to plan.Height-1 do
s := s + ' ' + IntToStr( solve.U[index].v );
Form1.Memo1.Lines.Add( s );
s := 'v: ';
for index := 0 to plan.Width-1 do
s := s + ' ' + IntToStr( solve.V[index].v );
Form1.Memo1.Lines.Add( s );
x.Reset;
x.AssignLT( data );
for index := 0 to plan.Height-1 do
for index2 := 0 to plan.Width-1 do
if (plan.Arr[index2,index] = 0) then
begin
t := (solve.V[index2].v + solve.U[index].v); // * to_sign( (index+index2) and 1 );
x.Arr[index2,index] := data.Arr[index2,index] - t;
end; {}
end;
procedure TForm1.ShiftPlan(var data, plan, potential: TData );
var
x_m, y_m, v_m, f, f2: integer;
a: TData;
flag: boolean;
procedure Line( x, y, vert, val: integer );
begin
if (vert = 1) then y := plan.Width-1
else x := 0;
while (x < plan.Width) and (y >= 0) { plan.Height) } and (not flag) do
begin
if (plan.Arr[x,y] <> 0) and (a.Arr[x,y] = 0) then
begin
a.Arr[x,y] := val;
if (x = x_m) and (vert = 0) then
flag := true;
end;
if (vert = 1) then dec(y)
else inc(x);
end; {}
end;
// Найти значение в строке/столбце
procedure Find( var x, y: integer; vert, val: integer );
begin
if (vert = 1) then y := 0
else x := 0;
while (x < plan.Width) and (y < plan.Height) do
begin
if a.Arr[x,y] = val then
break;
if (vert = 1) then inc(y)
else inc(x);
end;
end;
var
index, index2, x1, y1: integer;
path: array [0..100] of TPoint;
begin
FillChar( path, sizeof(path), 0 );
// Ищем минимальный элемент в C
x_m := -1;
y_m := -1;
v_m := MaxInt;
for index := 0 to plan.Height-1 do
for index2 := 0 to plan.Width-1 do
if (potential.Arr[index2,index] < v_m) then
begin
x_m := index2;
y_m := index;
v_m := potential.Arr[index2,index];
end;
// Ищем путь
a := TData.Create;
a.AssignLT( plan );
a.Arr[x_m,y_m] := 1;
// Строим путь (вперед)
flag := false;
f := 1;
while not flag do
begin
for index := 0 to plan.Height-1 do
for index2 := 0 to plan.Width-1 do
if (a.Arr[index2,index] = f) then
begin
Line( index2, index, (f+1) and 1, f+1 );
{ Memo1.Lines.Add( 'path (' + IntToStr(f) + '):' );
Dump( a, 1 ); {}
end;
inc( f );
end; {}
// Строим путь (назад)
x1 := x_m;
y1 := y_m;
f2 := f;
while (f >= 0) do
begin
path[f].x := x1;
path[f].y := y1;
Find( x1, y1, (f+1) and 1, f );
dec(f);
end;
v_m := MaxInt;
x_m := -1;
index := 1;
while (index < f2) do
begin
f := plan.Arr[ path[index].x, path[index].y ];
if (f < v_m) then
begin
v_m := f;
x_m := index;
end;
inc(index,2);
end;
for index := 0 to f2-1 do
begin
f := plan.Arr[ path[index].x, path[index].y ];
if ( (index and 1) = 0 ) then f := f + v_m
else f := f - v_m;
plan.Arr[ path[index].x, path[index].y ] := f;
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
procedure c( x, y: integer; s: string );
begin
StringGrid1.Cells[ x, y ] := s;
end;
var index, index2: integer;
begin
StringGrid1.ColCount := 7;
StringGrid1.RowCount := 6;
// top
for index2:=2 to StringGrid1.ColCount-1 do
c( index2, 1, '' );
// left
for index:=2 to StringGrid1.RowCount-1 do
c( 1, index, '' );
// mid
for index2:=2 to StringGrid1.ColCount-1 do
for index:=2 to StringGrid1.RowCount-1 do
c( index2, index, '' );
end;
procedure TForm1.Button4Click(Sender: TObject);
procedure c( x, y: integer; s: string );
begin
StringGrid1.Cells[ x, y ] := s;
end;
var index, index2,st, summa2: integer;
summa: real;
begin
StringGrid1.ColCount := 7;
StringGrid1.RowCount := 6;
// top
summa:=0;
for index2:=2 to StringGrid1.ColCount-1 do
begin
st:=random(20)+1;
c( index2, 1, inttostr(st) );
summa:=summa+st;
end;
summa2:=0;
// left
for index:=2 to StringGrid1.RowCount-1 do
begin
if index = StringGrid1.RowCount-1 then
st:=round(summa)-summa2
else
st:=random(round(summa/(StringGrid1.RowCount-index)))+1;
c( 1, index, inttostr(st) );
summa2:=summa2+st;
end;
// mid
for index2:=2 to StringGrid1.ColCount-1 do
for index:=2 to StringGrid1.RowCount-1 do
c( index2, index, inttostr(random(30)+1) );
end;
end.
Заключение
В данной курсовой работе была решена задача линейного программирования с помощью следующих методов: метода северо-западного угла, метода минимальной стоимости и метода потенциалов. Были рассмотрены алгоритмы решения задачи данными методами. В результате были получены данные по оптимальному распределению груза от поставщиков к потребителям при наименьших затратах на перевозку груза.
В среде Delphi было разработано приложение, решающую эту задачу с различными исходными данными. Список используемой литературы
1. Колесников В.П., Рябцева С.В. - Белгород: Изд-во БИЭИ, 2005. - 200 с.
2. Величко Д.В., Рубанов В.Г. Численные методы и оптимизация. - Белгород: Изд-во БГТУ, 2008. - 160 с.
Документ
Категория
Рефераты
Просмотров
71
Размер файла
1 389 Кб
Теги
готовая, бгту, транса, курсовая
1/--страниц
Пожаловаться на содержимое документа