|
Реферат: Представление об информационном обществе и этапы развития информационных технологий (Кибернетика)
Содержание
ПРЕДСТАВЛЕНИЕ ОБ ИНФОРМАЦИОННОМ ОБЩЕСТВЕ 2
РОЛЬ ИНФОРМАТИЗАЦИИ В РАЗВИТИИ ОБЩЕСТВА 2
Роль и значение информационных революций 2
Об информации, информатизации и защите информации 6
Глава 4. Информатизация, информационные системы, технологии и средства
их обеспечения 6
КАЧЕСТВЕННЫЕ ИЗМЕНЕНИЯ В ИТ 7
ТРИ КАЧЕСТВЕННЫХ СКАЧКА В ИТ - ТРИ ВЕЛИКИХ ФЕНОМЕНА 8
ЭТАПЫ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ 8
ПРЕДСТАВЛЕНИЕ ОБ ИНФОРМАЦИОННОМ ОБЩЕСТВЕ
РОЛЬ ИНФОРМАТИЗАЦИИ В РАЗВИТИИ ОБЩЕСТВА
Что такое процесс информатизации общества
Деятельность отдельных людей, групп, коллективов и организаций сейчас все в
большей степени начинает зависеть от их информированности и способности
эффективно использовать имеющуюся информацию. Прежде чем предпринять какие-
то действия, необходимо провести большую работу по сбору и переработке
информации, ее осмыслению и анализу. Отыскание рациональных решений в любой
сфере требует обработки больших объемов информации, что подчас невозможно
без привлечения специальных технических средств.
Возрастание объема информации особенно стало заметно в середине XX в.
Лавинообразный поток информации хлынул на человека, не давая ему
возможности воспринять эту информацию в полной мере. В ежедневно
появляющемся новом потоке информации ориентироваться становилось все
труднее. Подчас выгоднее стало создавать новый материальный или
интеллектуальный продукт, нежели вести розыск аналога, сделанного ранее.
Образование больших потоков информации обусловливается:
o чрезвычайно быстрым ростом числа документов, отчетов,
диссертаций, докладов и т.п., в которых излагаются результаты
научных исследований и опьггно-конструкторских работ;
o постоянно увеличивающимся числом периодических изданий по рыным
областям человеческой деятельности;
o появлением разнообразных данных (метеорологических,
геофизических, медицинских, экономических и др.), записываемых
обычно на магнитных лентах и поэтому не попадающих в сферу
действия системы коммуникации.
Роль и значение информационных революций
В истории развития цивилизации произошло несколько информационных революций
– преобразований общественных отношений из-за кардинальных изменений в
сфере обработки информации. Следствием подобных преобразований являлось
приобретение человеческим обществом нового качества.
Первая революция связана с изобретением письменности, что привело к
гигантскому качественному и количественному скачку. Появилась возможность
передачи знаний от поколения к поколениям.
Вто р а я (середина XVI в.) вызвана изобретением книгопечатания, которое
радикально изменило индустриальное общество, культуру, организацию
деятельности.
Т р е т ь я (конец XIx в.) обусловлена изобретением электричества,
благодаря которому появились телеграф, телефон, радио, позволяющие
оперативно передавать и накапливать информацию в любом объеме.
Ч е т в е р т а я (70-е гг. XX в.) связана с изобретением микропроцессорной
технологии и появлением персонального компьютера. На микропроцессорах и
интегральных схемах создакугся компьютеры, компьютерные сети, системы
передачи данных (информационные коммуникации). Этот период характеризуют
три фундаментальные инновации:
. переход от механических и электрических средств преобразования
информации к электронным;
. миниатюризация всех узлов, устройств, приборов, машин;
. создание программно-управляемых устройств и процессов.
Для создания более целостного представления об эом периоде целесообразно
позна-
комигься с приведенной ниже справкой о смене поколений электронно-
вычислительных машин (ЭВМ) и сопоставить эти сведения с этапами в области
обработки и передачи информацин.
Справка о смене поколений ЭВМ. 1-е поколение (начало 50-x
гг.). Элементная база – электронные лампы. ЭВМ отличались
большими габаритами, большим потреблением энергии, малым
быстродействием, низкой надежностъю, программированием в
кодах.
2-е поколение (с конца 50-x гг. ). Элементная баа –
полупроводниковые элеменгы. Улучшились по сравнению с ЭВМ
предыдущего поколения все технические характеристики. Для
программирования используются алгоритмические языки.
3-е поколение (начало бо-х гт.). Элементная база –
интегральные схемы, многослойный печатный монтаж. Резкое
снижение габаритов ЭВМ, повышение их надежности, увеличение
производительности. Доступ с удаленных терминалов.
4-е поколение (с середины 70-x гг.). Элементняя бма –
микропроцессоры, большие интегральные схемы. Улучшились
технические характеристики. Массовый выпуск персональных
компьютеров. Направления развития: мощные многопроцессорные
вычислительные системы с высокой производигельностью,
создание дешевых микроЭВМ.
5-е поколение (с середины 80-х гг.). Началась разработка
интеллектуальных компьютеров, пока не увенчавшаяся успехом.
Внедрение во все сферы компьютерных сетей и их объединение,
использование распределенной обработки данных, повсеместное
применение компьютерных информационных технологий.
Последняя информационная революция выдвигает на первый план новую отрасль –
информационную индустрию, связанную с производством технических средств,
методов, технологий для производства новых знаний. Важнейшими составляющими
информационной индустрии становятся все виды информационных технологий,
особенно телекоммуникации. Современная информационная технология опирается
на достижения в области компьютерной техники и средств связи.
Информационная технология (ИТ) – процесс, использующий
совокупность средств и методов сбора, обработки и передачи
данных (первичной информации) для получения информации
нового качества о состоянии объекта, процесса или явления.
Телекоммуникации – дистанционная передача данных на базе
компьютерных сетей и современных технических средств связи.
Примечание. Подробный анализ видов информационных
технологий рассмотрен в подразд. 3.3 и 3.4.
Усложнение индустриального производства, социальной, экономической и
политической жизни, изменение динамики процессов во всех сферах
деятельности человека привели, с одной стороны, к росту потребностей в
знаниях, а с другой – к созданию новых средств и способов удовлетворения
этих потребностей.
Бурное развитие компьютерной техники и информационных технологий послужило
толчком к развитию общества, построенного на использовании различной
информации и получившего название информационного общества.
Как понимают ученые информационное общество
Японские ученые считают, что в информационном обществе процесс
компьютеризации даст людям доступ к надежным источникам информации, избавит
их от рутинной работы, обеспечит высокий уровень автоматизации обработки
информации в производственной и социальной сферах. Движущей силой развития
общества должно стать производство информационного, а не материального
продукта. Материальный же продукт ствнет более информационно емким, что
означает увеличение доли инноваций, дизайна и маркетинга в его стоимости.
В информационном обществе изменятся не только производство, но и весь уклад
жизни, система ценностей, возрастет значимость культурного досуга по
отношению к материальным ценностям. По сравнению с индустриальным
обществом, где все направлено на производство и потребление товаров, в
информационном обществе производятся и потребляются интеллект, знания, что
приводит к увеличению доли умственного труда. От человека потребуется
способность к творчеству, возрастет спрос на знания.
Материальной и технологической базой информационного общества станут
различного рода системы на базе компьютерной техники и компьютерных сетей,
информационной технологии, телекоммуникационной связи.
Информационное общество – общество, в котором большинство
работающих занято производством, хранением, переработкой и
реализацией информации, особенно высшей ее формы – знаний.
В реальной практике развития науки и техники передовых стран в конце XX в.
постепенно приобретает зримые очертания созданная теоретиками картина
информационного общества. Прогнозируется превращение всего мирового
пространства в единое компьютеризированное и информационное сообщество
людей, проживающих в электронных квартирах и коттеджах. Любое жилище
оснащено всевозможными электронными приборами и компьютеризированными
устройствами. Деятельность людей будет сосредоточена главным образом на
обработке информации, а материальное производство и производство энергии
будет возложено на машины.
Уже опубликован ряд фактических материалов, свидетельствующих, что это не
утопия, а неизбежная реальность недалекого будущего.
Пример 1.1. По данным социологического исследования,
проведенного в США, уже сейчас 27 млн. работающих могут
осуществить свою деятельность, не выходя из дома, а 1/3
всех недавно зарегистрированных фирм основана на широком
использовании самостоятельной занятости. В США к категории
самостоятельно занятых были отнесены: в 1980 г. – 5,7 млн.
человек, в 1989 г. – 14,6 млн., а в 1995 г. – 20,7 млн.
человек.
При переходе к информационному обществу возникает новая индустрия
переработки информации на базе компьютерных и телекоммуникационных
информационных технологий.
Ряд ученых выделяют характерные черты информационного
общества:
o решена проблема информационного кризиса, т.е. разрешено
противоречие между информационной лавиной и информационным
голодом;
o обеспечен приоритет информации по сравнению с другими ресурсами;
o главной формой развития станет информационная экономика;
в основу общества будут заложены автоматизированные
генерация, хранение, обработка и использование знаний с
помощью новейшей информационной техники и техцологии;
o информационная технология приобретет глобальный характер,
охватывая все сферы социальной деятельностй человека;
o формируется информационное единство всей человеческой
цивилизации;
o с помощью средств информатики реализован свободный доступ
каждого человека к информационным ресурсам всей цивилизации;
o реализованы гуманистические принципы управления обществом и
воздействия на окружающую среду.
Кроме положительных моментов прогнозируются и опасные
тенденции:
o все большее влияние на общество средств массовой информации;
o информационные технологии могут разрушить частную жизнь людей и
организаций; существует проблема отбора качественной и
достоверной информации;
o многим людям будет трудно адаптироваться к среде информационного
общества. Существует опасность разрыва между "информационной
элитой" (людьми, занимающимися разработкой информационных
технологий) и потребителями.
Ближе всех на пути к информационному обществу стоят страны с развитой
информационной индустрией, к числу которых следует отнести США, Японию,
Англию, Германию, страны Западной Европы. В этих странах уже давно одним из
направлений государственной политики является направление, связанное с
инвестициями и поддержкой инноваций в информационную индустрию, в развитие
компьютерных систем и телекоммуникаций.
Федеральный закон
20 февраля 1995 года № 24-ФЗ
Принят Государственной Думой25 января 1995 года
Об информации, информатизации и защите информации
Глава 4.
Глава 4. Информатизация, информационные системы, технологии и средства их
обеспечения
Статья 16. Разработка и производство информационных систем, технологий
и средств их обеспечения
Статья 17. Право собственности на информационные системы, технологии и
средства их обеспечения
Статья 18. Право авторства и право собственности на информационные
системы, технологии и средства их обеспечения
Статья 19. Сертификация информационных систем, технологий, средств их
обеспечения и лицензирование деятельности по формированию и
использованию информационных ресурсов
Глава 4. Информатизация, информационные системы, технологии и средства их
обеспечения
Статья 16. Разработка и производство информационных систем, технологий и
средств их обеспечения
1. Все виды производства информационных систем и сетей, технологий и
средств их обеспечения составляют специальную отрасль экономической
деятельности, развитие которой определяется государственной научно-
технической и промышленной политикой информатизации.
2. Государственные и негосударственные организации, а также граждане имеют
равные права на разработку и производство информационных систем, технологий
и средств их обеспечения.
3. Государство создает условия для проведения научно-исследовательских и
опытно-конструкторских работ в области разработки и производства
информационных систем, технологий и средств их обеспечения. Правительство
Российской Федерации определяет приоритетные направления развития
информатизации и устанавливает порядок их финансирования.
4. Разработка и эксплуатация федеральных информационных систем
финансируются из средств федерального бюджета по статье расходов
"Информатика" ("Информационное обеспечение").
5. Органы государственной статистики совместно с Комитетом при Президенте
Российской Федерации по политике информатизации устанавливают правила учета
и анализа состояния отрасли экономической деятельности, развитие которой
определяется государственной научно-технической и промышленной политикой
информатизации.
Статья 17. Право собственности на информационные системы, технологии и
средства их обеспечения
1. Информационные системы, технологии и средства их обеспечения могут быть
объектами собственности физических и юридических лиц, государства.
2. Собственником информационной системы, технологии и средств их
обеспечения признается физическое или юридическое лицо, на средства
которого эти объекты произведены, приобретены или получены в порядке
наследования, дарения или иным законным способом.
3. Информационные системы, технологии и средства их обеспечения включаются
в состав имущества субъекта, осуществляющего права собственника или
владельца этих объектов. Информационные системы, технологии и средства их
обеспечения выступают в качестве товара (продукции) при соблюдении
исключительных прав их разработчиков. Собственник информационной системы,
технологии и средств их обеспечения определяет условия использования этой
продукции.
Статья 18. Право авторства и право собственности на информационные системы,
технологии и средства их обеспечения
Право авторства и право собственности на информационные системы, технологии
и средства их обеспечения могут принадлежать разным лицам. Собственник
информационной системы, технологии и средств их обеспечения обязан защищать
права их автора в соответствии с законодательством Российской Федерации.
Статья 19. Сертификация информационных систем, технологий, средств их
обеспечения и лицензирование деятельности по формированию и использованию
информационных ресурсов
1. Информационные системы, базы и банки данных, предназначенные для
информационного обслуживания граждан и организаций, подлежат сертификации в
порядке, установленном Законом Российской Федерации "О сертификации
продукции и услуг".
2. Информационные системы органов государственной власти Российской
Федерации и органов государственной власти субъектов Российской Федерации,
других государственных органов, организаций, которые обрабатывают
документированную информацию с ограниченным доступом, а также средства
защиты этих систем подлежат обязательной сертификации. Порядок сертификации
определяется законодательством Российской Федерации.
3. Организации, выполняющие работы в области проектирования, производства
средств защиты информации и обработки персональных данных, получают
лицензии на этот вид деятельности. Порядок лицензирования определяется
законодательством Российской Федерации.
4. Интересы потребителя информации при использовании импортной продукции в
информационных системах защищаются таможенными органами Российской
Федерации на основе международной системы сертификации.
[pic]
Президент Российской Федерации Б.Ельцин
Москва, Кремль.
20 февраля 1995 года. № 24-ФЗ
[pic]
Закон опубликован:
20 февраля 1995 года, "Собрание законодательства РФ", № 8
22 февраля 1995 года, "Российская газета", № 39
КАЧЕСТВЕННЫЕ ИЗМЕНЕНИЯ В ИТ
В 80-х годах произошел целый ряд качественных изменений в ИТ. Некоторые из
них осознавались постепенно (например, развитие архитектуры и стандартов
открытых систем), другие, как феномен персональных вычислений, входили в
жизнь гораздо более революционным путем. Кратко рассмотрим, как эти
изменения все более ограничивали применение классических методов системного
проектирования, требуя новых подходов в разработке чисто "компьютерных"
компонентов ИС. Далее, во второй части будет рассмотрено, как эти изменения
помогали также появлению BPR.
ТРИ КАЧЕСТВЕННЫХ СКАЧКА В ИТ - ТРИ ВЕЛИКИХ ФЕНОМЕНА
Наконец, к концу 80-х - началу 90-х во всем мире не только разработчиками,
но и пользователями были осознаны три действительно революционных феномена.
Они стали все шире входить в отечественную практику, качественно меняя
деятельность компьютеризованных предприятий:
1.Феномен персональных вычислений, основанный на постоянной доступности
работнику возможностей ЭВМ, в первую очередь - на использовании
персональных компьютеров. Феномен состоит в том, что во многих видах
информационных, проектных и управленческих работ исчезла необходимость в
работниках-исполнителях (машинистках, чертежниках, делопроизводителях и
др.), являющихся посредниками между постановкой задачи и ее решением.
2.Феномен кооперативных технологий, состоящий в компьютерной поддержке
совместной согласованной работы группы работников над одним проектом. Этот
феномен возник на основе суммы методов, обеспечивающих управление доступом
членов группы к разным частям проекта, управление версиями и редакциями
проектной документации и согласованным выполнением работ в последовательной
процедуре работ, управление параллельным конструированием и др.
3.Феномен компьютерных коммуникаций, состоящий в резком увеличении
возможностей обмена любой информацией. Он возник, в частности, на основе
стандартизованных протоколов обмена данными прикладного уровня в локальных
и глобальных сетях. Это позволило исключить необходимость передачи бумажных
документов для получения согласия или содержательных замечаний, ненужные
переезды для проведения совещаний, обеспечить постоянную готовность
работника получить и отослать сообщение или информативные записи данных вне
зависимости от места его географического расположения и др.
Оценка их влияния на производственную деятельность и оргструктуры,
разработка соответствующих методик производились не только за рубежом, но и
отечественными специалистами, хотя тогда у нас время реального применения
этих методов еще не настало.
ЭТАПЫ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Существует несколько точек зрения на развитие информационных технологий с
использованием компьютеров, которые определяются различными признаками
деления.
Общим для всех изложенных ниже подходов является то, что с появлением
персонального компьютера начался новый этап развития информационной
технологии. Основной целью становится удовлетворение персональных
информационных потребностей человека как для профессиональной сферы, так и
для бытовой.
Признак деления – вид задач и процессов обработки информации.
1 - й э т а п (60 – 70-е гг.) – обработка данных в вычислительных центрах в
режйме коллективного пользования. Основным направлением развития
информационной технологии являлась автоматизация операционных рутинных
действий человека.
2- й э т а п (с 80-х гг.) – создание информационных технологий,
направленных на решение стратегических задач.
Признак деления – проблемы, стоящие на пути
информатизации общества
1-й этап (до конца 60-х гг.) характеризуется проблемой обработки больших
объемов данных в условиях ограниченных возможностей аппаратных средств.
2 - й э т а п (до конца 70-х гг.) связывается с распространением ЭВМ серии
IBM/360. Проблема этого этапа – отставание программного обеспечения от
уровня развития аппаратных средств.
3 - й э т а п (с начала 80-х гг.) – компьютер становится инструментом
непрофессионального пользователя, а информационные системы – средством
поддержки принятия его решений. Проблемы – максимальное удовлетворение
потребностей пользователя и создание соответствующего интерфейса работы в
компьютерной среде.
4 - й э т а п ( с начала 90-х гг.) – создание современной технологии
межорганизационных связей и информационных систем. Проблемы этого этапа
весьма многочисленны. Наиболее существенными из них являются:
o выработка соглашений и установление стандартов, протоколов для
компьютерной связи;
o организация доступа к стратегической информации;
o организация защиты и безопасности информации.
Признак деления – преимущество, которое приносит
компьютерная технология
1- й этап (с начала 60-х гг.) характеризуется довольно эффективной
обработкой информации при выполнении рутинных операций с ориентацией на
централизованное коллективное использование ресурсов вычислительных
центров. Основным критерием оценки эффективности создаваемых информационных
систем была разница между затраченными на разработку и сэкономленными в
результате внедрения средствами. Основной проблемой на этом этапе была
психологическая – плохое взаимодействие пользователей, для которых
создавались информационные системы, и разработчиков из-за различия их
взглядов и понимания решаемых проблем. Как следствие этой проблемы,
создавались системы, которые пользователи плохо воспринимали и, несмотря на
их достаточно большие возможности, не использовали в полной мере.
2-й этап (с середины 70-х гг.) связан с появлением персональных
компьютеров. Изменился подход к созданию информационных систем – ориентация
смещается в сторону индивидуального пользователя для поддержки принимаемых
им решений. Пользователь заинтересован в проводимой разработке,
налаживается контакт с разработчиком, возникает взаимопонимание обеих групп
специалистов. На этом этапе используется как централизованная обработка
данных, характерная для первого этапа, так и децентрализованная,
базирующаяся на решении локальных задач и работе с локальными базами данных
на рабочем месте пользователя.
3- й этап ( с начала 90-х гг.) связан с понятием анализа стратегических
преимуществ в бизнесе и основан на достижениях телекоммуникационной
технологии распределенной обработки информации. Информационные системы
имеют своей целью не просто увеличение эффективности обработки данных и
помощь управленцу. Соответствующие информационные технологии должны помочь
организации выстоять в конкурентной борьбе и получить преимущество.
Признак деления – виды инструментария технологии
1 - й э т а п (до второй половины XIX в.) – "ручная" информационная
технология, инструментарий которой составляли: перо, чернильница, книга.
Коммуникации осуществлялись ручным способом путем переправки через почту
писем, пакетов, депеш. Основная цель технологии – представление информации
в нужной форме.
2- й этап (с конца XIX в.) – "механическая" технология, инструментарий
которой составляли: пишущая машинка, телефон, диктофон, оснащенная более
совершенными средствами доставки почта. Основная цель технологии –
представление информации в нужной форме более удобными средствами.
3 - й э т а п (40 – 60-е гг. XX в.) – "электрическая" технология,
инструментарий которой составляли: большие ЭВМ и соответствующее
программное обеспечение, электрические пишущие машинки, ксероксы,
портативные диктофоны.
Изменяется цель технологии. Акцент в информационной технологии начинает
перемещаться с формы представления информации на формирование ее
содержания.
4- й э т а п (с начала 70-х гг.) – "электронная" технология, основным
инструментарием которой становятся большие ЭВМ и создаваемые на их базе
автоматизированные системы управления (АСУ) и информационно-поисковые
системы (ИПС), оснащенные широким спектром базовых и специализированных
программных комплексов. Центр тяжести технологии еще более смещается на
формирование содержательной стороны информации для управленческой среды
различных сфер общественной жизни, особенно на организацию аналитической
работы. Множество объективных и субъективных факторов не позволили решить
стоящие перед новой концепцией информационной технологии поставленные
задачи. Однако был приобретен опыт формирования содержательной стороны
управленческой информации и подготовлена профессиональная, психологическая
и социальная база для перехода на новый этап развития технологии.
5 - й э т а п (с середины 80-х гг.) – "комиыотерная" ("новая") технология,
основным инструментарием которой является персональный компьютер с широким
спектром стандартных программных продуктов разного назначения. На этом
этапе происходит процесс персонализации АСУ, который проявляется в создании
систем поддержки принятия решений определенными специалистами. Подобные
системы имеют встроенные элементы анализа и интеллекта для разных уровней
управления, реализуются на персональном компьютере и используют
телекоммуникации. В связи с переходом на микропроцессорную базу
существенным изменениям подвергаются и технические средства бытового,
культурного и прочего назначений. Начинают широко использоваться в
различных областях глобальные и локальные компьютерные сети.
БИБЛИОГРАФИЯ
Федеральный закон от 20 февраля 1995 года № 24-ФЗ «Об информации,
информатизации и защите информации»
Также в данном реферате мною были использованы данные электронных журналов
опубликованных на страничке сервера http://students.informika.ru/ - Каталог
для студентов.
ВТиТФ
Антонов Владимир Фиохарович
студентка группы КТПОП 993 Лахмотова Ольга Валентиновна
Реферат на тему: Применение метода ветвей и границ для задач календарного планирования
ФИНАНСОВАЯ АКАДЕМИЯ ПРИ ПРАВИТЕЛЬСТВЕ РФ
КАФЕДРА МТЕМАТИКИ
КУРСОВАЯ РАБОТА
тема:
Применение метода ветвей и границ для задач календарного планирования
Студент группы МЭК 1-1 Клеймёнов И.Д.
Научный руководитель Солодовников А.С.
МОСКВА, 2001г.
План
1.Постановка задачи целочисленного программирования 3
2. Понятие о методе ветвей и границ 4
3.Применение метода ветвей и границ для задач календарного планирования
13
Летература 20
1.Постановка задачи целочисленного программирования
По смыслу значительной части экономических задач, относятся к задачам
линейного программирования, компоненты решения должны выражаться в целых
числах, т.е. быть целочисленными. К ним относятся, например, задачи, в
которых переменные означают количество единиц неделимой продукции, число
станков при загрузке оборудования, число судов при распределениях по
линиям, число турбин в энергосистеме, число вычислительных машин в
управляющем комплексе и многие другие.
Задача линейного целочисленного программирования формируется следующим
образом: найти такое решение (план) X = (x1,x2,...,xn), при котором
линейная функция
[pic] (1)
принимает максимальное или минимальное значение при
ограничениях
[pic]=bi , i=1, 2…, m. (2)
хj ( 0, j=1, 2,..., п. (3)
xj — целые числа (4)
2. Понятие о методе ветвей и границ
Метод ветвей и границ — один из комбинаторных методов. Его суть
заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из
них, которые оказываются по определенным признакам перспективными, и
отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений
(планов) некоторым способом разбивается на подмножества, каждое из которых
этим же способом снова разбивается на подмножества. Процесс продолжается до
тех пор, пока не получено оптимальное целочисленное решение исходной
задачи.
Алгоритм решения:
Первоначально находим симплексным методом или методом искусственного
базиса оптимальный план задачи без учета целочисленности переменных. Пусть
им является план X0. Если среди компонент этого плана нет дробных чисел, то
тем самым найдено искомое решение данной задачи и Fmax = F(Xo).
Если же среди компонент плана X0 имеются дробные числа, то X0 не
удовлетворяет условию целочисленности и необходимо осуществить
упорядоченный переход к новым планам, пока не будет найдено решение задачи.
Покажем, как это можно сделать, предварительно отметив, что F(X0) ( F(X)
для всякого последующего плана X.
Предполагая, что найденный оптимальный план X0 не удовлетворяет условию
целочисленности переменных, тем самым считаем, что среди его компонент есть
дробные числа. Пусть, например, переменная [pic] приняла в плане X0 дробное
значение. Тогда в оптимальном целочисленном плане ее значение будет по
крайней мере либо меньше или равно ближайшему меньшему целому числу[pic],
либо больше или равно ближайшему большему целому числу [pic] + 1. Определяя
эти числа, находим симплексным методом решение двух задач линейного
программирования:
Найдем решение задач линейного программирования (I) и (II). Очевидно,
здесь возможен один из следующих четырех случаев:
1. Одна из задач неразрешима, а другая имеет целочисленный
оптимальный план. Тогда этот план и значение целевой функции на нем и дают
решение исходной задачи.
2. Одна из задач неразрешима, а другая имеет оптимальный план, среди
компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и
в ее оптимальном плане выбираем одну из компонент, значение которой равно
дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный
план, а в оптимальном плане другой задачи есть дробные числа. Тогда
вычисляем значения целевой функции на этих планах и сравниваем их между
собой. Если на целочисленном оптимальном плане значение целевой функции
больше или равно ее значению на плане, среди компонент которого есть
дробные числа, то данный целочисленный план является оптимальным для
исходной задачи и он вместе со значением целевой функции на нем дает
искомое решение.
Если же значение целевой функции больше на плане, среди компонент которого
есть дробные числа, то следует взять одно из таких чисел и для задачи, план
которой рассматривается, необходимо построить две задачи, аналогичные (I) и
(II).
4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть
дробные числа. Тогда вычисляем значение целевой функции на данных
оптимальных планах и рассматриваем ту из задач, для которой значение
целевой функции является наибольшим. В оптимальном плане этой задачи
выбираем одну из компонент, значение которой является дробным числом, и
строим две задачи, аналогичные (I) и (II).
Таким образом, описанный выше итерационный процесс может быть представлен в
виде некоторого дерева, на котором исходная вершина отвечает оптимальному
плану Х0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает
оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои
ветвления. При этом на каждом шаге выбирается та вершина, для которой
значение функции является наибольшим. Если на некотором шаге будет получен
план, имеющий целочисленные компоненты, и значение функции на нем окажется
больше или равно, чем значение функции в других возможных для ветвления
вершинах, то данный план является оптимальным планом исходной задачи
целочисленного программирования и значение целевой функции на нем является
максимальным.
Итак, процесс нахождения решения задачи целочисленного программирования (1)-
(4) методом ветвей и границ включает следующие основные этапы:
1°. Находят решение задачи линейного программирования (1)-(3).
2°. Составляют дополнительные ограничения для одной из пере-менных,
значение которой в оптимальном плане задачи (1)-(3) является дробным
числом.
3°. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3)
в результате присоединения дополнительных ограничений.
4°. В случае необходимости составляют дополнительные ограничения для
переменной, значение которой является дробным, формулируют задачи,
аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс
продолжают до тех пор, пока не будет найдена вершина, соответствующая
целочисленному плану задачи (1)-(3) и такая, что значение функции в этой
вершине больше или равно значению функции в других возможных для ветвления
вершинах.
Описанный выше метод ветвей и границ имеет более простую логическую схему
расчетов, чем метод Гомори. Поэтому в большинстве случаев для нахождения
решения конкретных задач целочисленного программирования с использованием
ЭВМ применяется именно этот метод.
Проиллюстрируем метод ветвей и границ на примере.
Решить задачу
Z = Зх1 + х2 — max
при ограничениях:
4xl + Зх2 < 18,
x1 + 2x2 ( 6,
0 ( x1 ( 5,
0 ( x2 ( 4,
х1, x2 — целые числа.
Решение. За нижнюю границу линейной функции примем, например, ее значение
в точке (0,0), т.е. Z0 = Z (0; 0) = 0.
I этап. Решая задачу симплексным методом, получим Zmax = 13 при Х1* = (4,5;
0; 0; 1,5; 0,5; 4); так как первая компонента х1* дробная, то из области
решения исключается полоса, содержащая дробное оптимальное значение х1*,
т.е. 4 < х1 < 5. Поэтому задача 1 разбивается на две задачи 2 и 3:
Задача 2
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18
x1 + 2x2 ( 6
0 ( x1 ( 4
0 ( x2 ( 4
х1, x2 — целые числа.
Задача 3
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18
x1 + 2x2 ( 6
5 ( x1 ( 5
0 ( x2 ( 4
х1, x2 — целые числа.
Список задач: 2 и 3. Нижняя граница линейной функции не изменилась: Z0=
0.
II этап. Решаем (по выбору) одну из задач списка, например задачу 3
симплексным методом.
Получим, что условия задачи 3 противоречивы.
III этап. Решаем задачу 2 симплексным методом. Получим Zmax = 14/3 при
X3*= (4; 2/3; 0; 2/3; 0; 10/3). Хотя Z(X3*) = 14/3 > Z0 = 0, по-прежнему
сохраняется Z0 = 0, ибо план нецелочисленный. Так как х2* — дробное
число, из области решений исключаем полосу 0 < x2 < 1 и задачу 2 разбиваем
на две задачи 4 и 5.
Задача 4
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18
x1 + 2x2 ( 6
0 ( x1 ( 4
0 ( x2 ( 0
х1, x2 — целые числа.
Задача 5
Z=3x1+x2>max
при ограничениях:
4xl + Зх2 < 18
x1 + 2x2 ( 6
0 ( x1 ( 4
1 ( x2 ( 4
х1, x2 — целые числа.
Список задач: 4 и 5. Значение Z0 = 0.
IV этап. Решаем задачу 4 симплексным методом.
Получим Zmax = 12 при X4* = (4; 0; 2; 2; 0; 0). Задачу исключаем из списка,
но при этом меняем Z0; Z0 = Z(X4*) = 12, ибо план Х4* целочисленный.
V этап. Решаем задачу 5 симплексным методом.
Получим Zmax = 12,25 при X5* = (3,75; 1; 0; 0,25; 0,25; 0; 3). Z 0 не
меняется, т.е. Z0 = 12, ибо план X5* нецелочисленный. Так как х1* —
дробное, из области решений исключаем полосу 3max
при ограничениях:
4xl + Зх2 < 18
x1 + 2x2 ( 6
4 ( x1 ( 4
1 ( x2 ( 4
х1, x2 — целые числа.
Список задач: 6 и 7. Значение Z0 = 12.
VI этап. Решаем одну из задач списка, например задачу 7, симплексным
методом.
Получим, что условия задачи 7 противоречивы.
VII этап. Решаем задачу 6 симплексным методом.
Получим Zmax = 10,5 ,при X6* = (3; 1,5; 1,5; 0; 0; 0,5; 2,5).
Так какZ(X6*) = 10,5 < Z0 = 12, то задача исключается из списка.
Итак, список задач исчерпан и оптимальным целочисленным решением исходной
задачи будет X* = Х4* = (4; 0; 2; 2; 0; 0), а оптимум линейной функции
Zmax = 12
Замечание 1. Нетрудно видеть, что каждая последующая задача, составляемая в
процессе применения метода ветвей и границ, отличается от предыдущей лишь
одним неравенством — ограничением. Поэтому при решении каждой последующей
задачи нет смысла решать ее симплексным методом с самого начала (с I шага).
А целесообразнее начать решение с последнего шага (итерации) предыдущей
задачи, из системы ограничений которой исключить "старые" (одно или два)
уравнения — ограничения и ввести в эту систему "новые" уравнения —
ограничения.
3.Применение метода ветвей и границ для задач календарного планирования
Метод ветвей и границ является универсальным методом решения
комбинаторных задач дискретного программирования. Сложность практического
применения метода заключается в трудностях нахождения способа ветвления
множества на подмножества и вычисления соответствующих оценок, которые
зависят от специфики конкретной задачи.
Рассмотрим применение разновидности метода ветвей и границ— метода
«последовательного конструирования и анализа вариантов» для решения
задачи календарного планирования трех станков.
Заданы п деталей di (i = 1, 2, ..., n), последовательно
обрабатываемых на трех станках R1, R2, R3, причем технологические
маршруты всех деталей одинаковы. Обозначим ai ,bi ,ci — длительность
обработки деталей di на первом, втором и третьем станках соответственно.
Определить такую очередность запуска деталей в обработку, при которой
минимизируется суммарное время завершения всех работ Tц.
Можно показать, что в задаче трех станков очередность выполнения
первых, вторых и третьих операций в оптимальном решении может быть
одинаковой (для четырех станков это свойство уже не выполняется). Поэтому
достаточно определить очередность запуска только на одном станке
(например, третьем).
Обозначим (k = (i1, i2 , ..., ik) — некоторую последовательность
очередности запуска длиной k (1 ( k ( п) и A ((k), В ((k), С ((k) — время
окончания обработки последовательности деталей (k на первом, втором и
третьем станках соответственно.
Необходимо найти такую последовательность (опт, что
С((опт) = min С (().
(
Покажем, как можно рекуррентно вычислять A ((k), В ((k), С ((k).
Пусть (k+1 = ((k ,ik+i), т. е. последовательность деталей (k+1 получена
из деталей (k с добавлением еще одной детали ik+1. Тогда
A ((k+1) = A ((k)+[pic],
В ((k+1) = max [A ((k+1); В ((k)] + [pic],
С ((k+1) = max [В ((k+1); С ((k)] +[pic]
Для задачи трех станков можно использовать следующее правило
доминирования .
Если ( — некоторая начальная последовательность, а [pic] — под
последовательность образованная из ( перестановкой некоторых символов, то
вариант ( доминирует над [pic], когда выполняются следующие неравенства:
А (() ( А ([pic]), В (() ( В ([pic]), С (() ( С
([pic]),
причем хотя бы одно из них выполняется как строгое неравенство.
Способ конструирования вариантов после-
довательностей ( и вычисления оценок ((() для каждого из них состоит в
следующем.
Пусть имеется начальная подпоследовательность (. Тогда вычисляются
величины:
(C(() = С(() +[pic], (1)
(B(() = В (() +[pic] + min cj , (2)
(A(() = A (() +[pic] + [pic] (3)
где J (() — множество символов, образующих последовательность (.
За оценку критерия С (() для варианта ( можно принять величину
((() = max {(A((), (B ((), (C (()}. (4)
Тогда ход решения задачи трех станков можно представить следующей
формальной схемой.
Нулевой шаг. Задание множества G(0), образуется всеми возможными
последовательностями (( = 0).
Вычисление оценки для множества G0:
где ((0) = max {(A(0), (B (0), бC (0)},
[pic]; [pic]; [pic].
Первый шаг.Образование множеств G1(1) U G1(2) U... …G1(n).
Подмножество Gk определяется всеми последовательностями с началом
ik(k — 1, ...,n ).
Вычисление оценок. Оценку для последовательности (k определяют из
соотношения (4), т. е.
(((k) = max {(A((k), (B ((k), (C ((k)}; k = 1, n.
Выбор варианта для продолжения. Из всех подпоследовательностей,
построенных на предыдущем шаге, выбирают наиболее перспективную
последовательность (k с наименьшей оценкой, т. е.
(((k(1))=min (((j(1)).
Ветвление. Выбрав наиболее перспективный вариант последовательности
(k(1), развивают его построением всех возможных подпоследовательностей
длиной 2 с началом (k(1) вида (k+1(2)= ((k(1), j), где j не входит в
(k.
Вычисление оценок производят в соответствии с соотношениями (1), (2),
(3).
k - ш а г. Допустим, что уже проведено k шагов, в результате чего
построены варианты (1(k), (2(k) ,…,(vk(k), а именно подпоследовательности
длиной k.
Выбираем самый перспективный вариант (S(k) такой, что
(((s(k))=min (((j(k)).
Множество Gs(k) разбиваем на (п — k) подмножеств, каждое из которых
образуется добавлением к последовательности (s(k) некоторого элемента
ik+1 такого, что ik+1[pic].
Оценка [pic] определяется в соответствии с соотношениями (1) — (4).
В результате строим дерево вариантов следующего вида: вершина О
отвечает ( = 0, вершины первого уровня G1(1), G2(1)..., Gn(1)
соответствуют последовательностям длиной 1, т. е. (1(1) = 1, (2(1) =
2,..., (n(1) = п и т. д. Каждая конечная вершина отвечает
последовательности максимальной длины п.
Признак оптимальности. Если (v(n) отвечает конечной вершине дерева,
причем оценка [pic] наименьшая из оценок всех вершин, то (v(n) — искомый
вариант, иначе переходим к продолжению варианта с наименьшей оценкой.
Пример 6. Рассмотрим задачу .трех станков, условия которой приведены
в табл. 1:
Таблица 1
|Длительность |Деталь |
|операций | |
| |1 |2 |3 |4 |5 |
|ai |2 |5 |1 |3 |3 |
|bi |3 |2 |1 |4 |5 |
|ci |4 |4 |2 |2 |2 |
Нулевой шаг. ( = 0.
(A(( = 0) = A(0) + [pic] + [pic] = 0 + 14 + 3 = 17;
(B(( = 0) = В(0) + [pic] + min cj = 0 + 15 + 2 = 17;
(C(( = 0) = С(0) + [pic]=14 .
Тогда
? (( = 0) = max {17, 17,14} = 17.
Первый шаг. Конструируем все возможные последовательности длиной 1
(1(1) = 1; (2(1) = 2; (3(1) = 3; (4(1) = 4; (5(1) = 5.
Находим
(A(1) = A1 + [pic] + [pic] = 14 + 3 = 17;
(B(1)(( = 0) = В1 + [pic] + [pic] = 5 + 12 + 2 = 19;
(C(1) = С1 + [pic]= 9 + 10 = 19 .
Откуда ? (1) = max {17, 19, 19} = 19.
Аналогично определяем ? (2), ? (3), ? (4), ? (5).
[pic]
Второй шаг. Среди множества подпоследовательностей длиной 1, (1(1) =
1, (2(1) = 2,..., (5(1) = 5 выбираем наиболее перспективную ( = 1, для
которой величина оценки-прогноза ? (() оказывается наименьшей. Далее
развиваем ее, конструируя возможные варианты длиной 2, т. е. (1.2),
(1.3), (1.4), (1.5).
Для каждого из этих вариантов вновь определяем оценки по формулам (1)
— (4).
Процесс вычислений продолжаем аналогично.
Процесс построения дерева вариантов приведен на рис. 1.
Каждой конечной вершине дерева вариантов будет отвечать полная
последовательность ( = i1,i2,,.in. Если для некоторой такой вершины
величина оценки ? (() не превосходит величины оценок для всех остальных
вершин, то эта оценка определяет искомый оптимальный вариант. В противном
случае разбиваем более перспективный вариант с наилучшей оценкой.
Конечная вершина определяет вариант (последовательность) [pic] = 3,
1, 5, 2, 4 с наилучшей оценкой ? = 20. Поэтому данный вариант является
оптимальным.
Непосредственной проверкой убеждаемся, что время обработки всей
последовательности деталей для этого варианта совпадает со значением
оценки-прогноза и является минимальным:
[pic]
Летература
1)Зайченко Ю. П., «Исследование операций», Киев «Высшая школа» 1975г.
2)Акулич И.Л., «Математическое программирование в примерах и задачах»,
Москва «В ысшая школа» 1993г.
3)Кузнецов Ю.Н., Кузубов В.И., Волощенко А.Б. «Математическое
программирование», Москва «В ысшая школа» 1980г.
-----------------------
††††††††††??
[pic]
| |
