Автор работы: Пользователь скрыл имя, 31 Мая 2012 в 18:05, курсовая работа
Данная курсовая работа имеет прямое отношение к экономике и звучит как первый опорный план о минимальной стоимости перевозки газа. Эта задача является одной из важнейших экономических задач в наше время, ведь различные крупные газодобывающие организации нуждаются в постоянной транспортировке газа в различные точки города, страны или даже мира.
Введение 4
1. Общая часть 5
1.1. Цель разработки 5
1.2. Анализ использования разработки 5
1.3. Анализ методов решения 6
1.4. Анализ средств программирования 6
1.4.1. Характеристики ПЭВМ 6
1.4.2. Характеристика ПО 8
1.4.3. Обзор средств программирования 9
1.4.4. Характеристика языков программирования 10
2. Специальная часть 13
2.1. Постановка задачи 13
2.2. Экономико-математическая модель 14
2.3. Метод северо-западного угла 15
2.4. Метод минимальной стоимости 17
2.5. Алгоритм решения задачи 20
2.5.1. Алгоритм основной программы 20
2.5.2. Алгоритм процедуры TForm1.Edit1Exit 21
2.5.3. Алгоритм процедуры TForm1.Edit2Exit 22
2.5.4. Алгоритм процедуры TForm1.Button4Click 23
2.5.5. Алгоритм процедуры TForm1.Button3Click1 23
2.5.6. Алгоритм процедуры sevzar 29
2.5.7. Алгоритм процедуры minelem 30
2.6. Описание решения задачи 32
2.6.1. Описание алгоритма основной программы 32
2.6.2. Описание алгоритма процедуры TForm1.Edit1Exit 32
2.6.3. Описание алгоритма процедуры TForm1.Edit2Exit 33
2.6.4. Описание алгоритма процедуры TForm1.Button4Click 33
2.6.5. Описание алгоритма процедуры TForm1.Button3Click1 33
2.6.6. Описание алгоритма процедуры sevzap 34
2.6.7. Описание алгоритма процедуры minelem 35
2.7. Ручной расчет контрольных примеров 36
2.8. Описание процесса отладки программы 51
Заключение 53
Список литературы 54
Заполнение таблицы
Метод состоит из ряда однотипных шагов, на каждом из которых, исходя из запасов очередного поставщика и запросов очередного потребителя, заполняется только одна клетка и соответственно исключается из рассмотрения один поставщик или один потребитель.
В данном примере три поставщика с м3 газа 12, 18 и 10, и три потребителя с м3 газа 10, 11 и 19, как показано в таблице 2.
Таблица 2
В1 |
В2 |
В3 |
|||||
А1 |
|
1 |
|
2 |
|
3 |
12 |
А2 |
|
4 |
|
1 |
|
6 |
18 |
А3 |
|
7 |
|
4 |
|
9 |
10 |
10 |
11 |
19 |
|||||
Если запасы первого поставщика больше запросов первого потребителя, то записываем в клетку (1,1) сумму запроса первого потребителя и переходим ко второму потребителю. Если же запасы первого поставщика меньше запросов первого потребителя, то записываем в клетку (1,1) сумму запасов первого поставщика, исключаем из рассмотрения первого поставщика и переходим ко второму поставщику.
Таким образом, так как запасы первого поставщика (A1) больше запросов первого потребителя (B1), в клетку (1,1) записываем сумму запросов B1 (10), и первого потребителя исключаем из рассмотрения. В клетку с запасами первого поставщика записываем количество неизрасходованных запасов, т.е. 12 - 10 = 2.
Таблица 3
В1 |
В2 |
В3 |
|||||
А1 |
10 |
1 |
|
2 |
|
3 |
2 |
А2 |
|
4 |
|
1 |
|
6 |
18 |
А3 |
|
7 |
|
4 |
|
9 |
10 |
0 |
11 |
19 |
|||||
Выполняя аналогичные
действия для следующих пар поставщик-
Таблица 4
В1 |
В2 |
В3 |
|||||
А1 |
10 |
1 |
2 |
2 |
|
3 |
0 |
А2 |
|
4 |
9 |
1 |
9 |
6 |
0 |
А3 |
|
7 |
|
4 |
10 |
9 |
0 |
0 |
0 |
0 |
|||||
После того как первый опорный план найден, рассчитывается целевая функция задачи. В данном случае F=10*1+2*2+9*1+9*6+10*9=167.
Следующий метод, рассмотренный в данной работе, называется метод минимальной стоимости.
Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости:
где cij – стоимость перевозки единицы газа от i-ого поставщика j-ому потребителю;
и исключается из рассмотрения только одна строка (поставщик) или один столбец (потребитель). Очередную клетку, соответствующую условию, заполняют по тем же правилам, что и в методе северо-западного угла. Поставщик исключается из рассмотрения, если его запасы груза использованы полностью. Потребитель исключается из рассмотрения, если его запросы удовлетворены полностью. На каждом шаге исключается либо один поставщик, либо один потребитель. При этом если поставщик еще не исключен, но его запасы равны нулю, то на том шаге, когда от данного поставщика требуется поставить груз, в соответствующую клетку таблицы заносится базисный нуль и лишь, затем поставщик исключается из рассмотрения. Аналогично с потребителем.
В данном примере сначала заполнятся клетка (1,1), поскольку цена перевозки газа в эту клетку равна 1, т.е., минимальна. В клетку записывается сумма запросов B1 (10), первый потребитель исключается из рассмотрения, а в клетку с запасами первого поставщика записывается количество неизрасходованных запасов (2).
Таблица 5
В1 |
В2 |
В3 |
|||||
А1 |
10 |
1 |
|
2 |
|
3 |
2 |
А2 |
|
4 |
|
1 |
|
6 |
18 |
А3 |
|
7 |
|
4 |
|
9 |
10 |
0 |
11 |
19 |
|||||
Затем ищем следующий минимальный
элемент матрицы стоимостей. Это
клетка (2,2). Записываем в нее значение
по правилам.
Таблица 6
В1 |
В2 |
В3 |
|||||
А1 |
10 |
1 |
|
2 |
|
3 |
2 |
А2 |
|
4 |
11 |
1 |
|
6 |
7 |
А3 |
|
7 |
|
4 |
|
9 |
10 |
0 |
0 |
19 |
|||||