Транспортная задача

Кавминводский Институт сервиса КМВИС Филиал Южно-Российского Государственного Университета Экономики и Сервиса ЮРГУЭС Курсовая работа по информатике тема работы Транспортная задача Выполнил студент 2-го курса Очного отделения группы ИС-01 Ханин Константин Александрович проверил старший преподаватель Макаров Борис Сергеевич.Пятигорск 2003 г. 1. Постановка задачи. В качестве объекта исследования рассматривается сеть с потоками однородного продукта экономико-математическая модель задачи оптимизации транспорта энергии, газа, трубопроводных систем различного назначения, а также транспортировки продукции от поставщиков к потребителям.

Требуется написать программу оптимизации транспорта энергии, газа, трубопроводных систем различного назначения по заданной схеме, решить систему уравнений заданным методом. 2. Спецификация. 1. Название задачи. По заданной схеме 3 следует найти в ходе выполнения работы направления потоков по ветвям и их величину P в условных единицах. 2.2 Описание задачи. Выберем произвольное направление на схеме по ветвям для формирования матрицы A Таким образом, получим матрицу A вида Таб.1. Ветви -10001000-100-1-100010011000100-111-1-10 00 Узлы 1 2 3 4 0 0-1 0-2 0-3 0-4 1-2 2-3 3-4 Затем введм диагональную матрицу R, элементами которой являются заданные стоимости перевозок по отдельным ветвям.

R Можно показать, опуская преобразования, связанные с поиском минимума целевой функции F, что искомый вектор потоков Р можно вычислить в матричной форме как -R- t . Где R-1 матрица, обратная матрице R, At транспонированная матрица А вектор Лагранжа потенциалов, который предварительно должен быть найден из решения системы уравнений в матричной форме R- t . Вектор Q- объм производства в узлах схемы, которые задаются в качестве входных данных по вариантам работы, и входит в уравнение 0, Таблица соответствия ВетвиНачалоКонецСтоимость 3. Управление программой. В среде Turbo Pascal программа после подготовки текста программы можно попытаться исполнить е, т.е. откомпилировать программу, связать е если это необходимо с библиотекой стандартных процедур и функций, загрузить в оперативную память и передать е управление.

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

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

Итак, нажимаем CtrlF9 или выбираем из меню RunRun, появляется голубой экран, которым является оформление курсовой работы, через некоторое время на экране появляется меню с 10-ю пунктами, выбрав любой пункт из меню, можно просмотреть интересующие результаты вычислений. 4. Входные данные Ввод данных это передача информации от внешних устройств в оперативную память. Вводятся, как правило, исходные данные решаемой задачи.

В мом курсовом проекте входными данными являются числа от 0 до 9, которые вводятся при выборе пункта меню с цифровой клавиатуры.

В разделе переменных они у меня записаны типом Byte. Byte это целочисленный тип данных я его взял потому, что числа от 0 до 9 являются целыми числами. Длина Byte 1 байт, а диапазон значений от 0 до 5. Выходные данные. Вывод данных это обратный процесс вводу данных, когда данные передаются из оперативной памяти на внешние носители принтер, дисплей, магнитные устройства и т.д Результаты решения всякой задачи должны быть выведены на один из этих носителей.Как и в моем курсовом проекте все результаты вычислений выводятся на дисплей монитора.

Основным устройством вывода у персонального компьютера является дисплей экран монитора. Все результаты вычислений я выводил на дисплей с помощью оператора Write Список вывода . Здесь элементами списка вывода могут быть выражения различных типов в частности, константы и переменные. У меня элементами списка вывода являются переменные.Второй вариант процедуры вывода на экран Writeln список вывода , слово Write line означает писать строку.

Его действие отличается от оператора Write тем, что после вывода последнего в списке значения происходит перевод курсора к началу следующей строки. Оператор Writeln, записанный без параметров, вызывает перевод строки. Форматы вывода. В списке вывода могут присутствовать указатели форматов вывода форматы. Формат определяет представление выводимого значения на экране. Он отделяется от соответствующего ему элемента двоеточием.Если указатель формата отсутствует, то машина выводит значение по определенному правилу, предусмотренному по умолчанию. 6. Пример Для тестирования программы нужно запустить программу нажатием CtrlF9 и дождаться появления меню, затем нужно ввести с клавиатуры цифру 1 и сравнить результат выведенной матрицы с матрицей приведнной в таблице 1выделенное заливкой, они должны совпасть. 3. Проектирование и алгоритмизация. Метод решения задачи метод Крамерапо предложенному преподавателем.

Метод Крамера имеет весьма простую схему.

Пусть detA определитель матрицы А, а detAi определитель матрицы Ai, полученной в матрице А столбца с номером i столбцов свободных членов. Тогда метод Крамера сводится к вычислению detA, detAi, i1,2 n, после чего значения неизвестных определяются элементарными соотношениями XidetAidetA, i1,2,n Определители в этой формуле вычисляются с помощью усеченного метода Гаусса.Действительно, прямой ход метода Гаусса приводит к верхней треугольной матрице, определитель которой равен произведению диагональных элементов матрицы. В прямом ходе метода Гаусса на каждом очередном шаге соответствующая строка делится на диагональный элемент.

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

