Доклад на тему: Тема: «Математическое программирование»

Скачать 0.49 Mb.

Название	Доклад на тему: Тема: «Математическое программирование»
страница	4/11
Дата публикации	15.06.2014
Размер	0.49 Mb.
Тип	Доклад

literature-edu.ru > Математика > Доклад

1 2 3 4 5 6 7 8 9 10 11

3 Целочисленное программирование.

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

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

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

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

1. Существуют задачи линейного программирования, которые формально к целочисленным не относятся, но при соответствующих исходных данных всегда обладают целочисленным планом. Примеры таких задач – транспортная задача и ее модификации (задачи о назначениях, о потоках в сетях).

2. Толчком к изучению целочисленных задач в собственном смысле слова явилось рассмотрение задач линейного программирования, в которых переменные представляли физически неделимые величины. Они были названы задачами с неделимостью. Таковы, например, задачи об оптимизации комплекса средств доставки грузов, о нахождении минимального порожнего пробега автомобилей при выполнении заданного плана перевозок, об определении оптимального машинного парка и его оптимального распределения по указанным работам при условии минимизации суммарной стоимости (машинного парка и производимых работ), о нахождении минимального количества судов для осуществления данного графика перевозок и т. п.

3. Другим важным толчком к построению теории целочисленного программирования стал их требуется найти экстремум целочисленной линейной функции, заданной на конечном множестве элементов. Такие задачи принято называть задачами с альтернативными переменными. В качестве примеров можно назвать задачи коммивояжера (бродячего торговца), об оптимальном назначении, теории расписания, или календарного планирования, и задачи с дополнительными логическими условиями (например, типа «или – или», «если – то» и т. п.).

Исторически первой задачей целочисленного типа является опубликованная в 1932 г. венгерским математиком Е. Эгервари задача о назначении персонала. В 1955 г. на Втором симпозиуме по линейному программированию была рассмотрена задача о бомбардировщике, известная как задача о ранце.

Тогда математическая модель примет следующий вид:

Максимизировать

при условиях

Целочисленное программирование включает в себя:

- условную оптимизацию( поиск минимума функции одной переменной для фиксированного интервала когда x, x1 и x2 есть скаляры, а f(x) - функция, которая возвращает скаляр);

- безусловную оптимизацию(f(x) – возвращающая скаляр функция).

Оптимизация — в математике, информатике и исследовании операций задача нахождения экстремума (минимума или максимума) целевой функции в некоторой области конечномерного векторного пространства, ограниченной набором линейных и/или нелинейных равенств и/или неравенств.

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

Допустимое множество — множество ;

Целевую функцию — отображение ;

Критерий поиска (max или min).

Тогда решить задачу означает одно из:

Показать, что .

Показать, что целевая функция не ограничена снизу.

Найти .

Если , то найти .

1 2 3 4 5 6 7 8 9 10 11

Похожие:

	«Математическое и программное обеспечение планирования и управления... Специальность 010503 “Математическое обеспечение и администрирование информационных систем”		Программа учебной дисциплины «Управление данными» «Математика», «Информатика», «Программирование на языках высокого уровня», «Дискретная математика», «Объектно-ориентированное программирование»,...
	Специальность «Математическое обеспечение и администрирование информационных... Специальность «Математическое обеспечение и администрирование информационных систем»		Доклад директора- агаева Д. Р на тему: «Анализ работы коллектива школы в 2012-2013 учебном году» Публичный доклад директора- агаева Д. Р на тему: «Анализ работы коллектива школы в 2012-2013 учебном году»
	Урока-презентации по русскому языку в 9 классе. Тема: «Подготовка... Тема: «Подготовка к гиа. Обучение сочинению-рассуждению на лингвистическую тему»		Учебно-методический комплекс санкт-Петербург 2010 министерство образования... Учебно-методический комплекс предназначен для студентов специальности 220201. 65 управление и информатика в технических системах,...
	Доклад седьмой. Внутриприродное взаимодействие 214 Восьмой доклад. Сущность кормления 235 Пятый доклад. Наблюдение макрокосмического, как задача духовной науки: земной и растительный рост 141		Исследовательская работа на тему Тема дуэли в русском обществе и литературе почти не изучена, поэтому она представляет для меня интерес и я решила исследовать эту...
	Реферат к вступительному экзамену в аспирантуру по специальности... «Разработка численной модели распространения лазерного излучения в нелинейно-оптических средах»		Доклад на тему: «основные этапы развития русского письма» Официальное принятие христианства в Киевской Руси и начало систематического русского письма

Литература