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

Содержание

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

1.1 Требования к системе и ее структуре

1.2 Требования к функциям, выполняемым системой

1.3 Требования к программно-аппаратному обеспечению

1.4 Требования к техническому обеспечению

1.6 Требования к надежности и хранению информации

2. Основная часть

2.1 Математическая модель

2.3 Метод решения задачи

2.3 Структурная схема программы

2.4 Схема взаимодействия модулей

3. Руководство программисту

4 Руководство пользователю

4.1 Общие сведения

4.2 Работа с помощью

4.3 Наиболее вероятные ошибки

Заключение

Список использованных источников

Приложение А Текст программы

Приложение Б Формы программы

Приложение В Диск с программой



Введение

Данный курсовой проект выполнен на тему «Решение транспортной задачи методом потенциалов».

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

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

Для достижения поставленной цели необходимо решение следующих задач:

1) изучение теоретического материала по теме работы;

2) рассмотрение метода потенциалов;

3) создание ПП;

4) описание создания программного продукта по теме работы.



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

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

К основным характеристикам функциональных задач, уточняемых в процессе формализованной постановки, относят:

1) цель и назначение задачи, её место и связь с другими задачами: целью разработки программного продукта является автоматическое решение транспортных задач «методом потенциалов»;

2) условия решения задачи с использованием средств вычислительной техники:

- процессор: AMD Turion™ II Dual-Core M500 2.20 GHz и выше;

- полный объём физической памяти: 512,00 МБ и выше;

- виртуальная память: 2,00 ГБ;

- операционная система Microsoft Windows XP / Seven;

- видео карта 216 Мб;

- клавиатура;

- мышь;

3) содержание функций обработки входной информации для решения задачи: ввод данных, проверка корректности данных, сохранение;

4) требование к периодичности решения задачи: по требованию;

5) ограничение по срокам и точности выходной информации: вывод интересующей информации происходит сразу после обработки запроса пользователя;

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

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

8) пользователи задачи: программа предназначается для использования ее пользователями, нуждающимися в решение подобного рода задач.

1.1 Требования к системе и ее структуре

Для полноценной работы программы необходимо наличие следующего программного обеспечения:

операционная система Windows 7;

Borland Delphi 7.0.

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

1.2 Требования к функциям, выполняемым системой

Функции, которые осуществляет система, должны придерживаться следующих правил:

- универсальные системы;

- поддержка безошибочной и корректной работы своих функций;

- поддержка стандартов той операционной системы, в которой работает программа;

- корректировка различных данных;

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

1.3 Требования к программно-аппаратному обеспечению

Для корректной работы с данным программным продуктом необходимы следующие требования:

- операционная система Microsoft Windows XP / Seven;

- процессор семейства Intel или AMD с тактовой частотой от 1 ГГц;

- видео карта 216 Мб;

- свободное место на жестком диске более 10 Мб.

1.4 Требования к техническому обеспечению

Для использования данного программного продукта необходимо следующее техническое обеспечение:

ОЗУ не менее 512 Мб;

клавиатура;

мышь;

монитор.

1.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=)

B_j - потребители груза (j=)

a_i - запасы груза (i=)

b_J - потребители в грузе (j=)

c_ij - стоимость (тариф) каждой перевозки (i=, j=)

x_ij - количество распределенного товара от i-го поставщика j-му потребителю(i=, j=).

Если в транспортной задаче выполняется условие формулы (1), то транспортная задача называется закрытой, иначе - открытой.

Для написания модели необходимо все ограничения и целевую функцию представить в виде математических уравнений (формулы 2, 3, 4, 5 и 6).

(i=);

(j=);

x_ij ? 0 (i=;j=);

.

Методами отыскания начального плана (опорного решения) для решения транспортной задачи являются:

1. метод «северо-западного угла»;

2. метод минимального элемента;

3. метод Фогеля.

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



2.3 Метод решения задачи

Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.

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

Таблица для метода потенциалов (таблица 2) имеет следующий вид:

Таблица 2 - Вид таблицы метода потенциалов

	B1 …	Bj	… Bn	U