Достаточно прост и нагляден, обеспечивает приемлемое быстродействие для систем невысокого порядка. Сохраняет преимущества и недостатки методов вычисления определителей. Как вычислительный метод в научных и технических задачах применяется редко.Блок-схема работы программы 3.1 Формирование матрицы А 3.2 Формирование матрицы R 3.3 Формирование обратной матрицы R1 3.4 Транспонирование матрицы А 3.5 Вычисление матрицы AR1At 3.6 Решение системы уравнений методом Крамера 3.6.1 Описание процедуры замены 3.6.2 Описание процедуры Opr 3.6.3 Вычисление Х-ов 3.7 Нахождение вектора Р 4. Кодирование алгоритма.

В мом курсовом проекте я использовал 3 одномерных массива X array 1 4 of real P array 1 7 of real pr array 1 4 of real Одномерный массив Х вещественного типа мне потребовался для формирования столбца из полученных корней уравнения, решенного методом Крамера.Массив Р, вещественного типа, я использовал для формирования столбца значений вектора потоков Р. Массив Pr , вещественного типа, я применил для формирования столбца проверочных данных.

Так же было использовано 6 двумерных массивов At array 1 7,1 4 of shortint R array 1 7,1 7 of shortint R1 array 1 7,1 7 of real R1At array 1 7,1 4 of real A array 1 4,1 7 of shortint U,U1 array 1 4,1 4 of real Массив At используется для формирования транспонированной матрицы А размерностью 7 строк и 4 столбца, элементы которой типа Shortint т.к. все элементы матрицы являются целыми числами, а в Shortint входят все числа от -128 до 128 . Массив R используется для формирования диагональной матрицы размером 7 строк на 7 столбцов все элементы этой матрицы, как и элементы матрицы At Shortint типа. Массив R1 матрица размером 7 строк на 7 столбцов обратная матрице R типа real вещественный тип данных т.к. при формировании обратной матрицы нужно применить деление, а при делении частное получается почти всегда вещественного типа. Массив R1At матрица размером 7 строк на 4 столбца, полученная в результате умножения матрицы R1 на матрицу At, элементы этой матрицы, как и элементы массива R1 типа real. Массив A матрица элементов таб.1выделено заливкой размером 4 строки на 7 столбцов тип Shortint.

Массивы U и U1 это матрица размером 4 строки на 4 столбца полученная в результате умножения R t тип элементов матрицы real. Переменную S я использовал в процедурах умножения матриц, в качестве счтчика тип этой переменной вещественного типа real. Переменные х1,х2,х3,х4 использованы в решении уравнения методом Крамера в качестве корней уравнения.

Тип этих переменных так же вещественный. d,dv,d1,d2,d3,d4 переменные вещественного типа d требуется для создания копии главного определителя dv. d1 - d4 определители требующиеся для нахождения корней уравнения.

Переменные i,j нужны для счтчиков в операциях с матрицами i это строки, j это столбцы тип этих переменных integer целый тип данных.

Переменная k использована при умножении матриц в качестве дополнительного счтчика тип integer. n переменная, использованная в процедуре замены для определения номера вырезаемого столбца тип переменной integer. nr переменная типа byte длина 1 байт, диапазон значений от 0 до 255 потребовалась в процедуре номеров пунктов меню. 5. Руководство ползователя. 5.1 Пуск Запуск из среды Turbo Pascal производится нажатием клавиш CtrlF9, а из Norton Commander нажатием клавиши Enter на файле Inform.exe. 5.2 Ввод данных Ввод данных производится только с цифровой клавиатуры. Цифры от 0 до 9. 5.3 Просмотр результатов.

