|
Реферат: Аппаратные средства ПК (Компьютеры)
Реферат на тему:
Аппаратные средства ПК
Студента СПБГУТД
Группа № 1-ЭД-2 «В»
Меркоева Дмитрия
Санкт-Петербург
2004 год
Оглавление:
Введение……………………………………………………….3
Конфигурация персонального компьютера.......................3
Материнская плата…………………………………………..5
BIOS…………………………………………………………….6
IBM PC и принцип открытой архитектуры……………….8
Введение
В наше время трудно представить себе, что без компьютеров можно
обойтись. А ведь не так давно, до начала 70-х годов вычислительные машины
были доступны весьма ограниченному кругу специалистов, а их применение, как
правило, оставалось окутанным завесой секретности и мало известным широкой
публике. Однако в1971 г. произошло событие, которое в корне изменило
ситуацию и с фантастической скоростью превратило компьютер в повседневный
рабочий инструмент десятков миллионов людей. В том вне всякого сомнения
знаменательном году еще почти никому не известная фирма Intel из небольшого
американского городка с красивым названием Санта-Клара (шт. Калифорния),
выпустила первый микропроцессор. Именно ему мы обязаны появлением нового
класса вычислительных систем - персональных компьютеров, которыми теперь
пользуются, по существу, все, от учащихся начальных классов и бухгалтеров
до маститых ученых и инженеров. Этим машинам, не занимающим и половины
поверхности обычного письменного стола, покоряются все новые и новые классы
задач, которые ранее были доступны (а по экономическим соображениям часто и
недоступны - слишком дорого тогда стоило машинное время мэйнфреймов и мини-
ЭВМ) лишь системам, занимавшим не одну сотню квадратных метров. Наверное,
никогда прежде человек не имел в своих руках инструмента, обладающего столь
колоссальной мощью при столь микроскопических размерах.
У персонального компьютера есть два важных преимущества по сравнению
со всеми другими видами компьютеров: он имеет относительно простое
управление и может решать достаточно широкий класс задач.
Если ранее на ЭВМ могли в основном работать только профессиональные
программисты (практически для любой задачи приходилось создавать свою
программу), то теперь ситуация коренным образом изменилась. В настоящее
время разработаны десятки тысяч программ по всем областям знаний. С ними
работают десятки миллионов квалифицированных пользователей.
Согласно статистическим данным, самыми распространенными и
используемыми программами являются операционные системы и текстовые
редакторы.
Знание характеристик компьютерных устройств поможет квалифицированному
пользователю выбрать оптимальную конфигурацию персонального компьютера для
решения поставленной практической задачи.
Конфигурация персонального компьютера
Персональными называются компьютеры, на которых может одновременно
работать только один пользователь. Персональные компьютеры имеют только
одно рабочее место.
Под термином «конфигурация» компьютера понимают список устройств,
входящих в его состав.
В соответствие с принципом открытой архитектуры аппаратное обеспечение
компьютеров (Hardware) может быть весьма различным. Но любой персональный
компьютер имеет обязательный и дополнительный набор устройств.
Обязательный набор устройств:
1. Монитор - устройство вывода текстовой и графической информации.
2. Клавиатура - устройство для ввода текстовой информации.
3. Системный блок - объединение большого количества различных компьютерных
устройств.
В системном блоке находится вся электронная начинка компьютера.
Основными деталями системного блока являются:
4. Процессор - главное компьютерное устройство управления и проведения
вычислений.
5. Материнская плата - устройство для крепления на ней других внутренних
компьютерных устройств.
6. Оперативная память (ОЗУ) - устройство для хранения программы и данных
во время ее работы в компьютере.
7. Постоянное запоминающее устройство (ПЗУ) - устройство для постоянного
хранения некоторых специальных программ и данных.
8. Кэш память - сверхбыстрая память для хранения особо важной информации.
9. Сопроцессор - устройство для выполнения операций с плавающей запятой.
10. Видеокарта - устройство, обеспечивающее вывод информации на монитор.
11. Флоппи дисковод - устройство для хранения и переноса информации между
ПК.
12. Винчестер - основное устройство для хранения информации на компьютере.
13. Блок питания - устройство для распределения электрической энергии между
другими компьютерными устройствами.
14. Контроллеры и шина - предназначены для передачи информации между
внутренними устройствами ПК.
15. Последовательные и параллельные порты - предназначены для подключения
внешних дополнительных устройств к компьютеру.
16. Корпус - предназначен для защиты материнской платы и внутренних
устройств компьютера от повреждений.
Дополнительные устройства, которые можно подключать к компьютеру:
17. Принтер - предназначен для вывода текстовой и графической информации на
бумагу.
18. Дисковод для компакт дисков (CD ROM) - для работы с компакт дисками.
19. Дисководы DVD - современные устройства для работы с носителями данных
объемом до 17 Гбайт.
20. Звуковая карта - устройство для работы со звуковой информацией.
21. Мышь - манипулятор для ввода информации в компьютер.
22. Джойстик - манипулятор для передачи информации о движении в компьютер.
23. Планшет - устройство для работы с компьютерной графикой.
24. TV тюнер является устройством, позволяющим ПК принимать и показывать
программы телевидения.
25. Колонки - внешние устройства для воспроизведения звуков.
26. Факс-модем - устройство для связи между компьютерами через телефонную
линию.
27. Плоттер - устройство для вывода чертежа на бумагу.
28. Сканер - для ввода графических изображений в компьютер.
29. Ленточные накопители - устройства для проведения резервного копирования
данных на магнитную ленту.
30. Источник бесперебойного питания - устройство защиты компьютера от
перебоев в электроснабжении.
31. Накопители на съемных дисках - устройства, в будущем заменяющие флоппи
дисководы.
32. Графический акселератор - устройство для ускорения обработки и вывода
трехмерной графики.
и многое другое...
Для обозначения конфигурации конкретного персонального компьютера
применяют записи стандартного типа. Разберем ее на примере:
Pentium II - 333/ 64 Sdram / 3.1Gb / ATI 3D Char 4 Mb / Mini / CD ROM
24X + SB 16 ESS68
Итак, что это за компьютер? Вначале пишется тип процессора - Pentium
II с тактовой частотой 333 МГц. Далее обозначен объем и тип оперативной
памяти - 64 Мбайта. В ПК встроен винчестер объемом 3.1 Гбайт. Используется
видеокарта ATI 3D Char c 4 Мбайтами видеопамяти, видеокарта оптимизирована
для работы с трехмерной графикой 3D. Корпус MiniTower. Также в состав ПК
входит 24-скоростной дисковод для компакт дисков и простая звуковая карта
Sound Blaster. В стандартную конфигурацию компьютера всегда входит 3.5
дюймовый флоппи-дисковод, поэтому он в записи не указывается. Мышь также
входит в стандартную конфигурацию. Но монитор совместно с данным комплектом
не продается. Его необходимо покупать отдельно. Общий итог - данный
компьютер имеет минимальную стандартную конфигурацию для использования в
офисе и дома весной 1999 г.
Материнская плата
Материнская плата (Mother board) является основной платой компьютера,
т.к. именно на ней крепятся все компьютерные устройства, например,
процессор, звуковая карта и т.д.
Материнские платы собираются на основе специального набора микросхем,
называемого Chipset.В зависимости от типа устанавливаемого процессора,
необходимо использовать различные chipsetы, и получать, т.о. материнские
платы разных типов.
Так, для 486 процессоров существовал специальный тип 486 материнских
плат. Для процессоров Pentium использовались два вида плат: первый для
процессоров с тактовой частотой 60 и 66 МГц, а второй - для всех остальных.
Для последующих типов процессоров также необходимо использовать
соответствующие системные платы. Так, например, для процессора Celeron
используется плата на наборе микросхем 443EX.
Самым популярным производителем материнских плат в России считается
фирма Asustek. Хотя на практике можно использовать компьютеры с материнской
платой различных производителей. Например, A-Bit, A-Trend, Giga - Byte и
другие.
Последней разработкой в области системных плат для настольных ПК стала
технология NLX, и, возможно, именно она окажется ведущей технологией
ближайшего будущего. Платы этого стандарта, на первый взгляд, напоминают
платы LPX, но на самом деле они значительно усовершенствованы. Если на
платы LPX нельзя установить самые новые процессоры из-за их более крупных
размеров и повышенного тепловыделения, то в разработке NLX эти проблемы
прекрасно разрешены. Вот каковы основные преимущества этого нового
стандарта, перед остальными.
• Поддержка современных процессорных технологий. Это особенно важно для
систем с процессором Pentium II, поскольку размер его корпус Single Edge
Contact (т.е. корпуса, с единственным рядом расположенных по периметру
контактов) практически не позволяет устанавливать этот процессор на
платах Baby-AT и LPX. И хотя некоторые производители системных плат все
же предлагают АТХ-системы на основе Pentium II, на их платах остается
место только для двух 72-контактных разъемов модулей SIMM!
• Гибкость по отношению к быстро изменяющимся процессорным технологиям.
Идея гибких систем с объединительной платой нашла новое воплощение в
конструкции плат NLX, установить которые можно быстро и легко, не
разбирая при этом всю систему на части. Но в отличие от традиционных
систем с объединительными платами, у нового стандарта NLX есть поддержка
таких лидеров компьютерной индустрии, как AST, Digital, Gateway, Hewlett-
Packard, IBM, Micron, NEC и другие.
• Поддержка других новых технологий. Речь здесь идет о таких высоко
производительных решениях, как AGP (Accelerated Graphics Port -
ускоренный графический порт), USB (Universal Serial Bus - универсальная
последовательная шина), технологии больших модулей памяти и DIMM. А в
ответ на всевозрастающую роль мультимедиа-приложений разработчики
встроили в новую системную плату еще и поддержку таких возможностей, как
проигрывание назад видеоролика, расширенные графика и звук. И если в
прошлом использование мультимедиа-технологий означало дополнительные
затраты на различные дочерние платы, то теперь необходимость в них
отпала.
Системная плата NLX и платы ввода-вывода (располагающиеся, как и в
конструкции LPX, параллельно системной) теперь легко вставляются и
вынимаются, при этом другие платы, в том числе и расположенные вертикально,
остаются нетронутыми. Легче добраться и до самого процессора, который
охлаждается теперь гораздо лучше, чем в системах с тесно расположенными
компонентами. Поддержка плат расширения различного размера позволяет
выпускать системы различных модификаций.
Стандарт NLX обеспечивает максимальную гибкость систем и самое
оптимальное использование свободного пространства. Даже самые длинные платы
ввода-вывода устанавливаются без труда и не задевают при этом никаких
других системных компонентов, что было настоящей проблемой для компьютеров
типа Baby-AT.
BIOS
BIOS - Базовая система ввода-вывода (Basic Input Output System)
называется так потому, что включает в себя обширный набор программ ввода-
вывода, благодаря которым операционная система и прикладные программы могут
взаимодействовать с различными устройствами как самого компьютера, так и
подключоными к нему. Вообще говоря, в PS система BIOS занимает особое
место. С одной стороны, ее можно рассматривать как составную часть
аппаратных средств, с другой стороны, она является как бы одним из
програмных модулей операционной системы. Сам термин BIOS, видимо,
заимствован из операционной системы CP/M, в которой модуль с подобным
названием был реализован програмно и выполнял примерно подобные действия.
Большинство современных видеоадаптеров, а также контроллеры накопителей
имеют собственную систему BIOS, которая обычно дополняет системную. Во
многих случаях программы, входящие в конкретную BIOS, заменяют
соответствующие програмные модули основной BIOS. Вызов программ BIOS, как
правило, осуществляется через програмные или аппаратные прерывния.
Система BIOS помимо программ взаимодействия с аппаратными средствами на
физическом уровне содержит программу тестирования при включении питания
компьютера POST (Power–On-Self-Test, Самотестирование при включении питания
компьютера). Тестируются основные компоненты, такие как процкссор, память,
вспомогательные микросхемы, приводы дисков, клавиатуру и видеоподсистему.
Если при включении питания компьютера возникают проблемы (BIOS не может
выполнить начальный тест), вы услышите последовательность звуковых
сигналов:
|Код |Значение |
|сигнала | |
|1 |Ошибка регенерации DRAM |
|2 |Отказ схемы четности |
|3 |Отказ базового ОЗУ 64 Кб |
|4 |Отказ системного таймера |
|5 |Отказ процессора |
|6 |Ошибка адресной линии A20 контроллера клавиатуры |
|7 |Ошибка исключения виртуального режима Virtual Mode |
| |Exception |
|8 |Ошибка теста чтения, записи памяти дисплея |
|9 |Ошибка контрольной суммы ROM-BIOS |
Если вы сталкиваетесь с чем-либо подобным, существует высокая
вероятность того, что эта проблема связана с аппаратными средствами.
Система BIOS в PS реализована в виде одной микросхемы, установленной на
материнской плате компьютера.Название ROM BIOS в настоящее время не совсем
справедливо, ибо «ROM» - предполагает использование постоянных запоминающих
устройств (ROM - Read Only Memory), а для хранения кодов BIOS в настоящее
время применяются в основном перепрограммируемые (стираемые электрически
или с помощью ультрафиолетового излучения) запоминающие устройства. Мало
того, наиболее перспективным для хранения системы BIOS является сейчас флэш-
память. Это позволяет легко модифицировать старые или добавлять
дополнительные функции для поддержки новых устройств, подключаемых к
компьютеру.
Поскольку содержимое ROM BIOS фирмы IBM было защищено авторским правом,
то есть его нельзя подвергать копированию, то большинство других
производителей компьютеров вынуждены были использовать микросхемы BIOS
независимых фирм, системы BIOS которых, разумеется, были практически
полностью совместимы с оригиналом. Наиболее известные из этих фирм три:
American Megatrends Inc. (AMI), Award Software и Phoenix Technologies.
Заметим, что конкретные версии BIOS неразрывно связаны с набором микросхем
(chipset), используемым на системной плате. Кстати, компания Phoenix
Technologies считается пионером в производстве лицензионно-чистых BIOS.
Именно в них впервые были реализованы такие функции, как задание типа
жесткого диска, поддержка привода флоппи-дисков емкостью 1,44 Мбайта и т.д.
Более того, считается, что процедура POST этих BIOS имеет самую мощную
диагностику. Справедливости ради надо отметить, что BIOS компании AMI
наиболее распространены. По некоторым данным, AMI занимает около 60% этого
сегмента рынка. Кроме того, из программы Setup AMI BIOS можно вызвать
несколько утилит для тестирования основных компонентов системы и работы с
накопителями. Однако при их использовании особое внимание следует обратить
на тип интерфейса, который использует привод накопителя.
Система BIOS в компьютерах, неразрывно связана с SMOS RAM. Под этим
понимается «неизменяемая» память, в которой хранится информация о текущих
показаниях часов, значении времени для будильника, конфигурации компьютера:
количестве памяти, типах накопителей и т.д. Именно в этой информации
нуждаются программные модули системы BIOS. Своим названием SMOS RAM обязана
тому, что эта память выполнена на основе КМОП-струкгур (CMOS-Complementary
Metal Oxide Semiconductor), которые, как известно, отличаются малым
энергопотреблением. Заметим, что CMOS-память энергонезависима только
постольку, поскольку постоянно подпитывается, например, от аккумулятора,
расположенного на системной плате, или батареи гальванических элементов,
как правило, смонтированной на корпусе системного блока.Большинство
системных плат допускают питание CMOS RAM как от встроенного, так и от
внешнего источника.
В случае повреждения микросхемы CMOS RAM (или разряде батареи или
аккумулятора) программа Setup имеет возможность воспользоваться некой
информацией по умолчанию (BIOS Setup Default Values), которая хранится в
таблице соответствующей микросхемы ROM BIOS. Кстати, на некоторых
материнских платах питание микросхемы CMOS RAM может осуществляться как от
внутреннего, так и от внешнего источника. Выбор определяется установкой
соответствующей перемычки.
Программа Setup поддерживает установку нескольких режимов
энергосбережения, например Doze (дремлющий), Standby (ожидания, или
резервный) и Suspend (приостановки работы). Данные режимы перечислены в
порядке возрастания экономии электроэнергии. Система может переходить в
конкретный режим работы по истечении определенного времени, указанного в
Setup. Кроме того, BIOS обычно поддерживает и спецификацию АРМ (Advanced
Power Management). Как известно, впервые ее предложили фирмы Microsoft и
Intel. В их совместном документе содержались основные принципы разработки
технологии управления потребляемой портативным компьютером мощностью.
Задание полной конфигурации компьютера осуществляется не только
установками из программы Setup, но и замыканием (или размыканием)
соответствующих перемычек на системной плате. Назначение каждой из них
указано в соответствующей документации.
IBM PC и принцип открытой архитектуры
Принцип открытой архитектуры гласит, что компьютеры собираются из
комплектующих, созданных в соответствии с определенными стандартами. Данные
стандарты опубликованы и информационно доступны. При этом пользователь
имеет возможность самостоятельно вставлять в ПК платы самых разных фирм -
производителей и адаптировать свой персональный компьютер к требуемой
деятельности.
До появления персональных компьютеров IBM PC все другие модели были
основаны на принципе «закрытой архитектуры», т.е. все аппаратные средства
были для конечного пользователя «вещью в себе». После того, как
заканчивалась сборка аппарата, он «был обречен на необратимое старение».
Если с производства снималась хоть одна деталь, систему можно было
выбрасывать.
То, что IBM PC стали стандартом персональных машин связано с его очень
удачной конструкцией. Компьютеры IBM могут быть созданы из независимо
изготовленных частей аналогично детскому конструктору. Если работа любой
детали вас не устраивает, ее вынимают и заменяют другой. Ранее, если какая-
нибудь деталь снималась с производства, надо было выбрасывать весь прибор.
Для IBM PC есть десятки предложений по замене. Компьютеры IBM PC созданы в
соответствие с принципом открытой архитектуры
Достоинства принципа открытой архитектуры можно рассмотреть на
следующем примере: Пусть у нас есть простой монофонический плеер. Мы
покупаем и вставляем в него устройство для записи звука. В результате
получаем монофонический магнитофон. Добавляем вторую колонку и слушаем
стерео. Подключаем FM тюнер и получаем магнитолу. Далее осталось сделать
еще один шаг и в результате вместо старого плеера мы имеем - двух кассетную
стерео магнитолу. Просто в дополнение к прежним деталям мы докупили
несколько новых и соединили их вместе. К сожалению, на практике с
магнитофонами данный подход не работает, но с компьютерами все обстоит
намного лучше.
Реферат на тему: Аппроксимация
Министерство общего и профессионального образования Российской Федерации
Московский Государственный Строительный Университет
Кафедра информатики и прикладной математики
КУРСОВАЯ РАБОТА ПО ИНФОРМАТИКЕ
на темы:
1. Аппроксимация.
2. Разработка модуля исключения нуль-уравнений в комплексе “Решение
задачи линейного программирования”.
Выполнил студент ЭОУС – I – 2: Моносов А. Л.
Преподаватель: доцент Марьямов А. Г.
Москва 1999.
Оглавление.
I. Математическая часть. Название…………………………………3.
1.1 Постановка задачи………………………………………………….3.
2.1 Изложение метода………………………………………………….4.
3.1 Блок-схема алгоритма. Описание исходных данных и
результатов………………………………………………………………5.
4.1 Листинг программы, исходных данных и результатов……………6.
5.1 Список переменных основной программы………………………10.
6.1 Заголовки процедур и функций. Список их переменных……….10.
7.1 Ручной расчет……………………………………………………..11.
8.1 Обсуждение результатов с целью доказательства правильности алгоритма
и программы………………………………………………..12.
9.1 Выводы…………………………………………………………….13.
II. Экономическая часть. Название………………………………..14.
1.2 Постановка задачи линейного программирования и задание на разработку
модуля……………………………………………………...14.
2.2 Описание исходных данных и результатов решения задач линейного
программирования………………………………………...18.
3.2 Описание модуля типов…………………………………………..19.
4.2 Укрупненная блок-схема задачи линейного программирования..20.
5.2 Параметры и заголовки процедур задачи линейного
программирования……………………………………………………..21.
6.2 Блок-схема и параметры реализованной процедуры……………21.
7.2 Листинг модуля, исходных данных и результатов машинного
расчета………………………………………………………………….23.
8.2 Ручной расчет задачи линейного программирования…………...24.
9.2 Выводы…………………………………………………………….26.
Список использованной литературы. ……………………………..27.
I. Математическая часть. Аппроксимация.
1. Постановка задачи.
Пусть величина y является функцией аргумента x. Это означает, что любому
значению x из области определения поставлено в соответствии значение y.
Вместе с тем на практике часто неизвестна явная связь между y и x, т.е.
невозможно записать эту связь в виде y=f(x). В некоторых случаях даже при
известной зависимости y=f(x) она настолько громоздка (например, содержит
трудно вычисляемые выражения, сложные интегралы и т.п.), что ее
использование в практических расчетах затруднительно.
Наиболее распространенным и практически важным случаем, когда вид связи
между параметрами x и y неизвестен, является задание этой связи в виде
некоторой таблицы {xi yi}. Это означает, что дискретному множеству значений
аргумента {xi} поставлено в соответствие множество значений функции {yi}
(i=0,1…n). Эти значения - либо результаты расчетов, либо экспериментальные
данные. На практике нам могут понадобиться значение величины y и в других
точках, отличных от узлов xi. Однако получить эти значения можно лишь путем
очень сложных расчетов или провидением дорогостоящих экспериментов.
Таким образом, с точки зрения экономии времени и средств мы приходим к
необходимости использования имеющихся табличных данных для приближенного
вычисления искомого параметра y при любом значении (из некоторой области)
определяющего параметра x, поскольку точная связь y=f(x) неизвестна.
Этой цели и служит задача о приближение (аппроксимации) функций: данную
функцию f(x) требуется приближенно заменить (аппроксимировать) некоторой
функцией g(x) так, чтобы отклонение (в некотором смысле) g(x) от f(x) в
заданной области было минимальным. Функция g(x) при этом называется
аппроксимирующей.
Для практики весьма важен случай аппроксимации функции многочленом:
g(x)=a0+a1x+a2x2+…+amxm (2.1)
При этом коэффициенты aj будут подбираться так, чтобы достичь
наименьшего отклонения многочлена от данной функции.
Если приближение строиться на заданном множестве точек {xi}, то
аппроксимация называется точечной. К ней относятся интерполирование,
среднеквадратичное приближение и др. При построении приближения на
непрерывном множестве точек (например, на отрезке [a,b] аппроксимация
называется непрерывной или интегральной).
2.1 Изложение метода (Точечная аппроксимация).
Одним из основных типов точечной аппроксимации является
интерполирование. Оно состоит в следующем: для данной функции y=f(x) строим
многочлен (2.1), принимающий в заданных точках xi те же значения yi, что и
функция f(x), т.е. g(xi)=yi, i=0,1,…n.
При этом предполагается, что среди значений xi нет одинаковых, т.е.
xi(xk при этом i(k. Точки xi называются узлами интерполяции, а многочлен
g(x) - интерполяционным многочленом.
Рис. 1
Таким образом, близость интерполяционного многочлена к заданной функции
состоит в том, что их значения совпадают на заданной схеме точек (рис.1,
сплошная линия).
Максимальная степень интерполяционного многочлена m=n; в этом случае
говорят о глобальной интерполяции.
При большом количестве узлов интерполяции получается высокая степень
многочлена (2.1) в случае глобальной интерполяции, т.е. когда нужно уметь
один интерполяционный многочлен для всего интервала изменения аргумента.
Кроме того, табличные данные могли быть получены путем измерений и
содержать ошибки. Построение аппроксимируемого многочлена с условием
обязательного прохождения его графика через эти экспериментальные точки
означало бы тщательное повторение допущенных при измерениях ошибок. Выход
из этого положения может быть найден выбором такого многочлена, график
которого проходит близко от данных точек (рис.1, штриховая линия).
Одним из таких видов является среднеквадратичное приближение функции с
помощью многочлена (2.1). При этом m ( n; случай m = n соответствует
интерполяции. На практике стараются подобрать аппроксимирующий многочлен
как можно меньшей степени (как правило, m=1, 2, 3).
Мерой отклонения многочлена g(x) от заданной функции f(x) на множестве
точек (xi,yi) (i=0,1,…,n) при среднеквадратичном приближении является
величина S, равная сумме квадратов разности между значениями многочлена и
функции в данных точках:
n
S = ([g(xi)-yi]2
i=0
Для построения аппроксимирующего многочлена нужно подобрать коэффициенты
a0, a1,…,am так, чтобы величина S была наименьшей. В этом состоит метод
наименьших квадратов.
n
dS/da1=2([ g(xi)-yi]2*1=0;
i=1
n
dS/da2=2([ g(xi)-yi]2*xi=0;
i=1
…
n
dS/dam+1=2([ g(xi)-yi]2*xim=0.
i=1
C
A B
|n |( xi |… |( xim | |a1 | |(yi |
|( xi |( xi2 |… |( | |a2 | |(yixi |
| | | |xim+1 | | | | |
|… |…… |… |…… | |… | |… |
|( xim|( |… |( xi2m| |am+1| |(yixim|
| |xim+1 | | | | | | |
3.1 Блок-схема алгоритма. Описание исходных данных и результатов.
Исходные данные, а именно:
m-число узлов аппроксимации.
n - степень аппроксимирующего многочлена.
X - вектор узлов аппроксимации.
Y - вектор значений аппроксимируемой функции.
Все эти значения мы заносим в файл jan.dat, который работает только на
чтение и файловой переменной является f1.
Результаты:
Все результаты выводятся в файл jan.res, работающий на запись и имеющий
файловую переменную f2.
Первоначально в этот файл выводятся исходные данные, которые берутся из
файла jan.dat, но при этом уже с описанием, то есть не просто числа, а
скоментарием, что они означают.
Затем выводятся результаты вычисления, проведенной машиной, при этом все
результаты отформатированы:
Выводится матрица С системы линейных уравнений для аппроксимации вместе
с вектором правых частей. Затем выводится решение этой системы уравнений,
что является вектором коэффициентов аппроксимирующего многочлена по
возрастанию степени. И в конце выводится вектор погрешности аппроксимации
Z.
4.1 Листинг программы, исходных данных и результатов.
program approx;
uses crt,gausstpu;
const nm=20;
type vect1=array[1..nm] of real;
var c:matr;
a,b:vect;
x,y,z:vect1;
n,i,j,m:integer;
f1,f2:text;
procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);
var i,j:integer;
r:vect;
begin
for i:=1 to n do
r[i]:=1;
for j:=1 to m+1 do begin
c[1,j]:=0;
b[j]:=0;
for i:=1 to n do begin
c[1,j]:=c[1,j]+r[i];
b[j]:=b[j]+r[i]*y[i];
end;
for i:=1 to n do
r[i]:=r[i]*x[i];
end;
for i:=1 to m do begin
for j:=1 to m do
c[i+1,j]:=c[1,j+1];
c[i+1,m+1]:=0;
for j:=1 to n do
c[i+1,m+1]:=c[i+1,m+1]+r[j];
for j:=1 to n do
r[j]:=r[j]*x[j];
end;end;
begin
assign(f1,'jan.dat');reset(f1);
assign(f2,'jan.res');rewrite(f2);
readln(f1,n);writeln(f2,'Число узлов аппроксимации n=',n:3);
readln(f1,m);writeln(f2,'Степень многочлена m=',m:2);
writeln(f2,'Вектор узлов аппроксимации x[i]');
for i:=1 to n do begin
read(f1,x[i]);
write(f2,x[i]:4:2,' ');
end;
writeln(f2);
writeln(f2,'Вектор значений аппроксимируемой функции y[i]');
for i:=1 to n do begin
read(f1,y[i]);
write(f2,y[i]:4:2,' ');
end;
Create_BC(n,m,x,y,c,b);
writeln(f2);
writeln(f2,'Матрица системы линейных уравнений для аппроксимации и вектор
правых частей);
for i:=1 to m+1 do begin
for j:=1 to m+1 do
write(f2,c[i,j]:8:1);writeln(f2,b[i]:8:1);end;
gauss(m+1,c,b,a);
for i:=1 to n do begin
z[i]:=0;
for j:=m+1 downto 1 do
z[i]:=z[i]*x[i]+a[j];
z[i]:=z[i]-y[i];end;
writeln(f2);
writeln(f2,'Вектор коэфициентов аппроксимирующего многочлена по
возрастанию);
writeln(f2,'степени (m+1 элементов)');
for i:=1 to m+1 do
writeln(f2,'a[',i:1,']=',a[i]:6:2);
writeln(f2,'Вектор погрешности аппроксимации в узлах X);
for i:=1 to n do
writeln(f2,'z[',i:1,']=',z[i]:5:3);
close(f1);close(f2);
end.
Исходный файл jan.dat:
10
2
1 6 0 3 8 2 12 9 2 5
9 4 13 7 3 9 3 1 4 2
Файл результатов jan.res:
Число узлов аппроксимации n=10
Степень многочлена m=2
Вектор узлов аппроксимации x[i]
1.00 6.00 0.00 3.00 8.00 2.00 12.00 9.00 2.00 5.00
Вектор значений аппроксимируемой функции y[i]
9.00 4.00 13.00 7.00 3.00 9.00 3.00 1.00 4.00 2.00
Матрица системы линейных уравнений для аппроксимации и вектор правых частей
10.0 48.0 368.0 55.0
48.0 368.0 3354.0 159.0
368.0 3354.0 33428.0 1023.0
Вектор коэфициентов аппроксимирующего многочлена по возрастанию степени
(m+1 элементов)
a[1]= 11.66
a[2]= -2.31
a[3]= 0.13
Вектор погрешности аппроксимации в узлах X
z[1]=0.479
z[2]=-1.381
z[3]=-1.343
z[4]=-1.070
z[5]=-1.247
z[6]=-1.430
z[7]=-0.244
z[8]=0.723
z[9]=3.570
z[10]=1.454
5.1 Список переменных основной программы.
В основной программе используются раздел констант и типов:
const nm=20;
type vect1=array[1..nm] of real;
Следующие переменные так же используются в программе, которые описываются в
разделе var:
|Переменная |Тип |Описание переменной |
| |переменной | |
|С |matr |Матрица системы линейных уравнений |
| | |для аппроксимации |
|А |vect |Вектор коэфициентов аппроксимирующего|
| | |многочлена по возрастанию степени |
| | |(m+1 элементов) |
|Х |vect1 |Вектор узлов аппроксимации |
|B |vect |Вектор правых частей |
|Y |vect1 |Вектор значений аппроксимирующей |
| | |функции |
|Z |vect |Вектор погрешности аппроксимации в |
| | |узлах Х |
|n |integer |Число узлов аппроксимации |
|m |integer |Степень многочлена |
|i |integer |Необходима для нумерации элементов |
| | |массивов. |
|j |integer |Необходима для нумерации элементов |
| | |массивов. |
|f1 |text |Файловая переменная для файла |
| | |исходных значений |
|f2 |text |Файловая переменная резуртирующего |
| | |файла |
6.1 Заголовки процедур и функций. Список их переменных.
В своей программе я использовал следующие модули, которые описываются в
операторе uses и процедуры:
Crt - стандартный модуль подключения экрана и клавиатуры для работы с
программой.
Gauss - процедура решения системы линейных уравнений методом Гаусса. Она
берется из модуля Gausstpu, где интерфейсная часть имеет вид:
Interface
Const nmax=20
Type
Поэтому при объявлении матрицы С ссылаться надо на matr, а векторов A и B
на vect.
Create_BC - процедура расчета матрицы С (С - матрица системы линейных
уравнений для аппроксимации). Заголовок этой процедуры выглядит так:
procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);
var i,j:integer;
r:vect;
А вот такие переменные используются только в этой процедуре, остальные
засылаются из основной программы:
|Переменная |Тип |Описание переменной |
| |переменной | |
|i |integer |Используются в циклах для перебора |
| | |численных значений |
|j |integer |Используются в циклах для перебора |
| | |численных значений |
|R |vect |Рабочий вектор |
7.1 Ручной счет.
Составляем матрицу системы уравнений по следующему принципу:
|n |(xi |(xi2|(yi |
|(xi |(xi2|(xi3|(xiyi|
|(xi2 |(xi3|(xi4|(xi2y|
| | | |i |
Для этого вычисляем необходимые значения:
n=10;
(xi=1+6+0+3+8+2+12+9+2+5=48;
(xi2=12+62+02+32+82+22+122+92+22+52=368;
(yi=9+4+13+7+3+9+3+1+4+2=55;
(xi3=13+63+03+33+83+23+123+93+23+53=3354;
(xiyi=1*9+6*4+0*13+3*7+8*3+2*9+12*3+9*1+2*4+5*2=159;
(xi3=14+64+04+34+84+24+124+94+24+54=33428;
(xi2yi=12*9+62*4+02*13+32*7+82*3+22*9+122*3+92*1+22*4+52*2=1023.
Получается следующая матрица:
|10 |48 |368 |55 |
|48 |368 |3354 |159 |
|368 |3354 |33428 |1023|
Которая эквивалентна такой системе уравнений:
10a1 + 48a2 + 368a3 = 55
48a1 + 368a2 + 3354a3 = 159
368a1 + 3354a2 + 33428a3 = 1023
Мы решаем эту систему уравнений методом Гаусса:
|10 |48 |368 |55 |
|0 |137,6 |1587,6 |-105 |
|0 |1587,6|19885,6 |-1001 |
|10 |48 |368 |55 |
|0 |137,6|1587,6 |-105 |
|0 |0 |1568,203488|210.4680233 |
Получаем упрощенную систему уравнений:
1568,203488a3 = 210,4680233
137,6a2 + 1587,6a3 = -105
10a1 + 48a2 + 368a3 = 55
Решая которую получаем следующие окончательные значения, которые
являются ответом:
a3=210,4680233/1568,203488=0,134209638
a2=(-105-1587,6 a3)/137,6=-2,311564115
a1=(55-48a2-368a3)/10=11,65659307
8.1 Обсуждение результатов с целью доказательства правильности алгоритма и
программы.
Полученные результаты показывают, что алгоритм и программа составлены
верно, так как значения полученные при ручном счете близки к машинным
вычислением.
9.1 Выводы.
Данная программа очень эффективна, так как машина выполняет все действия
гораздо быстрее, чем человек при ручном счете. Так же во время ручного
счета могут произоити ошибки, что приведет к повторному перещитыванию, а у
машины, при правильном алгоритме, таких сбоев не бывает (если только
"зависает"). Следовательно эта программа во многом облегчает жизнь
человеку.
II. Экономическая часть. Разработка модуля исключения нуль-уравнений в
комплексе “Решение задачи линейного программирования”.
1.2 Постановка задачи линейного программирования и задание на разработку
модуля.
Рассмотрим задачу оптимального планирования производства [1]. Пусть
предприятие выпускает n изделий, для производства которых используется m
ингредиентов. Ингредиенты это – детали определенного сортамента, станки,
работники, электроэнергия и т.д., иначе говоря, все что требуется для
осуществления производственного цикла. Запасы ингредиентов задаются
вектором b=(b1, b2,…, bm ), где bi - запас i-го ингридиента (i=1,…,m).
Задана матрица А, элемент которой aij определяет расход i-го ингридиента
для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан
вектор рыночных цен изделий p=(p1, p2,…, pn), где p - цена j-го изделия
(j=1,…,n).
Требуется составить такой план производства х=(х1, х2,…, хn), чтобы при
выполнение условий
|a11x1 + a12x2 + … + a1nxn (|
|b1 |
|a21x1 + a22x2 + … + a2nxn (|
|b2 |
|…………………………….……………………. |
|am1x1 + am2x2 + … + amnxn (|
|bm |
|xj ( 0, (j=1,…,n). |
достигался максимум функции
Z= p1x1 + p2x2 + … + pnxn
Функция Z называется целевой.
i-е ограничение из (1) означает, что нельзя израсходовать i-го
ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество
(. Переменные, удовлетворяющие условию xj(0, называются несвободными. В
нашей задаче это означает, что при xj=0 - ничего не производится или при
xj>0 производится некоторое количество изделий.
Переменные, на которые условия неотрицательности не накладываются,
называются свободными.
Задача (1)-(1') и есть задача оптимального производственного
планирования, решение которой обеспечивает достижение в конкретных условиях
максимальной прибыли.
Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов
по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в
задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для
производства тех же n изделий. При этом количество приобретаемых
ингридиентов определяется вектором b=(b1, b2, …, bm). Задана та же матрица
А, элемент которой aij определяет расход i-го ингридиента для производства
j-го изделия. Кроме того задан вектор цен p=(p1, p2, …, pn) на продукцию
предприятия. Требуется отыскать вектор цен ингридиентов u=(u1, u2, …, um),
где ui - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись
условия:
|a11u1 + a21u2 + … + am1um (|
|p1 |
|a12u1 + a22u2 + … + am2um (|
|p2 |
|…………………………….……………………. |
|a1nu1 + a2nu2 + … + amnum (|
|pn |
|ui ( 0, (i=1,…,m) |
при достижении минимума целевой функции
W=b1u1 + … + bmum
j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на
производство j-го изделия, не меньше рыночной цены этого изделия.
Условие несвободности uj(0 означает, что j-й ингредиент либо бесплатен
(uj=0), либо стоит положительное количество рублей (uj >0).
Опорным решением задачи (1)-(1') называется точка множества (, в которой
не менее чем n ограничений из (1) обращается в верное равенство. Это - так
называемая, угловая точка множества. Для n=2 это - вершина плоского угла.
Опорным решением задачи (2)-(2') называется точка, в которой не менее
чем m ограничений из (2) обращается в верное равенство.
В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В
задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не
является.
Опорное решение, доставляющее максимум функции (1') или минимум функции
(2') называется оптимальным. В работе [1] показано, что оптимальное решение
можно всегда искать среди опорных решений.
Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и
равенства. Тогда условимся писать эти равенства первыми. Если их количество
равно k, то область ( запишется в виде:
|a11x1 + a12x2 + … + a1nxn = |
|b1 |
|…………………………….……………………… |
|ak1x1 + ak2x2 + … + aknxn = |
|bk |
|ak+1, 1x1+ak+1, 2x2+…+ak+1, n|
|xn(bk+1 |
|…………………………….……………………… |
|am1x1 + am2x2 + … + amnxn ( |
|bm |
|xj ( 0, (j=1,…,n) |
Требуется найти максимум функции
Z=p1x1 + p2x2 + … + pnxn
В общем случае среди переменных xj могут быть свободные. Номера
свободных переменных будем хранить в отдельном массиве.
При формировании двойственной задачи к задаче (3)-(3') i-му ограничению
- равенству будет соответствовать свободная переменная ui (i=1,…,k), а
свободной переменной xj ограничение - равенство:
a1j u1 + a2j u2 + … + amj um =pj
Введем вспомогательные переменные yi(0 (i=1,…,n) и запишем ограничения
(3) и функцию Z в виде:
|0 = a11 (-x1) + a12 (-x2) + … + a1n |
|(-xn) + a1, n+1 |
|…………………………………………………….……………………………………… |
|0 = ak1 (-x1) + ak2 (-x2) + … + akn|
|(-xn) + ak, n+1 |
|yk+1 = ak+1, 1 (-x1) + ak+1, 2(-x2)+ … + ak+1, |
|n(-xn) + ak+1, n+1 |
|…………………………………………………….……………………………………… |
|ym = am1 (-x1) + am2 (-x2) + … + amn(-xn) |
|+ am, n+1 |
|Z = am+1, 1 (-x1) + am+1, 2(-x2)+ … + am+1, |
|n(-xn) + am+1, n+1 |
Условие несвободности отдельных или всех переменных здесь не отмечено.
Обозначения:
ai, n+1 = bi (i=1, …, m),
am+1, j = -pj (j=1, …, n)
am+1, n+1 = 0.
Таким образом, матрицу а мы дополнили столбцом свободных членов и
строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на
противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:
Прямая задача Таблица 1
| |-x1 |-x2 | |-xn |1 |
|0 = |a11 |a12 |… |a1n |a1, n+1|
|…… |…………………………… |……… |
|0 = |.. |ak, n+1|
|yk+1 =|ak1 |ak2 |… |akn |ak+1, |
| | | | | |n+1 |
|…… |ak+1, 1|ak+1, 2|… |ak+1,|……… |
| | | | |n | |
|ym = |…………………………… |……… |
| |am1 |am2 |… |amn |am, n+1|
|Z = |am+1, n|am+1, 2|… |am+1,|am+1, |
| | | | |n |n+1 |
Номера свободных переменных запоминаются отдельно.
Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.
Прямая и двойственная задачи Таблица 2
| | |v1 = |v2 = | |vn = |W = |
| | |-x1 |-x2 | |-xn |1 |
|u1 |0 = |a11 |a12 |… |a1n |a1, n+1 |
| |…… |……………...……………… |……… |
|uk |0 = |ak1 |ak2 |… |akn |ak, n+1 |
|uk+1 |yk+1 =|ak+1, 1|ak+1, 2|… |ak+1,|ak+1, |
| | | | | |n |n+1 |
| |…… |…………………………… |……… |
|um |ym = |am1 |am2 |… |amn |am, n+1 |
|1 |Z = |am+1, n|am+1, 2|… |am+1,|am+1, |
| | | | | |n |n+1 |
vj - вспомогательные переменные двойственной задачи.
Тогда j-е ограничение из таблицы имеет вид:
vj = a1j u1 + a2j u2 + … + amj um + am+1, j ( 0, если xj ( 0
Если переменная xj свободна, то ей соответствует ограничение-равенство
двойственной задачи:
0=a1j u1 + a2j u2 + … + amj um + am+1, j
т.е. вместо vj фактически будет нуль.
Кроме того первые k переменных двойственной задачи свободны, а остальные
несвободны.
Целевая функция двойственной задачи
W= a1, n+1 u1 + a2, n+1 u2 + … + am, n+1 um + am+1, n+1
Совмещение в одной таблице прямой и двойственной задачи неслучайно.
Решая прямую задачу, мы получаем о дновременно решение двойственной задачи,
причем
max Z = min W = am+1, n+1
Сделаем замену переменных в таблице 1 , перебросив вспомогательную
переменную yr на верх таблицы со знаком минус, а основную пременную xs на
бок таблицы (ars(0). Это означает движение из вершины x=(0, …, 0) в другую
вершину многогранника ( по его ребру. Элемент аrs называется разрешающим,
строка r - разрешающей строкой, столбец s - разрешающим столбцом. Такая
замена переменных носит название модифицированных жордановых исключений
(МЖИ). Элементы матрицы а, не принадлежащие разрешающему столбцу или
разрешающей строке, назовем рядовыми.
2.2 Описание исходных данных и результатов решения задачи линейного
программирования.
Обсудим исходные данные (текстовой файл simp.dat) и результаты решения
задачи линейного программирования (текстовой файл simp.res). В начале файла
simp.dat расположены, так называемые, представительские данные - строковые
данные, каждое из которых распологается в файле с новой строки:
1. Строка с номером варианта,
2. Строка с русским названием модуля,
3. Строка с координатами студента (ФИО, факультет, курс, группа),
4. Строка с датой исполнения.
Далее следуют строки файла с числовыми исходными данными:
1. Управляющий вектор kl - отдельная строка состоящая из трёх чисел kl1 ,
kl2 , kl3:
kl1=0, если необходимо получить решение только прямой задачи.
kl1=1, если необходимо получить решение только двойственной задачи.
kl1=2, если необходимо получить решение обеих задач.
kl2=0, если нет свободных переменных, иначе kl2 равен числу этих нуль-
уравнений.
2. Число ограничений и переменных (отдельная строка ввода).
3. Коэффициенты расширенной матрицы a, начиная с отдельной строки ввода.
4. Вектор номеров свободных переменных, если они есть, начиная с отдельной
строки ввода.
Результаты решения зависят от значения kl .
Если kl1=0, то при благоприятном исходе это будет вектор оптимального
решения прямой задачи и оптимальное значение целевой функции. При
неблагоприятном исходе, это одно из сообщений: либо "Система ограничений
несовместна", либо "Целевая функция неограничена".
Если kl2=1, то же для двойственной задачи.
Если kl2=2, то сначала выдается решение прямой, а потом двойственной
задачи. При не благоприятном исходе сообщения справедливы только для прямой
задачи (для двойственной аналогичные сообщения не выдаются). Результаты
помещаются в файл simp.res.
3.2 Описание модуля типов.
Для задания типов и файловых переменных вводного и выводного текстовых
файлов используется модуль типов unit typesm, структура которого приведена
ниже
unit typesm;
interface
const
mmax=20; nmax=20; e=1e-5;
type
klt =array[1..3] of integer;
at =array[1..mmax+1,1..nmax+1] of real;
vec1it =array[1..nmax] of integer;
vec2it =array[1..mmax] of integer;
vec1rt =array[1..nmax] of real;
vec2rt =array[1..mmax] of real;
var
fi, fo:text;
implementation
end.
В разделе констант заданы константы nmax и mmax, задающие максимальное
число строк расширенной матрицы a без единицы, а также пороговая константа
е, используемая в модуле поиска разрешающей строки. Константа е
используется для обеспечения устойчивости алгоритма (модуль разрешающего
элемента не должен быть слишком мал, а именно, больше е).
Ниже приведена таблица фактических и формальных параметров подпрограмм
задач линейного программирования. Обозначения формальных и фактических
параметров совпадают.
|N/N |Назначение |Обозначение |Тип |
|1. |Управляющий вектор |k1 |ki1t |
|2. |Число ограничений |m |intege|
| | | |r |
|3. |Число переменных |n |intege|
| | | |r |
|4. |Матрица коэффициентов |a |at |
|5. |Вектор номеров свободных переменных |i1 |vec1it|
|6. |Отслеживающий вектор основных |p1 |vec1it|
| |переменных прямой задачи | | |
|7. |Отслеживающий вектор вспомогательных|q1 |vec1it|
| |переменных двойственной задачи | | |
|8. |Отслеживающий вектор вспомогательных|p2 |vec2it|
| |переменных прямой задачи | | |
|9. |Отслеживающий вектор основных |q2 |vec2it|
| |переменных двойственной задачи | | |
|10. |Разрешающая строка |r |intege|
| | | |r |
|11. |Разрешающий столбец |s |intege|
| | | |r |
|12. |Вектор-решение прямой задачи |x |vec1rt|
|13. |Вектор-решение двойственной задачи |u |vec2rt|
4.2 Укрупненная блок-схема задачи линейного программирования.
[pic]
5.2 Параметры и заголовки процедур задачи линейного программирования.
В основной программе используются следующие переменные, которые описаны
в разделе var:
m,n,r,s:integer;{числовые переменные целого типа}
Процедуры программы:
|N/N |Назначение |Заголовок |
|1. |Ввод и контроль исходных |input(var k1:k1t; var |
| |данных и вывод их в файл |m,n:integer; var a:at, var |
| |результатов |i1:vec1it; var p1,q1:vec1it; |
| | |var p2,q2:vec2it) |
|2. |Исключение свободных |issp(var k1:k1t; m,n:integer; |
| |переменных |var a:at; var i1,p1,q1:vec1it;|
| | |var p2,q2: vec2it) |
|3. |Исключение нуль-уравнений |isnu(var k1:k1t; m,n:integer; |
| | |var a:at; var p1,q1:vec1it; |
| | |var p2,q2: vec2it) |
|4. |Поиск опорного решения |opor(m,n:integer; var a:at; |
| | |var p1,q1:vec1it; var p2,q2: |
| | |vec2it) |
|5. |Поиск оптимального решения |optim(m,n:integer; var a:at; |
| | |var p1,q1:vec1it; var p2,q2: |
| | |vec2it) |
|6. |Вывод решения прямой задачи|outp(m,n:integer; var a:at; |
| | |var p2: vec2it; x:vec1rt) |
|7. |Вывод решения двойственной |outd(m,n:integer; var a:at; |
| |задачи |var q1: vec1it; u:vec2rt) |
|8. |МЖИ |mji ( m,n:integer; var a:at; |
| | |r,s:integer) |
|9. |Поиск разрешающей строки |nstro(m,n:integer; var a:at; |
| | |r,s:integer var p2:vec2it) |
6.2 Блок-схема и параметры реализованной процедуры.
Обращащение: isnu(k1,m,n,a,p1,q1,p2,q2). Используются модули typesm,
mjim.
Параметры подпрограммы isnu:
|Наименование |Обозначение |
|Число ограничений |m |
|Число переменных |n |
|Матрица задачи |a |
|Отслеживающие векторы |p1, q1, p2, q2 |
В итоге успешной работы алгоритма все нуль-уравнения будут исключены, и
в отслеживающем векторе p1 это будет отмечено как -1, что даст возможность
в дальнейшем соответствующие столбцы матрицы А при выборе разрешающего
элемента не трогать. Если же алгоритм применить нельзя, то будет выдано
сообщение (см. блок-схему), и работа программы закончится.
7.2 Листинг модуля, исходных данных и результатов машинного расчета.
unit isnum;
interface
uses typesm,mjim;
procedure isnu(var k1:k1t;m,n:integer; var a:at;
var p1,q1:vec1it; var p2,q2:vec2it);
implementation
procedure isnu;
var p:real;k,s,r,j,t:integer;
begin
for r:=1 to k do begin
if p2[r]0 then begin
if abs(a[r,j])>p then begin p:=abs(a[r,j]);s:=j;end;
end;end;
if p=0 then begin writeln(fo,'Исключить r',r:6,'-ое нуль-уравнение
нельзя');
close(fi);close(fo);halt end;
mji(m,n,a,r,s);
p2[r]:=p1[s];p1[s]:=-1;
t:=q2[r];q2[r]:=q1[s];q1[s]:=t;
end;
end.
Исходный файл simp.dat:
12
Исключение нуль-уравнений
Моносов ЭОУС-1-2 преподаватель Марьямов А. Г.
12.05.98
2 2 0
5 3
-2 -1 1 -2
1 -1 0 -1
-1 -1 0 -2
0 1 0 2
2 1 0 4
4 4 0 0
1 2
Файл результатов simp.res:
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ
КАФЕДРА ИНФОРМАТИКИ И ПРИКЛАДНОЙ МАТЕМАТИКИ
Лабораторная работа по информатике
Факультет ЭОУС, 2-ой семестр обучения
Решение задачи линейного программирования
Вариант 12
модуль: Исключение нуль-уравнений
Исполнил студент Моносов ЭОУС-1-2 преподаватель Марьямов А. Г.
Дата исполнения: 12.05.98
Управляющий вектор:
2 2 0
Число ограничений: 5
Число переменных: 3
Матрица задачи
Н-р Коэффициенты Св. члены
строки
1 -2.00000 -1.00000 1.00000 -2.00000
2 1.00000 -1.00000 0.00000 -1.00000
3 -1.00000 -1.00000 0.00000 -2.00000
4 0.00000 1.00000 0.00000 2.00000
5 2.00000 1.00000 0.00000 4.00000
6 4.00000 4.00000 0.00000 0.00000
Вектор номеров свободных переменных:
1 2
Вектор решения прямой задачи:
1.00000 2.00000 3.00000
Значение целевой функции прямой задачи= 12.00000
Вектор решения двойственной задачи:
0.00000 4.00000 0.00000 8.00000 0.00000
Значение целевой функции двойственной задачи= 12.00000
8.2 Ручной расчет задачи линейного программирования.
Требуется максимизировать функцию
z=4x1+5x2
при ограничениях:
-2x1-x2+x3=-2
x1-x2( -1
- x1 - x2 ( -2
0x1+ 1x2 ( 2
2x1 + 1x2 ( 4
x3 ( 0
Коэфициенты ограничений, записанных в таком виде, переписываются со
своими знаками, в последней строке таблицы записываются коэффициенты
целевой функции с противоположными знаками. Сперва следует исключить
свободные переменные, перекинув их на бок таблицы:
| |-x1 |-x2 |-x3 |1 |
|0= |-2 |-1 |1 |-2 |
|y2= |1 |-1 |0 |-1 |
|y3= |-1 |-1 |0 |-2 |
|y4= |0 |1 |0 |2 |
|y5= |2 |1 |0 |4 |
|z= |-4 |-4 |0 |0 |
| |-x1 |-y4 |-x3 |1 |
|0= |-2 |1 |1 |0 |
|y2= |1 |1 |0 |1 |
|y3= |-1 |1 |0 |0 |
|*x2= |0 |1 |0 |2 |
|y5= |2 |-1 |0 |2 |
|z= |-4 |4 |0 |8 |
| |-y2 |-y4 |-x3 |1 |
|0= |-2 |3 |1 |2 |
|*x1= |1 |1 |0 |1 |
|y3= |-1 |2 |0 |0 |
|*x2= |0 |1 |0 |2 |
|y5= |2 |-3 |0 |0 |
|z= |4 |8 |0 |12 |
После этого следует исключить нуль-уравнение:
| | | |* | |
| |-y2 |-y4 |-y1 |1 |
|x3= |-2 |3 |1 |2 |
|*x1= |1 |1 |0 |1 |
|y3= |-1 |2 |0 |0 |
|*x2= |0 |1 |0 |2 |
|y5= |2 |-3 |0 |0 |
|z= |4 |8 |0 |12 |
Мы видим, что свободные члены в непомеченных строках неотрицательны,
следовательно опорное решение получено и надо перейти к поиску оптимального
решения. Находим непомеченные столбцы с отрицательными коэфициентами
целевой функции, исключая последний. У нас таких нет, поэтому оптимальное
решение получено и переходим к извлечению результатов. Для этого составим
еще одну таблицу, где содержаться переменные прямой и двойственной задач.
Для извлечения решений нужны только столбец свободных членов и строка
коэффициентов целевой функции. Поэтому внутренняя часть таблицы не
преведена.
| | |u2= |u4= |u1= |w= |
| | |-y2 |-y4 |-y1 |1 |
|v3= |x3= |-2 |3 |1 |2 |
|v1= |x1= |1 |1 |0 |1 |
|u3= |y3= |-1 |2 |0 |0 |
|v2= |x2= |0 |1 |0 |2 |
|u5= |y5= |2 |-3 |0 |0 |
|1 |z= |4 |8 |0 |12 |
В итоге получаем следующие результаты:
1. Прямая задача. Переменные прямой задачи, находящиеся сверху таблицы
равны в решении 0, а сбоку - соответствующим свободным членам:
x1=1; x2=2; x3=2.
2. Двойственная задача. Переменные двойственной задачи, находящиеся сверху
таблицы равны 0, а сбоку - соответствующим коэфициентам целевой функции:
u1=0; u2=4; u3=0; u4=8; u5=0.
Значение целевых функций обеих задач zmax= wmin=12.
9.2 Выводы.
Полученные результаты при ручном расчёте совпадают с данными машинного
счёта. Это подтверждает правильность составления алгоритма и написания
программы.
Список использованной литературы.
. Турчак Л. И. "Основы численных методов".
. Марьямов А. Г. "Применение модульного способа програмирования в среде
Turbo Pascal 7.0 с целью решения полной задачи линейного
программирования".
-----------------------
C1j=C1j+Ri
Bj=Bj+Ri*Yi
C1j=0, Bj=0
Ri=1
Ввод
n, m, X, Y
Y0 Y1 . . . Yn
Y
X
X0 X1 . . . Xn
Ri=Ri*Xi
Ci+1, j=Ci, j+1
Ci+1, m+1=0
Ci+1, m+1=Ci+1, m+1 +Rj
Rj=Rj*Xj
Решение системы линейных уравнений Gauss(m+1,C,B,A)
Zi=0
Zi=Zi*Xi+Aj
Zi=Zi*Yi
K
Вывод A, Z
i=1
i=n
j=1
j=m+1
Расчет первой строки матрицы С и вектора В
i=1
i=n
i=1
i=n
i=1
i=m
j=1
j=m
j=1
j=n
j=1
j=n
i=1
i=n
j=m+1
j=1
шаг=-1
Расчет остальных строк матрицы С
(1)
(1')
(2)
(2')
(3)
(3')
(4)
{
{
{
p1(|p2r|)=-1
p2r0
|arj|>p
p=|arj| s=j
P=0
MJI(m,n,a,r,s)
p2r=p1s p1s=-1
t=q2r q2r=q1s q1s=t
B
"Искл. r-ое нуль-ур. Нельзя"
Закрыть файлы
К
r=1
r=k
да
нет
j=1
j=n
нет
нет
да
да
да
нет
=
| |