A1 …				U1 …
Aj		Cij Xij		Ui
Am …				Um …
v	v1 …	vj	… vn	Z

Каждая ячейка (i; j) таблицы хранит информацию о цене (С_ij) и о количестве перевозимого товара (X_ij). В процессе решения задачи часть клеток будем называть базисными, а остальные -- небазисными (или свободными).

Алгоритм решения.

1. Замкнуть задачу, если она не замкнута. Перейти на шаг 2.

2. Нарисовать начальную таблицу. Перейти на шаг 3.

3. Рассчитать начальный план перевозок (например, методом северо-западного угла) и выделить базисные клетки. Вычислить значение целевой функции. Перейти на шаг 4.

4. Рассчитать значения потенциалов. Положить u1 = 0 (или любому другому числу). Остальные потенциалы рассчитать с помощью базисных клеток, исходя из уравнения ui + vj = cij. Перейти на шаг 5.

5. Для свободных клеток рассчитать оценки sij = cij - vi - vj. Если все sij > 0, то найдено оптимальное решение. Перейти на шаг 5. Иначе выполнить шаг 6.

6. Из небазисных клеток выбрать ту, у которой оценка sij минимальна и для нее выполнить следующую процедуру:

- построить цикл для этой клетки. Цикл -- это замкнутая ломаная линия, которая чередует вертикальное и горизонтальное направления и проходит только по базисным клеткам. В исходной клетке поставить « + » и далее по циклу расставить, чередуя, « + » и « - »;

- вычислить л= min{X_ij : «-»}. Клетку, на которой достигается этот минимум, убрать из базиса (только одну), а клетку (i; j) (у которой минимальная оценка sij) сделать базисной;

- нарисовать новую таблицу, с пересчитанным планом перевозок: для клеток с « + » прибавить к X_ij а для клеток с « - » -- вычесть. Остальные клетки остаются как были. Пересчитать целевую функцию: z? = z + min S_ij* л;

- перейти на шаг 4.

7. Конец алгоритма.

Пример. От трех поставщиков A₁, A₂ и A₃ необходимо перевезти некий однородный груз трем потребителям B₁, B₂, B₃. Известны запасы груза поставщиков {a₁,a₂,a₃} и потребности потребителя {b₁,b₂,b₃,}. Кроме того, известна стоимость перевозки c_ij от любого поставщика A_i каждому потребителю B_j - эти стоимости заданы в виде матрицы С размерности 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), предполагая что u₁=0:

u_i+v_j=c_ij

1) u₁ + v₁ = 12; 0 + v₁ = 12; v₁ = 12;

2) u₁ + v₂ = 16; 0 + v₂ = 16; v₂ = 16;

3) u₂ + v₂ = 4; 16 + u₂ = 4; u₂ = -12;

4) u₃ + v₂ = 8; 16 + u₃ = 8; u₃ = -8;

5) u₃ + v₃ = 14; -8 + v₃ = 14; v₃ = 22.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых: u_i + v_j > c_ij:

(1;3): 0 + 22 > 21; ?₁₃ = 0 + 22 - 21 = 1;

(2;3): -12 + 22 > 9; ?₂₃ = -12 + 22 - 9 = 1;

(3;1): -8 + 12 > 3; ?₃₁ = -8 + 12 - 3 = 1;

max(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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0:

1) u₁ + v₁ = 12; 0 + v₁ = 12; v₁ = 12;

2) u₁ + v₃ = 21; 0 + v₃ = 21; v₃ = 21;

3) u₃ + v₃ = 14; 21 + u₃ = 14; u₃ = -7;

4) u₃ + v₂ = 8; -7 + v₂ = 8; v₂ = 15;

5) u₂ + v₂ = 4; 15 + u₂ = 4; u₂ = -11.

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij:

(2;3): -11 + 21 > 9; ?₂₃ = -11 + 21 - 9 = 1;

(3;1): -7 + 12 > 3; ?₃₁ = -7 + 12 - 3 = 2

