Решение транспортной задачи методом потенциалов
Содержание
1. Постановка
задачи
.1 Требования
к системе и ее структуре
.2 Требования
к функциям, выполняемым системой
.3 Требования
к программно-аппаратному обеспечению
.4 Требования
к техническому обеспечению
.6 Требования
к надежности и хранению информации
. Основная
часть
.1 Математическая
модель
.3 Метод
решения задачи
.3
Структурная схема программы
.4 Схема
взаимодействия модулей
. Руководство
программисту
Руководство
пользователю
.1 Общие
сведения
.2 Работа с
помощью
.3 Наиболее
вероятные ошибки
Заключение
Список
использованных источников
Приложение А
Текст программы
Приложение Б
Формы программы
Приложение В
Диск с программой
Введение
Данный курсовой проект выполнен на тему «Решение транспортной задачи
методом потенциалов».
Решение транспортных задач методом потенциалов была актуальна уже давно и
продолжает быть актуальной в сфере бизнеса и экономики, т.к. получение
наибольшей выгоды является основной задачей любого предприятия и
предпринимателя. Построение оптимального плана перевозки грузов посредством
автоматизации в значительной степени ускоряет работу, а также снижает затраты
по времени и средствам нахождения оптимального пути.
Целью курсового проекта является реализация решения транспортной задачи
методом потенциалов на компьютере средствами среды программирования Delphi.
Для достижения поставленной цели необходимо решение следующих задач:
) изучение теоретического материала по теме работы;
) рассмотрение метода потенциалов;
) создание ПП;
) описание создания программного продукта по теме работы.
. Постановка
задачи
Разработать программный продукт, реализующий математический метод решения
транспортной задачи «метод потенциалов» в среде программирования Borland Delphi.
К основным характеристикам функциональных задач, уточняемых в процессе
формализованной постановки, относят:
1) цель и назначение задачи, её место и связь с другими задачами: целью
разработки программного продукта является автоматическое решение транспортных
задач «методом потенциалов»;
2) условия решения задачи с использованием средств вычислительной
техники:
- процессор: AMD Turion™ II Dual-Core M500 2.20 GHz и выше;
- полный объём физической памяти: 512,00 МБ и выше;
- виртуальная память: 2,00 ГБ;
- операционная система Microsoft Windows XP / Seven;
- видео карта 216 Мб;
- клавиатура;
- мышь;
3) содержание функций обработки входной информации для решения задачи:
ввод данных, проверка корректности данных, сохранение;
4) требование к периодичности решения задачи: по требованию;
) ограничение по срокам и точности выходной информации: вывод
интересующей информации происходит сразу после обработки запроса пользователя;
) источники входной информации для решения задачи: цены на
перевозки грузов, а также запасы и потребности потребителей;
) состав и форма представления выходной информации: результатом
работы программы является нахождение опорного плана перевозок, расчет затрат и
сравнение затрат оптимизированного плана перевозок с первичным планом;
) пользователи задачи: программа предназначается для использования
ее пользователями, нуждающимися в решение подобного рода задач.
1.1 Требования
к системе и ее структуре
Для полноценной работы программы необходимо наличие следующего
программного обеспечения:
·
операционная
система Windows 7;
·
Borland
Delphi 7.0.
Для надежной работы программы в системе должны быть установлены
русскоязычные шрифты.
1.2 Требования
к функциям, выполняемым системой
Функции, которые осуществляет система, должны придерживаться следующих
правил:
универсальные системы;
поддержка безошибочной и корректной работы своих функций;
поддержка стандартов той операционной системы, в которой работает
программа;
- корректировка различных данных;
Это дает возможность пользователю программы выполнять необходимую ему
работу быстро и избежать ошибок.
.3 Требования
к программно-аппаратному обеспечению
Для корректной работы с данным программным продуктом необходимы следующие
требования:
- операционная система Microsoft Windows XP / Seven;
- процессор семейства Intel или AMD с тактовой частотой от 1 ГГц;
- видео карта 216 Мб;
- свободное место на жестком диске более 10 Мб.
1.4
Требования к техническому обеспечению
Для использования данного программного продукта необходимо следующее
техническое обеспечение:
·
ОЗУ не менее 512
Мб;
·
клавиатура;
·
мышь;
·
монитор.
.5 Требования к эргономике и технической эстетике
Взаимодействие пользователей с прикладным программным обеспечением,
входящим в состав системы должно осуществляться посредством визуального
графического интерфейса. Интерфейс системы должен быть понятным и удобным, не
должен быть перегружен графическими элементами и должен обеспечивать быстрое
отображение информации. Навигационные элементы должны быть выполнены в удобной
для пользователя форме. Средства редактирования информации должны удовлетворять
принятым соглашениям в части использования функциональных клавиш, режимов
работы, поиска, использования оконной системы. Ввод-вывод данных системы, прием
управляющих команд и отображение результатов их исполнения должны выполняться в
интерактивном режиме. Интерфейс должен соответствовать современным
эргономическим требованиям и обеспечивать удобный доступ к основным функциям и
операциям системы.
Система должна обеспечивать корректную обработку аварийных ситуаций,
вызванных неверными действиями пользователей, неверным форматом или
недопустимыми значениями входных данных. В указанных случаях система должна
выдавать пользователю соответствующие сообщения, после чего возвращаться в
рабочее состояние, предшествовавшее неверной (недопустимой) команде или
некорректному вводу данных.
Экранные формы должны проектироваться с учетом требований унификации:
·
все экранные
формы пользовательского интерфейса должны быть выполнены в едином графическом
дизайне, с одинаковым расположением основных элементов управления и навигации;
·
для обозначения
сходных операций должны использоваться сходные графические значки, кнопки и
другие управляющие (навигационные) элементы. Термины, используемые для
обозначения типовых операций (добавление информационной сущности,
редактирование поля данных), а также последовательности действий пользователя
при их выполнении, должны быть унифицированы;
·
внешнее поведение
сходных элементов интерфейса (реакция на наведение указателя «мыши»,
переключение фокуса, нажатие кнопки) должны реализовываться одинаково для
однотипных элементов.
1.6
Требования к надежности и хранению информации
Настоящая программный продукт выполнена с учётом ошибок, которые могут
возникнуть при работе с этой программой. В программный пакет данной программы
включен раздел справки, который содержит в себе помощь и информацию о программе
и разработчике.
От правильности работы пользователя с программой, будет зависеть
надёжность работы программы.
При разработке программы было минимизировано появление всех возможных
ошибок.
Ниже дан ряд рекомендаций при возможном появлении ошибок.
При некорректном запросе данных, например, изменении путей к внешним
модулям или библиотекам, программа не выполняет команды пользователя. Во
избежание появления данной ошибки советуем не перемещать какие-либо файлы из
родительских каталогов.
Когда системные требования не удовлетворяют программу, могут произойти
смещение гиперссылочного текста, а так же различные сбои размещения окна
программы или отдельных его элементов.
2
2. Основная часть
2.1 Математическая
модель
Математическая модель - это способ описания реальной жизненной
ситуации (задачи) с помощью математического языка.
Транспортная задача - задача о поиске оптимального распределения поставок
однородного товара от поставщиков к потребителям при известных затратах на
перевозку (тарифах) между пунктами отправления и назначения
В общем виде транспортную задачу принято рассматривать в виде таблицы (таблица
1).
Таблица 1- Общий вид транспортной задачи
|
Поставщики
|
Потребители
|
Запасы груза
|
|
В1
|
В2
|
…
|
Вm
|
|
|
А1
|
|
c11
|
|
c12
|
…
|
|
c1m
|
a1
|
|
x11
|
x12
|
|
x1m
|
|
|
А2
|
|
c21
|
|
c22
|
…
|
|
c2m
|
a2
|
|
x21
|
x22
|
|
x2m
|
|
|
…
|
…
|
…
|
…
|
…
|
…
|
|
Аn
|
|
cn1
|
|
cn2
|
…
|
|
cnm
|
an
|
|
xn1
|
xn2
|
|
xnm
|
|
|
Потребности в грузе
|
b1
|
b2
|
…
|
bm
|
|
где
Аi - поставщики груза (i=
)
Bj -
потребители груза (j=
)
ai -
запасы груза (i=)
bJ -
потребители в грузе (j=)
cij -
стоимость (тариф) каждой перевозки (i=, j=)
xij -
количество распределенного товара от i-го поставщика j-му
потребителю(i=, j=).
Если
в транспортной задаче выполняется условие формулы (1), то транспортная задача
называется закрытой, иначе - открытой.
Для написания модели необходимо все ограничения и целевую функцию
представить в виде математических уравнений (формулы 2, 3, 4, 5 и 6).
(j=);
xij ≥ 0
(i=;j=);
.
Методами
отыскания начального плана (опорного решения) для решения транспортной задачи
являются:
1. метод «северо-западного угла»;
2. метод минимального элемента;
3. метод Фогеля.
Для оптимизации опорного плана транспортной задачи используется метод
потенциалов.
.3 Метод
решения задачи
Метод потенциалов является модификацией симплекс-метода решения задачи
линейного программирования применительно к транспортной задаче. Он позволяет,
отправляясь от некоторого допустимого решения, получить оптимальное решение за
конечное число итераций.
Метод потенциалов предназначен для решения транспортной задачи в
матричной постановке. Потенциалы - это двойственные переменные. Сам метод -
прямой, на каждом шаге выбирается одно из двойственных ограничений, которое не
выполняется и исправляется таким образом, чтобы не нарушить ограничения прямой
задачи. Постепенно в двойственной задаче ограничения будут выполнены, что будет
означать оптимальность в прямой задаче.
Таблица для метода потенциалов (таблица 2) имеет следующий вид:
Таблица 2 - Вид таблицы метода потенциалов
|
B1 …
|
Bj
|
… Bn
|
U
|
|
A1 …
|
|
|
|
U1 …
|
|
Aj
|
|
Cij Xij
|
|
Ui
|
|
Am …
|
|
|
|
Um …
|
|
v
|
v1 …
|
vj
|
… vn
|
Z
|
Каждая ячейка (i; j) таблицы хранит информацию о цене (Сij) и о количестве перевозимого товара
(Xij). В процессе решения задачи часть
клеток будем называть базисными, а остальные - небазисными (или свободными).
Алгоритм решения.
1. Замкнуть задачу, если она не замкнута. Перейти на шаг 2.
2. Нарисовать начальную таблицу. Перейти на шаг 3.
. Рассчитать начальный план перевозок (например, методом
северо-западного угла) и выделить базисные клетки. Вычислить значение целевой функции. Перейти на шаг 4.
4. Рассчитать значения потенциалов. Положить u1 = 0 (или любому
другому числу). Остальные потенциалы рассчитать с помощью базисных клеток,
исходя из уравнения ui + vj = cij. Перейти на шаг 5.
. Для свободных клеток рассчитать оценки sij = cij - vi - vj. Если
все sij > 0, то найдено оптимальное решение. Перейти на шаг 5. Иначе выполнить шаг 6.
. Из небазисных клеток выбрать ту, у которой оценка sij минимальна
и для нее выполнить следующую процедуру:
- построить цикл для этой клетки. Цикл - это замкнутая ломаная
линия, которая чередует вертикальное и горизонтальное направления и проходит
только по базисным клеткам. В исходной клетке поставить « + » и далее по циклу
расставить, чередуя, « + » и « - »;
- вычислить λ= min{Xij : «-»}. Клетку, на которой
достигается этот минимум, убрать из базиса (только одну), а клетку (i; j) (у
которой минимальная оценка sij) сделать базисной;
- нарисовать новую таблицу, с пересчитанным планом перевозок:
для клеток с « + » прибавить к Xij а для клеток с « - » - вычесть. Остальные клетки остаются
как были. Пересчитать целевую функцию: z′ = z + min Sij*
λ;
- перейти на шаг 4.
7. Конец алгоритма.
Пример. От трех поставщиков A1, A2 и A3
необходимо перевезти некий однородный груз трем потребителям B1, B2,
B3. Известны запасы груза поставщиков {a1,a2,a3}
и потребности потребителя {b1,b2,b3,}. Кроме
того, известна стоимость перевозки cij от любого поставщика Ai
каждому потребителю Bj - эти стоимости заданы в виде матрицы С
размерности 3 x 3. Требуется составить такой план перевозки груза от
поставщиков к потребителям, при котором суммарная стоимость перевозки была бы
минимальной.
Стоимость доставки единицы груза из каждого пункта отправления в
соответствующие пункты назначения задана матрицей тарифов (см. Таблица 2).
Проверим необходимое и достаточное условие разрешимости задачи (формулы
2,3 и 4):
1) 
=950+50+1000=2000;
2) 
=250+1000+750=2000.
Условие баланса соблюдается. Запасы равны потребностям. Следовательно,
модель транспортной задачи является закрытой.
Рассчитываем начальный план перевозок методом «Северо-Западного угла» и
получаем план, указанный в таблице 3.
Таблица 3 - Начальный опорный план
|
1
|
2
|
3
|
|
1
|
250
|
700
|
0
|
|
2
|
0
|
50
|
0
|
|
3
|
0
|
250
|
750
|
Далее находим предварительные потенциалы по формуле (7), предполагая что u1=0:
ui+vj=cij
1) u1 + v1 = 12; 0 + v1 =
12; v1 = 12;
2) u1 + v2 = 16; 0 + v2
= 16; v2 = 16;
) u2 + v2 = 4; 16 + u2
= 4; u2 = -12;
) u3 + v3 = 14; -8 + v3
= 14; v3 = 22.
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых: ui + vj > cij:
(1;3): 0 + 22 > 21; ∆13 = 0 + 22 - 21 = 1;
(2;3): -12 + 22 > 9; ∆23 = -12 + 22 - 9 = 1;
(3;1): -8 + 12 > 3; ∆31 = -8 + 12 - 3 = 1;(1,1,1) =
1.
Выбираем максимальную оценку свободной клетки (1;3): 21.
Для этого в перспективную клетку (1;3) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
Полученный цикл приведен в таблице 4.
Таблица 4
- Цикл перспективной
клетки
|
1
|
2
|
3
|
Запасы
|
|
1
|
12[250]
|
16[700][-]
|
21[+]
|
950
|
|
2
|
4
|
4[50]
|
9
|
50
|
|
3
|
3
|
8[250][+]
|
14[750][-]
|
1000
|
|
Потребности
|
250
|
1000
|
750
|
|
Из грузов хij стоящих в минусовых клетках, выбираем
наименьшее, т.е. у = min (1, 2) = 700. Прибавляем 700 к объемам грузов, стоящих
в плюсовых клетках и вычитаем 700 из Хij, стоящих в минусовых
клетках. В результате получим новый опорный план (таблица 5).
Таблица 5 - Новый опорный план
|
1
|
2
|
3
|
Запасы
|
|
1
|
12[250]
|
16
|
21[700]
|
950
|
|
2
|
4
|
4[50]
|
9
|
50
|
|
3
|
3
|
8[950]
|
14[50]
|
1000
|
|
Потребности
|
250
|
1000
|
750
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vj. по занятым клеткам таблицы, в которых ui
+ vj = cij, полагая, что u1 = 0:
1) u1 + v1 = 12; 0 + v1 =
12; v1 = 12;
2) u1 + v3 = 21; 0 + v3
= 21; v3 = 21;
) u3 + v3 = 14; 21 + u3
= 14; u3 = -7;
4) u3 + v2 = 8; -7 + v2
= 8; v2 = 15;
5) u2 + v2 = 4; 15 + u2
= 4; u2 = -11.
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vj > cij:
(2;3): -11 + 21 > 9; ∆23 = -11 + 21 - 9 = 1;
(3;1): -7 + 12 > 3; ∆31 = -7 + 12 - 3 = 2(1,2) = 2.
Выбираем максимальную оценку свободной клетки (3;1): 3
Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
Полученный цикл приведен в таблице 6.
Таблица 6 - Цикл перспективной клетки
|
1
|
3
|
Запасы
|
|
1
|
12[250][-]
|
16
|
21[700][+]
|
950
|
|
2
|
4
|
4[50]
|
9
|
50
|
|
3
|
3[+]
|
8[950]
|
14[50][-]
|
1000
|
|
Потребности
|
250
|
1000
|
750
|
|
Из грузов хij стоящих в минусовых клетках, выбираем
наименьшее, т.е. у = min (3, 3) = 50. Прибавляем 50 к объемам грузов, стоящих в
плюсовых клетках и вычитаем 50 из Хij, стоящих в минусовых клетках.
В результате получим новый опорный план (таблица 7).
Таблица 7 - Новый опорный план
|
1
|
2
|
3
|
Запасы
|
|
1
|
12[200]
|
16
|
21[750]
|
950
|
|
2
|
4
|
4[50]
|
9
|
50
|
|
3
|
3[50]
|
8[950]
|
14
|
1000
|
|
Потребности
|
250
|
1000
|
750
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vj. по занятым клеткам таблицы, в которых ui
+ vj = cij, полагая, что u1 = 0.
1 + v1 = 12; 0 + v1 = 12; v1
= 123 + v1 = 3; 12 + u3 = 3; u3 =
-93 + v2 = 8; -9 + v2 = 8; v2 = 172 + v2 = 4; 17 + u2 = 4; u2 = -13
u1 + v3 = 21; 0 + v3 = 21; v3 = 21
Опорный план не является оптимальным, так как существуют оценки свободных
клеток, для которых ui + vj > cij
(1;2): 0 + 17 > 16; ∆12 = 0 + 17 - 16 = 1
Выбираем максимальную оценку свободной клетки (1;2): 16
Для этого в перспективную клетку (1;2) поставим знак «+», а в остальных
вершинах многоугольника чередующиеся знаки «-», «+», «-».
Полученный цикл приведен в таблице 8.
Таблица 8 - Цикл перспективной клетки
|
1
|
2
|
3
|
Запасы
|
|
1
|
12[200][-]
|
16[+]
|
21[750]
|
950
|
|
2
|
4
|
4[50]
|
9
|
50
|
|
3
|
8[950][-]
|
14
|
1000
|
|
Потребности
|
250
|
1000
|
750
|
|
Из грузов хij стоящих в минусовых клетках, выбираем
наименьшее, т.е. у = min (1, 1) = 200. Прибавляем 200 к объемам грузов, стоящих
в плюсовых клетках и вычитаем 200 из Хij, стоящих в минусовых
клетках. В результате получим новый опорный план (таблица 9).
Таблица 9 - Новый опорный план
|
1
|
2
|
3
|
Запасы
|
|
1
|
12
|
16[200]
|
21[750]
|
950
|
|
2
|
4
|
4[50]
|
9
|
50
|
|
3
|
3[250]
|
8[750]
|
14
|
1000
|
|
Потребности
|
250
|
1000
|
750
|
|
Проверим оптимальность опорного плана. Найдем предварительные потенциалы
ui, vj. по занятым клеткам таблицы, в которых ui
+ vj = cij, полагая, что u1 = 0.
1 + v2 = 16; 0 + v2 = 16; v2
= 162 + v2 = 4; 16 + u2 = 4; u2 =
-123 + v2 = 8; 16 + u3 = 8; u3 = -83 + v1 = 3; -8 + v1 = 3; v1 = 11
u1 + v3 = 21; 0 + v3 = 21; v3 = 21
Опорный план является оптимальным, так все оценки свободных клеток
удовлетворяют условию ui + vj <= cij.
Минимальные затраты составят (формула 6):(x) = 16*200 + 21*750 + 4*50 +
3*250 + 8*750 = 25900 д.е.
.3
Структурная схема программы
Эскиз интерфейса программы по методу потенциалов представлен на рисунке
1.
Рисунок 1 - Эскиз интерфейса программы «Метод потенциалов»
Структурная схема программы представлена на рисунке 2.
Рисунок 2 - Структурная схема программы «Метод потенциалов»
2.4 Схема
взаимодействия модулей
программный модуль пользователь информация
Схема взаимодействия модулей представлена на рисунке 3
Рисунок 3 - Схема взаимодействия модулей
. Руководство
программисту
Работа программы осуществляется под управлением операционной системы Windows XP и выше. Для установки программы «Метод потенциалов» нужно
скопировать файлы с носителя информации в один каталог.
Файлы с расширением *.pas содержат описания процедур и функций, которые
работают в программе, т.е. содержат код программы; файлы с расширением *.dfm
содержат параметры рабочих форм; файлы с расширением *.dpr - содержат общее описание проекта; файлы с
расширением *.dcu - содержат результаты преобразования
в машинной инструкции текста из предыдущих типов файла. Текст программы
находится в приложении А.
Для работы с программой нужно запустить MofP.exe
файл.
Для модификации программы, системный программист должен иметь программный
пакет. Это файлы модуля *.pas,
файл программы *.dpr и другие файлы
описаний. Модифицировать программу можно в информационной среде разработки
приложений Delphi 7.
Отладка программы - это сложный и нестандартный процесс. Исходный план
отладки заключается в том, чтобы оттестировать программу на контрольных
примерах.
Для предотвращения этого или для устранения неисправностей в программе,
(если это связано с отсутствием файлов), необходимо правильно указать путь
доступа к файлам.
Программа содержит 3
модуля:
·
форма Resh - главная форма программы, содержит
в себе кнопки «Решение», «Справка», и «Пример»;
·
форма priv - форма приветствия с кратким
описанием возможности программы;
·
форма Sprav - форма просмотра ознакомительной
информации, содержит информацию о методе и информацию о разработчике.
. Руководство
пользователю
4.1 Общие
сведения
Большинство программных продуктов, особенно прикладного характера,
ориентированных на конечного пользователя, работают в диалоговом режиме,
взаимодействуя с пользователем таким образом, что ведется обмен сообщениями,
влияющими на обработку данных.
Для запуска программы необходимо запустить файл MofP.exe.
На экране появится форма приветствия, на котором находится краткое описание
возможностей программы и кнопка «ОК» позволяющая нам начать работать с данной
программой.
При нажатии на кнопку «ОК» появляется форма для ввода условий задачи:
- таблица;
- комбинированные списки для ввода размерности таблицы;
- кнопки «Решение», «Пример» и «Справка»
Для того, чтобы начать работу нужно выбрать размерность таблицы и
заполнить ее (ввод разрешен только для целых чисел). Для демонстрации работы
программы можно нажать кнопку пример, после чего таблица заполнится
автоматически.
После нажатия на кнопку «Решение», будет рассчитан начальный опорный план
и стоимость перевозов, а в соседней таблице - конечный опорный план и стоимость
перевозов оптимального плана. После этого программа выдаст сообщение о
сравнении начального и оптимизированного планов.
При нажатии на кнопку помощь можно увидеть информацию о разработчике, о
программе, а также просмотреть алгоритм решения «Метода потенциалов».
.2 Работа с
помощью
Для вывода информации о методе решения в программном продукте, необходимо
воспользоваться кнопкой «Справка» и выбрать страницу « О методе». Для вывода
информации о разработчике программы, необходимо нажать на кнопку «Справка» и
выбрать страницу «О разработчике», а также можно увидеть сведения о программе
выбрав вкладку «О программе».
4.3 Наиболее
вероятные ошибки
Наиболее вероятной ошибкой является ошибка преобразования, которая
возникает в случаях некорректного заполнения данных, либо их не заполнение
(рисунок 4 и 5).
Так же выводится предупреждение в том случае, если данная задача имеет
открытый тип (рисунок 6).
Рисунок 4 - Ошибка ввода размерности таблицы
Рисунок 6 - Предупреждение о недопустимом типе задачи
Заключение
Во время разработки курсового проекта были закреплены знания по работе в
интегрированной объектно-ориентированной среде программирования Delphi 7.0. При создании программного
продукта были учтены множество факторов, позволяющих облегчить работу
пользователям.
В результате выполнения курсового проекта был освоен метод оптимизации
решения транспортной задачи «Методом потенциалов», разработан программный
продукт по решению данного метода, следовательно, поставленные цели достигнуты
и задачи выполнены.
Список
использованных источников
1
Агальцов, В.П.
Математические методы в программировании: учебник /В.П. Агальцова, -М.: 2006.
-244 с.
2
Бондарев В.М.,
Рублинецкий В.И., Качко Е.Г. Основы программирования / Худож. - оформитель С.А.
Пяткова. - Харьков:Фолто; Ростов н/Д: Феникс, 1998, - 368с.
3
Голованов М.
Создание компонентов в среде Delphi:
учеб.пособие. И. Халдин. Вильямс, 2006.- 768 с.
4
Партыка, Т.Л.
Математические методы: учебник /Т.Л. Партыка, -М.: 2005. -464 с.
5
Хомоненко А.И.,
Гофман В.П., Мещеряков Е.В, Никифоров В.Г.: учебник Delphi 7 в подлиннике. - СПб: БХВ-Петербург, 2004. - 1216 c.
Приложение А
Текст программы
program MofP;
uses,in 'Resh.pas' {Form1},in 'Privet.pas' {Form2},in
'Sprav.pas' {Form3};
{$R *.res}.Initialize;.CreateForm(TForm2,
Form2);.CreateForm(TForm1, Form1);.CreateForm(TForm3, Form3);.Run;.Privet;,
Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,, StdCtrls,
ExtCtrls, Buttons;= class(TForm): TImage;: TLabel;: TLabel;: TLabel;: TLabel;:
TLabel;: TLabel;: TLabel;: TLabel;: TBitBtn;BitBtn1Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm2;Resh;
{$R *.dfm}TForm2.BitBtn1Click(Sender:
TObject);.show;.Hide;;.Sprav;, Messages, SysUtils, Variants, Classes, Graphics,
Controls, Forms,, OleCtrls, SHDocVw, StdCtrls, ComCtrls;= class(TForm):
TPageControl;: TTabSheet;: TTabSheet;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;:
TWebBrowser;: TTabSheet;: TWebBrowser;
{ Private declarations }
{ Public declarations };: TForm3;
{$R *.dfm}.Resh;, Messages, SysUtils, Variants, Classes,
Graphics, Controls, Forms,, StdCtrls, Grids, Buttons, ExtCtrls;= class(TForm):
TStringGrid;: TStringGrid;: TStringGrid;: TStringGrid;: TStringGrid;: TLabel;:
TPanel;: TGroupBox;: TLabel;: TLabel;: TComboBox;: TComboBox;: TStringGrid;:
TButton;: TButton;: TLabel;: TLabel;: TLabel;: TLabel;: TLabel;: TBitBtn;:
TButton;Button1Click(Sender: TObject);FormCreate(Sender:
TObject);Button2Click(Sender: TObject);CB1Change(Sender:
TObject);CB2Change(Sender: TObject);FormClose(Sender: TObject; var Action:
TCloseAction);Button4Click(Sender: TObject);BitBtn1Click(Sender: TObject);
{ Private declarations }
{ Public declarations };: TForm1;,x,delta:array [1..10,1..10]
of real; Potr,beta:array[1..10] of real;
Zapas,alfa: array[1..10] of real; z,p:integer; //z-количество пунктов с
запасами,p - с потребностями
zapol:array [1..10,1..10] of Boolean;:Boolean; // Флаг окончания итерацийPrivet, Sprav;
{$R *.dfm}
//распределение ресурсов начального плана происходит методом
северо-западного угла
Procedure Naxod_Poten;i,j:integer;:boolean;i:=1 to z do
alfa[i]:=-MaxInt; // т.е все альфы не известныj:=1 to p do
beta[j]:=-MaxInt; // т.е все бэты не известны[1]:=0;i:=1 to z doj:=1 to
p dozapol[i,j] then(alfa[i]=-MaxInt)and(beta[j]<>-MaxInt) then
alfa[i]:=beta[j]-c[i,j]if (alfa[i]<>-MaxInt)and(beta[j]=-MaxInt) then
beta[j]:=c[i,j]+alfa[i];;:=True;i:=1 to z do if alfa[i]=-MaxInt then
vix:=False;j:=1 to p do if beta[j]=-MaxInt then
vix:=False;vix;;Naxod_delta;i,j:integer;i:=1 to z doj:=1 to p
do[i,j]:=beta[j]-alfa[i]-c[i,j];;;Naxod_Plan;i,j,sv_i,sv_j,i_tek,j_tek,i_min,j_min:integer;,min:real;:array
[1..10,1..10] of integer;_v_stolbce:array[1..10] of integer;_v_stroke:
array[1..10] of integer;:array [1..10,1..10] of Boolean;Init_cikl; //подпрограмма в процедуреi,j:integer;i:=1 to z doj:=1 to p do[i,j]:=0;
// найдем количество заполненых ячеек в строках и столбцах
for i:=1 to z do kol_v_stroke[i]:=0;j:=1 to p do
kol_v_stolbce[j]:=0;i:=1 to z doj:=1 to p dozapol1[i,j]
then_v_stroke[i]:=kol_v_stroke[i]+1;_v_stolbce[j]:=kol_v_stolbce[j]+1;;_tek:=sv_i;_tek:=sv_j;[i_tek,j_tek]:=1;;:=0;i:=1
to z doj:=1 to p do(delta[i,j]>max)and (Not(zapol[i,j])) then:=
delta[i,j];_i:=i; sv_j:=j;
//Клетка (sv_i,sv_j) - новая
заполняемая клетка;max=0 then // если не положительных дельта
begin:=True;;i:=1 to z doj:=1 to p do // переписываем матрицу
заполнения[i,j]:=zapol[i,j];
// Теперь найдем цикл_cikl;
Repeat
// переход по столбцуi:=1 to z do(i<>i_tek)and
zapol1[i,j_tek] then_tek:=i;[i_tek,j_tek]:=-1;;;i_tek=sv_i then break;
// переход по строкеj:=1 to p do
if (j<>j_tek)and zapol1[i_tek,j]
then_tek:=j;[i_tek,j_tek]:=1;;;kol_v_stolbce[j_tek]<2 then // если зашли в тупик[i_tek,j_tek]:=False; // убираем последнюю ячейку_cikl; // и начинаем сначала
end;kol_v_stroke[i_tek]<2 then // если зашли в тупик[i_tek,j_tek]:=False; // убираем последнюю ячейку_cikl; // и начинаем сначала;False;
// По матрице знаков находим минимальный элемент
min:=MaxInt; // заведомо большее числоi:=1 to z doj:=1 to p do(znaki[i,j]=-1)and(x[i,j]<min)
then:=x[i,j];_min:=i; j_min:=j;
end;
//Переходим к новому плану[i_min,j_min]:=False;
zapol[sv_i,sv_j]:=True;i:=1 to z doj:=1 to p
do[i,j]:=x[i,j]+znaki[i,j]*min;;Updat;i,j:integer;Form1 doi:=1 to z doj:=1 to p
do.Cells[j,i]:=FloatToStr(x[i,j]);;;TForm1.Button1Click(Sender:
TObject);i,j,shag:integer;,sum_zap,sum_potr:real;_nac:integer;i:=1 to
StringGrid1.ColCount-2 doj:=1 to StringGrid1.RowCount-2
do.Cells[i,j]:=StringGrid1.Cells[i,j];j:=0 to StringGrid1.RowCount-1
do.Cells[0,j]:=StringGrid1.Cells[StringGrid1.ColCount-1,j];i:=0 to
StringGrid1.RowCount-1
do.Cells[i,0]:=StringGrid1.Cells[i,StringGrid1.RowCount-1];:=StringGrid1.ColCount-2;:=StringGrid1.RowCount-2;:=False;i:=1
to z doj:=1 to p do
C[j,i]:=StrToFloat(sgIsx.Cells[i,j]);[i]:=StrToFloat(sgZap.Cells[0,i]);;j:=1 to
p do Potr[j]:=StrToFloat(sgPotr.Cells[j,0]);_zap:=0;_potr:=0;i:=1 to z do
sum_zap:=sum_zap+zapas[i];j:=1 to p do
sum_potr:=sum_potr+Potr[j];sum_zap<>sum_potr then messagebox(handle,'Сумма потребностей не равна сумме запасов','Ошибка',mb_OK+mb_iconstop).Cells[StringGrid1.colcount-1,StringGrid1.Rowcount-1]:=FloatToStr(sum_Zap);.RowCount:=z+1;.RowCount:=z+1;.ColCount:=p+1;.ColCount:=p+1;i:=1
to z doj:=1 to p do[i,j]:=0;[i,j]:=False;
end;
// Начальное заполнение - метод северо-западного угла
i:=1;j:=1;Zapas[i]>Potr[j]
then[i,j]:=Potr[j];[j]:=0;[i]:=Zapas[i]-x[i,j];[i,j]:=Zapas[i];[i]:=0;[j]:=Potr[j]-x[i,j];;[i,j]:=True;
if Potr[j]=0 then j:=j+1 // ??реход к след. клетке
else i:=i+1;(i>z) or (j>p);i:=1 to z doj:=1 to p do
sgNac.Cells[j,i]:=FloatToStr(x[i,j]);
// Основной цикл:=0;:=shag+1;_Poten;_delta;_Plan;;
// найдем значение целевой функции:=0;
For i:=1 to z doj:=1 to p do:=f+x[i,j]*c[i,j];zakon then
break;.Caption:=FloatToStr(f);False;_nac:=0;i:=1 to sgNac.ColCount-1 doj:=1 to
sgNac.RowCount-1 dosgNac.Cells[i,j]<>'0'
then_nac:=z_nac+(StrToInt(sgNac.Cells[i,j])*StrToInt(sgisx.cells[i,j]));.Caption:=IntToStr(z_nac);Z_nac>f
then messageDlg('Транспортная задача
закрытого типа'+#10#13
+' План оптимизирован!',mtInformation,[mbOK],0);;on EConvertError do MessageDlg('Заполните таблицу!'+#10#13+'Правая нижняя клетка не заполняется',MTError,[mbOK],0);;;TForm1.FormCreate(Sender:
TObject);i,j:integer;.show;i:=1 to StringGrid1.ColCount-2 do
StringGrid1.Cells[i,0]:='B'+IntToStr(i);j:=1 to StringGrid1.RowCount-2 do
StringGrid1.Cells[0,j]:='A'+IntToStr(j);.Cells[StringGrid1.ColCount-1,0]:='Запасы';.Cells[0,StringGrid1.RowCount-1]:='Потребности';;TForm1.Button2Click(Sender:
TObject);i,j:integer;.Enabled:=true;.ColCount:=StrToInt(CB2.Text)+2;.RowCount:=StrToInt(CB1.Text)+2;i:=1
to StringGrid1.ColCount-2 do StringGrid1.Cells[i,0]:='B'+IntToStr(i);j:=1 to
StringGrid1.RowCount-2 do
StringGrid1.Cells[0,j]:='A'+IntToStr(j);.Cells[StringGrid1.ColCount-1,0]:='Запасы';.Cells[0,StringGrid1.RowCount-1]:='Потребности';i:=1 to StringGrid1.ColCount-2
doj:=1 to StringGrid1.RowCount-2 do.Cells[i,j]:=StringGrid1.Cells[i,j];j:=0 to StringGrid1.RowCount-1
do.Cells[0,j]:=StringGrid1.Cells[StringGrid1.ColCount-1,j];i:=0 to
StringGrid1.RowCount-1
do.Cells[i,0]:=StringGrid1.Cells[i,StringGrid1.RowCount-1];.ColCount:=StringGrid1.ColCount-1;.RowCount:=StringGrid1.RowCount-1;.ColCount:=sgIsx.ColCount;.ColCount:=sgIsx.ColCount;.RowCount:=sgIsx.RowCount;.RowCount:=sgIsx.RowCount;.RowCount:=sgIsx.RowCount;.RowCount:=sgIsx.RowCount;.ColCount:=sgIsx.ColCount;.ColCount:=sgIsx.ColCount;on
EConvertError do MessageDlg('Выберите размерность матрицы!',MTError,[mbOK],0);;;TForm1.CB1Change(Sender:
TObject);.Text:=CB1.Text;;TForm1.CB2Change(Sender:
TObject);.Text:=CB2.Text;;TForm1.FormClose(Sender: TObject; var Action:
TCloseAction);.Close;;TForm1.Button4Click(Sender:
TObject);.ItemIndex:=1;.ItemIndex:=1;.Click;.Cells[1,1]:='12';.Cells[2,1]:='16';.Cells[3,1]:='21';.Cells[1,2]:='4';.Cells[2,2]:='4';.Cells[3,2]:='9';.Cells[1,3]:='3';.Cells[2,3]:='8';.Cells[3,3]:='14';.Cells[4,1]:='950';.Cells[4,2]:='50';.Cells[4,3]:='1000';
StringGrid1.Cells[1,4]:='250';
StringGrid1.Cells[2,4]:='1000';.Cells[3,4]:='750';;TForm1.BitBtn1Click(Sender:
TObject);.show;.WebBrowser1.Navigate(extractFilepath(paramstr(0))+'help.mht');.WebBrowser2.Navigate(ExtractFilePath(paramstr(0))+'prog.mht');
end;.
Приложение Б
Формы программы
Рисунок 5 - Форма «Приветствие»
Рисунок 6 - Форма «Метод потенциалов»
Рисунок 7 - Форма «Справка»