После ввода цифрынужного пункта в меню выводится требуемый результат и после просмотра результата нужно нажать Enter. Затем вновь появится меню на экране. 5.4 Выход из программы Выход из программы в среде Turbo Pascal и после запуска Inform.exe файла производится 0-ым пунктом меню. Листинг программы. uses crt var X array 1 4 of real P array 1 7 of real At array 1 7,1 4 of shortint R array 1 7,1 7 of shortint R1 array 1 7,1 7 of real R1At array 1 7,1 4 of real A array 1 4,1 7 of shortint U,U1 array 1 4,1 4 of real pr,pro array 1 4 of real s,x1,x2,x3,x4,d,d1,d2,d3,d4,dv real i,j,k,n integernr byte const Q array 1 4 of integer 70,100 160 80 C array 1 7 of byte 4,5,7,6,5,8,5 Procedure Titul begin ClrScr Window1,1,80,25 TextBackGroundblue TextColor10 ClrScr GoToXY20,2 writelnКавминводский институт сервиса GoToXY20,5 writelnКурсовая работа по информатике GoToXY10,8 writelnстудента 2-го курса очного отделения группы ИС-01 GoToXY18,11 writelnХанина Константина Александровича GoToXY19,14 writelnТема работы Транспортная задача GoToXY19,17 writelnРуководитель ст. преп. Макаров Б.С. for i1 to 20 do Delay30000 end Procedure Vivoda begin GoToXY2,2writeМатрица Awritelnwriteln for i 1 to 4 do begin for j 1 to 7 do begin writeai,j5, endwriteln end end Procedure VivodR begin GoToXY2,2writeМатрица Rwritelnwriteln for i 1 to 7 do begin for j 1 to 7 do begin writeRi,j3, endwriteln end end Procedure VivodR1 begin GoToXY2,2writeМатрица R1writelnwriteln for i 1 to 7 do begin for j 1 to 7 do begin writeR1i,j31, endwriteln end end Procedure VivodAt begin GoToXY2,2writeМатрица Atwritelnwriteln for i 1 to 7 do begin for j 1 to 4 do begin writeAti,j5, endwriteln end end Procedure VivodAR1At begin u u1 GoToXY2,2writeМатрица Uwritelnwriteln for i 1 to 4 do begin for j 1 to 4 do begin writeUi,j51, endwriteln end end Procedure VivodQ begin GoToXY2,2writeСтолбец свободных членов Qwritelnwriteln for i 1 to 4 do writelnQi7 end Procedure VivodU begin GoToXY2,2writeСтолбец вектора Uwritelnwriteln for i 1 to 4 do writelnxi71 end Procedure VivodP begin GoToXY2,2writeСтолбец вектора Pwritelnwriteln for i 1 to 7 do writelnPi71 end Procedure Proverka begin for i 1 to 4 do begin s 0 for j 1 to 7 do s s ai,j pj pri s end for i 1 to 4 do writelnpr ,pri40 end Procedure Screen begin clrscr GotoXY5,7write1. Сформировать матрицу A GoToXY5,9write2. Сформировать матрицу R GoToXY5,11write3. Найти обратную матрицу R1 GoToXY5,13write4. Транспонировать матрицу A GoToXY5,15write5. Вычислить матрицу AR1At GoToXY5,17write6. Сформировать стлбец свободных членов Q GoToXY5,19write7. Pешить систему уравнений т.е. найти вектор U GoToXY5,21write8. Найти вектор P GoToXY5,23write9. Проверка GoToXY5,25write0. Выход GoToXY20,30writeВ В Е Д И Т Е Н О М Е P П У Н К Т А - readlnnrclrscr case nr of 1 vivoda 2 vivodR 3 vivodR1 4 vivodAt 5 vivodAR1At 6 vivodQ 7 vivodU 8 vivodP 9 Proverka 0 halt else writelnВы ввели неправильно пункт end end Procedure opr begin dv u1,1u2,2u3,3u4,4 u1,2u2,3u3,4u4,1 u1,3u2,4u3,1u4,2 - u1,4u2,3u3,2u4,1 - u1,1u2,4u3,3u4,2 - u1,2u2,1u3,4u4,3 end Procedure Zamena begin for i 1 to 4 do ui,n Qi end Procedure formA begin Формирование матрицы А a1,1-1a1,20a1,30a1,40a1,51a1,60a1,70 a2,10a2,2-1a2,30a2,40a2,5-1a2,6-1a2,70 a3,10a3,20a3,31a3,40a3,50a3,61a3,71 a4,10a4,20a4,30a4,41a4,50a4,60a4,7-1 end Procedure formR begin Формиррование матрицы R for i 1 to 7 do for j 1 to 7 do if ij then ri,j ci else ri,j0 end Procedure formR1 begin Формирование матрицы R1 for i 1 to 7 do for j 1 to 7 do if ij then r1i,j 1ri,j else r1i,j 0 end Procedure transA begin Транспонирование матрицы А for i 1 to 4 do begin for j 1 to 7 do begin Atj,i Ai,j endend end Procedure umnosh begin Умножение R1At for i 1 to 7 do for j 1 to 4 do begin s 0 for k 1 to 7 do s s R1i,k Atk,j R1Ati,j S end end Procedure vychisl begin Вычисление матрицы AR1At for i 1 to 4 do for j 1 to 4 do begin s 0 for k 1 to 7 do s s Ai,k R1Atk,j Ui,j s end end Управляющая программа Begin TiTul FormA FormR FormR1 TransA Umnosh Vychisl u1 u opr d dv n 1 zamena opr d1 dv u u1 n 2 zamena opr d2 dv u u1 n 3 zamena opr d3 dv u u1 n 4 zamena opr d4 dv x1 d1d x2 d2d x3 d3d x4 d4d x1 x1x2 x2x3 x3x4 x4 for i 1 to 7 do begin s 0 for k 1 to 4 do s s - r1ati,k xk pi s endwriteln for i 1 to 10 do begin Screenreadln end End.