max(1,2) = 2.

Выбираем максимальную оценку свободной клетки (3;1): 3

Для этого в перспективную клетку (3;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

Полученный цикл приведен в таблице 6.

Таблица 6 - Цикл перспективной клетки

	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

Из грузов х_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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₁ = 12; 0 + v₁ = 12; v₁ = 12

u₃ + v₁ = 3; 12 + u₃ = 3; u₃ = -9

u₃ + v₂ = 8; -9 + v₂ = 8; v₂ = 17

u₂ + v₂ = 4; 17 + u₂ = 4; u₂ = -13

u₁ + v₃ = 21; 0 + v₃ = 21; v₃ = 21

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_j > c_ij

(1;2): 0 + 17 > 16; ?₁₂ = 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	3[50][+]	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

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_j. по занятым клеткам таблицы, в которых u_i + v_j = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 16; 0 + v₂ = 16; v₂ = 16

u₂ + v₂ = 4; 16 + u₂ = 4; u₂ = -12

u₃ + v₂ = 8; 16 + u₃ = 8; u₃ = -8

u₃ + v₁ = 3; -8 + v₁ = 3; v₁ = 11

u₁ + v₃ = 21; 0 + v₃ = 21; v₃ = 21

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_j <= c_ij.

Минимальные затраты составят (формула 6):

F(x) = 16*200 + 21*750 + 4*50 + 3*250 + 8*750 = 25900 д.е.

2.3 Структурная схема программы

Эскиз интерфейса программы по методу потенциалов представлен на рисунке 1.

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

Рисунок 1 - Эскиз интерфейса программы «Метод потенциалов»



Структурная схема программы представлена на рисунке 2.

Рисунок 2 - Структурная схема программы «Метод потенциалов»

2.4 Схема взаимодействия модулей

программный модуль пользователь информация

Схема взаимодействия модулей представлена на рисунке 3

Рисунок 3 - Схема взаимодействия модулей



3. Руководство программисту

Работа программы осуществляется под управлением операционной системы Windows XP и выше. Для установки программы «Метод потенциалов» нужно скопировать файлы с носителя информации в один каталог.

Файлы с расширением *.pas содержат описания процедур и функций, которые работают в программе, т.е. содержат код программы; файлы с расширением *.dfm содержат параметры рабочих форм; файлы с расширением *.dpr - содержат общее описание проекта; файлы с расширением *.dcu - содержат результаты преобразования в машинной инструкции текста из предыдущих типов файла. Текст программы находится в приложении А.

Для работы с программой нужно запустить MofP.exe файл.

Для модификации программы, системный программист должен иметь программный пакет. Это файлы модуля *.pas, файл программы *.dpr и другие файлы описаний. Модифицировать программу можно в информационной среде разработки приложений Delphi 7.

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

Для предотвращения этого или для устранения неисправностей в программе, (если это связано с отсутствием файлов), необходимо правильно указать путь доступа к файлам.

Программа содержит 3 модуля:

форма Resh - главная форма программы, содержит в себе кнопки «Решение», «Справка», и «Пример»;

форма priv - форма приветствия с кратким описанием возможности программы;

форма Sprav - форма просмотра ознакомительной информации, содержит информацию о методе и информацию о разработчике.



4. Руководство пользователю

4.1 Общие сведения

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

Для запуска программы необходимо запустить файл MofP.exe. На экране появится форма приветствия, на котором находится краткое описание возможностей программы и кнопка «ОК» позволяющая нам начать работать с данной программой.

При нажатии на кнопку «ОК» появляется форма для ввода условий задачи:

- таблица;

- комбинированные списки для ввода размерности таблицы;

- кнопки «Решение», «Пример» и «Справка»

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

После нажатия на кнопку «Решение», будет рассчитан начальный опорный план и стоимость перевозов, а в соседней таблице - конечный опорный план и стоимость перевозов оптимального плана. После этого программа выдаст сообщение о сравнении начального и оптимизированного планов.

При нажатии на кнопку помощь можно увидеть информацию о разработчике, о программе, а также просмотреть алгоритм решения «Метода потенциалов».



4.2 Работа с помощью

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

4.3 Наиболее вероятные ошибки

Наиболее вероятной ошибкой является ошибка преобразования, которая возникает в случаях некорректного заполнения данных, либо их не заполнение (рисунок 4 и 5).

Так же выводится предупреждение в том случае, если данная задача имеет открытый тип (рисунок 6).

Рисунок 4 - Ошибка ввода размерности таблицы

Рисунок 5 - Ошибка ввода данных в таблицу



Рисунок 6 - Предупреждение о недопустимом типе задачи



Заключение

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

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



Список использованных источников

Агальцов, В.П. Математические методы в программировании: учебник /В.П. Агальцова, -М.: 2006. -244 с.

Бондарев В.М., Рублинецкий В.И., Качко Е.Г. Основы программирования / Худож. - оформитель С.А. Пяткова. - Харьков:Фолто; Ростов н/Д: Феникс, 1998, - 368с.

Голованов М. Создание компонентов в среде Delphi: учеб.пособие. И. Халдин. Вильямс, 2006.- 768 с.

Партыка, Т.Л. Математические методы: учебник /Т.Л. Партыка, -М.: 2005. -464 с.

Хомоненко А.И., Гофман В.П., Мещеряков Е.В, Никифоров В.Г.: учебник Delphi 7 в подлиннике. - СПб: БХВ-Петербург, 2004. - 1216 c.



Приложение А

Текст программы

program MofP;

uses

Forms,

Resh in 'Resh.pas' {Form1},

Privet in 'Privet.pas' {Form2},

Sprav in 'Sprav.pas' {Form3};

{$R *.res}

begin

Application.Initialize;

Application.CreateForm(TForm2, Form2);

Application.CreateForm(TForm1, Form1);

Application.CreateForm(TForm3, Form3);

Application.Run;

end.

unit Privet;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, Buttons;

type

TForm2 = class(TForm)

Image1: TImage;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label5: TLabel;

Label6: TLabel;

Label7: TLabel;

Label8: TLabel;

Label9: TLabel;

BitBtn1: TBitBtn;

procedure BitBtn1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form2: TForm2;

implementation

uses Resh;

{$R *.dfm}

procedure TForm2.BitBtn1Click(Sender: TObject);

begin

form1.show;

form2.Hide;

end;

end.

unit Sprav;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, OleCtrls, SHDocVw, StdCtrls, ComCtrls;

type

TForm3 = class(TForm)

PageControl1: TPageControl;

TabSheet1: TTabSheet;

TabSheet2: TTabSheet;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

WebBrowser1: TWebBrowser;

TabSheet3: TTabSheet;

WebBrowser2: TWebBrowser;

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form3: TForm3;

implementation

{$R *.dfm}

end.

unit Resh;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Buttons, ExtCtrls;

type

TForm1 = class(TForm)

sgIsx: TStringGrid;

sgZap: TStringGrid;

sgPotr: TStringGrid;

sgNac: TStringGrid;

sgOpt: TStringGrid;

Label10: TLabel;

Panel2: TPanel;

GroupBox1: TGroupBox;

Label7: TLabel;

Label8: TLabel;

CB1: TComboBox;

CB2: TComboBox;

StringGrid1: TStringGrid;

Button2: TButton;

Button1: TButton;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

BitBtn1: TBitBtn;

Button4: TButton;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure CB1Change(Sender: TObject);

procedure CB2Change(Sender: TObject);

procedure FormClose(Sender: TObject; var Action: TCloseAction);

procedure Button4Click(Sender: TObject);

procedure BitBtn1Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

C,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;

zakon:Boolean; // Флаг окончания итераций

implementation

uses Privet, Sprav;

{$R *.dfm}

//распределение ресурсов начального плана происходит методом северо-западного угла

Procedure Naxod_Poten;

Var i,j:integer;

vix:boolean;

Begin

For i:=1 to z do alfa[i]:=-MaxInt; // т.е все альфы не известны

For j:=1 to p do beta[j]:=-MaxInt; // т.е все бэты не известны

Repeat

alfa[1]:=0;

For i:=1 to z do

For j:=1 to p do

Begin

If zapol[i,j] then

if (alfa[i]=-MaxInt)and(beta[j]<>-MaxInt) then alfa[i]:=beta[j]-c[i,j]

else if (alfa[i]<>-MaxInt)and(beta[j]=-MaxInt) then beta[j]:=c[i,j]+alfa[i];

End;

vix:=True;

For i:=1 to z do if alfa[i]=-MaxInt then vix:=False;

For j:=1 to p do if beta[j]=-MaxInt then vix:=False;

Until vix;

End;

Procedure Naxod_delta;

Var i,j:integer;

Begin

For i:=1 to z do

For j:=1 to p do

Begin

delta[i,j]:=beta[j]-alfa[i]-c[i,j];

End;

End;

Procedure Naxod_Plan;

var i,j,sv_i,sv_j,i_tek,j_tek,i_min,j_min:integer;

max,min:real;

znaki:array [1..10,1..10] of integer;

kol_v_stolbce:array[1..10] of integer;

kol_v_stroke: array[1..10] of integer;

zapol1:array [1..10,1..10] of Boolean;

Procedure Init_cikl; //подпрограмма в процедуре

var i,j:integer;

Begin

For i:=1 to z do

For j:=1 to p do

znaki[i,j]:=0;

// найдем количество заполненых ячеек в строках и столбцах

for i:=1 to z do kol_v_stroke[i]:=0;

For j:=1 to p do kol_v_stolbce[j]:=0;

for i:=1 to z do

For j:=1 to p do

if zapol1[i,j] then

begin

kol_v_stroke[i]:=kol_v_stroke[i]+1;

kol_v_stolbce[j]:=kol_v_stolbce[j]+1;

end;

i_tek:=sv_i;

j_tek:=sv_j;

znaki[i_tek,j_tek]:=1;

end;

Begin

max:=0;

For i:=1 to z do

For j:=1 to p do

if (delta[i,j]>max)and (Not(zapol[i,j])) then

begin

max:= delta[i,j];

sv_i:=i; sv_j:=j;

//Клетка (sv_i,sv_j) - новая заполняемая клетка

end;

if max=0 then // если не положительных дельта

begin

zakon:=True;

exit

end;

For i:=1 to z do

For j:=1 to p do // переписываем матрицу заполнения

zapol1[i,j]:=zapol[i,j];

// Теперь найдем цикл

Init_cikl;

Repeat

// переход по столбцу

for i:=1 to z do

if (i<>i_tek)and zapol1[i,j_tek] then

Begin

i_tek:=i;

znaki[i_tek,j_tek]:=-1;

break;

End;

if i_tek=sv_i then break;

// переход по строке

for j:=1 to p do

if (j<>j_tek)and zapol1[i_tek,j] then

Begin

j_tek:=j;

znaki[i_tek,j_tek]:=1;

break;

End;

if kol_v_stolbce[j_tek]<2 then // если зашли в тупик

begin

zapol1[i_tek,j_tek]:=False; // убираем последнюю ячейку

Init_cikl; // и начинаем сначала

end;

if kol_v_stroke[i_tek]<2 then // если зашли в тупик

begin

zapol1[i_tek,j_tek]:=False; // убираем последнюю ячейку

Init_cikl; // и начинаем сначала

end;

Until False;

// По матрице знаков находим минимальный элемент

min:=MaxInt; // заведомо большее число

for i:=1 to z do

for j:=1 to p do

if (znaki[i,j]=-1)and(x[i,j]<min) then

begin

min:=x[i,j];

i_min:=i; j_min:=j;

end;

//Переходим к новому плану

zapol[i_min,j_min]:=False;

zapol[sv_i,sv_j]:=True;

for i:=1 to z do

for j:=1 to p do

x[i,j]:=x[i,j]+znaki[i,j]*min;

End;

procedure Updat;

var i,j:integer;

Begin

With Form1 do

Begin

For i:=1 to z do

for j:=1 to p do

sgOpt.Cells[j,i]:=FloatToStr(x[i,j]);

end;

End;

procedure TForm1.Button1Click(Sender: TObject);

var i,j,shag:integer;

F,sum_zap,sum_potr:real;

Z_nac:integer;

begin

try

for i:=1 to StringGrid1.ColCount-2 do

for j:=1 to StringGrid1.RowCount-2 do

sgIsx.Cells[i,j]:=StringGrid1.Cells[i,j];

for j:=0 to StringGrid1.RowCount-1 do

sgZap.Cells[0,j]:=StringGrid1.Cells[StringGrid1.ColCount-1,j];

for i:=0 to StringGrid1.RowCount-1 do

sgPotr.Cells[i,0]:=StringGrid1.Cells[i,StringGrid1.RowCount-1];

z:=StringGrid1.ColCount-2;

p:=StringGrid1.RowCount-2;

zakon:=False;

For i:=1 to z do

Begin

for j:=1 to p do C[j,i]:=StrToFloat(sgIsx.Cells[i,j]);

Zapas[i]:=StrToFloat(sgZap.Cells[0,i]);

end;

For j:=1 to p do Potr[j]:=StrToFloat(sgPotr.Cells[j,0]);

sum_zap:=0;

sum_potr:=0;

For i:=1 to z do sum_zap:=sum_zap+zapas[i];

for j:=1 to p do sum_potr:=sum_potr+Potr[j];

if sum_zap<>sum_potr then messagebox(handle,'Сумма потребностей не равна сумме запасов','Ошибка',mb_OK+mb_iconstop)

else

begin

StringGrid1.Cells[StringGrid1.colcount-1,StringGrid1.Rowcount-1]:=FloatToStr(sum_Zap);

sgNac.RowCount:=z+1;

sgOpt.RowCount:=z+1;

sgNac.ColCount:=p+1;

sgOpt.ColCount:=p+1;

For i:=1 to z do

for j:=1 to p do

Begin

x[i,j]:=0;

zapol[i,j]:=False;

end;

// Начальное заполнение - метод северо-западного угла

i:=1;j:=1;

Repeat

if Zapas[i]>Potr[j] then

begin

x[i,j]:=Potr[j];

Potr[j]:=0;

Zapas[i]:=Zapas[i]-x[i,j];

end

else

begin

x[i,j]:=Zapas[i];

Zapas[i]:=0;

Potr[j]:=Potr[j]-x[i,j];

end;

Zapol[i,j]:=True;

if Potr[j]=0 then j:=j+1 // ??реход к след. клетке

else i:=i+1;

Until (i>z) or (j>p);

For i:=1 to z do

For j:=1 to p do sgNac.Cells[j,i]:=FloatToStr(x[i,j]);

// Основной цикл

shag:=0;

REPEAT

shag:=shag+1;

Naxod_Poten;

Naxod_delta;

Naxod_Plan;

Updat;

// найдем значение целевой функции

f:=0;

For i:=1 to z do

For j:=1 to p do

f:=f+x[i,j]*c[i,j];

if zakon then break;

label10.Caption:=FloatToStr(f);

UNTIL False;

z_nac:=0;

for i:=1 to sgNac.ColCount-1 do

for j:=1 to sgNac.RowCount-1 do

if sgNac.Cells[i,j]<>'0' then

Z_nac:=z_nac+(StrToInt(sgNac.Cells[i,j])*StrToInt(sgisx.cells[i,j]));

label4.Caption:=IntToStr(z_nac);

if Z_nac>f then messageDlg('Транспортная задача закрытого типа'+#10#13

+' План оптимизирован!',mtInformation,[mbOK],0);

end;

except on EConvertError do MessageDlg('Заполните таблицу!'+#10#13+'Правая нижняя клетка не заполняется',MTError,[mbOK],0);

end;

end;

procedure TForm1.FormCreate(Sender: TObject);

var i,j:integer;

begin

form2.show;

for i:=1 to StringGrid1.ColCount-2 do StringGrid1.Cells[i,0]:='B'+IntToStr(i);

for j:=1 to StringGrid1.RowCount-2 do StringGrid1.Cells[0,j]:='A'+IntToStr(j);

StringGrid1.Cells[StringGrid1.ColCount-1,0]:='Запасы';

StringGrid1.Cells[0,StringGrid1.RowCount-1]:='Потребности';

end;

procedure TForm1.Button2Click(Sender: TObject);

var i,j:integer;

begin

try

Button1.Enabled:=true;

StringGrid1.ColCount:=StrToInt(CB2.Text)+2;

StringGrid1.RowCount:=StrToInt(CB1.Text)+2;

for i:=1 to StringGrid1.ColCount-2 do StringGrid1.Cells[i,0]:='B'+IntToStr(i);

for j:=1 to StringGrid1.RowCount-2 do StringGrid1.Cells[0,j]:='A'+IntToStr(j);

StringGrid1.Cells[StringGrid1.ColCount-1,0]:='Запасы';

StringGrid1.Cells[0,StringGrid1.RowCount-1]:='Потребности';

for i:=1 to StringGrid1.ColCount-2 do

for j:=1 to StringGrid1.RowCount-2 do

sgIsx.Cells[i,j]:=StringGrid1.Cells[i,j];

for j:=0 to StringGrid1.RowCount-1 do

sgZap.Cells[0,j]:=StringGrid1.Cells[StringGrid1.ColCount-1,j];

for i:=0 to StringGrid1.RowCount-1 do

sgPotr.Cells[i,0]:=StringGrid1.Cells[i,StringGrid1.RowCount-1];

sgIsx.ColCount:=StringGrid1.ColCount-1;

sgIsx.RowCount:=StringGrid1.RowCount-1;

sgZap.ColCount:=sgIsx.ColCount;

sgPotr.ColCount:=sgIsx.ColCount;

sgZap.RowCount:=sgIsx.RowCount;

sgPotr.RowCount:=sgIsx.RowCount;

sgNac.RowCount:=sgIsx.RowCount;

sgOpt.RowCount:=sgIsx.RowCount;

sgNac.ColCount:=sgIsx.ColCount;

sgOpt.ColCount:=sgIsx.ColCount;

except on EConvertError do MessageDlg('Выберите размерность матрицы!',MTError,[mbOK],0);

End;

end;

procedure TForm1.CB1Change(Sender: TObject);

begin

CB2.Text:=CB1.Text;

end;

procedure TForm1.CB2Change(Sender: TObject);

begin

CB1.Text:=CB2.Text;

end;

procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);

begin

form2.Close;

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

CB1.ItemIndex:=1;

CB2.ItemIndex:=1;

Button2.Click;

StringGrid1.Cells[1,1]:='12';

StringGrid1.Cells[2,1]:='16';

StringGrid1.Cells[3,1]:='21';

StringGrid1.Cells[1,2]:='4';

StringGrid1.Cells[2,2]:='4';

StringGrid1.Cells[3,2]:='9';

StringGrid1.Cells[1,3]:='3';

StringGrid1.Cells[2,3]:='8';

StringGrid1.Cells[3,3]:='14';

StringGrid1.Cells[4,1]:='950';

StringGrid1.Cells[4,2]:='50';

StringGrid1.Cells[4,3]:='1000';

StringGrid1.Cells[1,4]:='250';

StringGrid1.Cells[2,4]:='1000';

StringGrid1.Cells[3,4]:='750';

end;

procedure TForm1.BitBtn1Click(Sender: TObject);

begin

form3.show;

form3.WebBrowser1.Navigate(extractFilepath(paramstr(0))+'help.mht');

form3.WebBrowser2.Navigate(ExtractFilePath(paramstr(0))+'prog.mht');

end;

end.



Приложение Б

Формы программы

Рисунок 5 - Форма «Приветствие»

Рисунок 6 - Форма «Метод потенциалов»



Рисунок 7 - Форма «Справка»

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