Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
8
«Транспортная задача»
2010
Реферат
Программа «OptTrans»
Цель работы – изучение транспортной задачи, с последующим написанием программы «OptTrans», которая наглядно представляет решение транспортной задачи. Данная программа может использоваться в процессе изучения по дисциплине «Методы программирования».
В результате проведенной работы был создан программный продукт, реализующий все заданные требования указанные в техническом задании.
Программа разработана на языке Borland С++ Builder (version 6.0). Выбор обусловлен тем, что данный язык наиболее распространен среди разработчиков программного обеспечения, а визуальная среда позволяет сделать программу проще для понимания пользователем.
Отчёт выполнен в текстовом редакторе Microsoft Word, и приложен на дискете к бумажному варианту вместе с исходным кодом и руководствами пользователя и программиста.
СОДЕРЖАНИЕ
2.3 Описание технического проекта…………………………………………18
Создать наглядное решение транспортной задачи. Программа ««OptTrans» предполагает реализацию метода потенциалов решения транспортной задачи на языке Borland С++ Builder. Алгоритмы, которые предполагается реализовать в данном проекте, можно использовать в обучающем процессе по дисциплине «Методы программирования», «Методы оптимизации».
В результате были разработаны процедуры, реализующие следующие функции:
GenDan
Матрица штрафов:
Задается цикл для обхода всех клеток матрици. При помощи библиотечной функии random, ячейкам случайным образом задаются значения 0-10.
Объмы складов и заводов:
Задается цикл для обхода всех клеток массива. При помощи библиотечной функии random, ячейкам случайным образом задаются значения 1-100.
OPRplant
Выбирается клетка с координатой [1][1], и для неё анализируются объемы складов и производства. Результирующее значение имеет меньший параметр. Далее движемся либо вниз, либо вправо и анализируем следующую клетку. Очередная загружаемая коммуникация выбирается в левой верхней клетке сохраненной части таблицы, т.е. в северо-западном углу таблицы. Математически это выражается следующим образом:
, I – множество номеров пунктов производства;
, J – множество номеров пунктов потребления;
OPTplant
Для наглядности работы процедуры приведем пример:
1) для каждой занятой клетки транспортной таблицы сумма потенциалов должна быть равна для этой клетки;
2) для каждой незанятой клетки сумма потенциалов не больше (меньше или равно) .
Построим для каждой свободной переменной плана числа и они должны быть положительны. Так как число потенциалов равно 9, а система состоит из 8 уравнений, то для нахождения какого-либо решения этой системы необходимо первому из потенциалов придать произвольное значение (например: ). Далее последовательно находим значения всех потенциалов. Распишем подробно эту процедуру.
|
Заводы Склады |
Заводы 1 |
Заводы 2 |
Заводы 3 |
Заводы 4 |
Заводы 5 |
||
|
5 |
18 |
17 |
22 |
8 |
|||
|
Склад 1 |
15 |
15 |
|||||
|
Склад 2 |
20 |
17 |
3 |
||||
|
Склад 3 |
10 |
2 |
8 |
||||
|
Склад 4 |
25 |
5 |
18 |
2 |
|||
Таким образом, после того, как все потенциалы найдены, можно искать :
Видно, что и меньше нуля, значит существующий опорный план можно улучшить. Поскольку , нужно ввести в базис вектор, соответствующий клетке (2; 1), для чего загрузить ее некоторым количеством единиц груза. Но, так как мы, увеличивая загрузку (2; 1), нарушаем баланс строк и столбцов распределительной таблицы, то следует изменить объемы поставок в ряде других занятых клеток. А чтобы число базисных переменных осталось прежним, необходимо вывести из базиса одну переменную. Выводится обычно та переменная, у которой загрузка в цикле минимальна.
Строим цикл:
(2; 1) – начальная точка цикла;
Что характерно, для этой точки (впрочем как и для других) мы можем построить только один цикл. Каждой клетке цикла приписываем определенный знак:
(2; 1) – “+”, (4; 1) – “-”, (4; 4) – “+” (2; 4) – “-”.
|
+ + - - Заводы Склады |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
Завод 5 |
|
|
5 |
18 |
17 |
22 |
8 |
||
|
Склад 1 |
15 |
15 |
||||
|
Склад 2 |
20 |
17 |
3 |
|||
|
Склад 3 |
10 |
2 |
8 |
|||
|
Склад 4 |
25 |
5 |
18 |
2 |
В клетках с “+” – увеличиваем загрузку, а в клетках с “-” – уменьшаем. Величина, на которую увеличиваем или уменьшаем всегда одна и она определяется из условия:
, где – содержимое клеток с “-”.
Таким образом получаем:
, а значит из базиса будет выведена (2; 4), где в процессе реализации цикла загрузка уменьшится до 0.
Перейдем к новому опорному плану
|
Заводы Склады |
Завод 1 |
Завод 2 |
Завод 3 |
Завод 4 |
Завод 5 |
||
|
5 |
18 |
17 |
22 |
8 |
|||
|
Склад 1 |
15 |
15 |
|||||
|
Склад 2 |
20 |
3 |
17 |
||||
|
Склад 3 |
10 |
2 |
8 |
||||
|
Склад 4 |
25 |
2 |
18 |
5 |
|||
Определяем
Все больше 0, следовательно план оптимальный.
.
Целевая функция при этом плане:
2.3 Описание технического проекта:
Задача группы заключается в создании программного продукта соответствующего следующим требованиям:
Для реализации решения необходим набор следующих сервисов и технологий:
Исполняемый файл project.exe использует в процессе выполнения следующие данные: