Лекция: Линейные оптимизационные модели

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

«Нижегородский государственный университет им. Н.И.Лобачевского»

Факультет вычислительной математики и кибернетики

МЕТОДИЧЕСКИЕ ПОСОБИЯ

по курсу «Математические основы информатики»

для студентов факультета ВМК

специальности „Прикладная информатика“

Часть 1

Н. Новгород — 2007

Методические пособия по курсу «Математические основы информатики» для студентов факультета ВМК специальности „Прикладная информатика“. Часть 1. / Нижег.гос.ун‑т, 2004, с.15 .

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

Содержание

1. Рабочая программа курса “Математические основы информатики”. 3

Предисловие. 3

Содержание курса. 3

Линейные оптимизационные модели. 3

Практические занятия. 3

Литература (основная) 4

Литература (дополнительная) 4

2. Задачник. 4

3. Задание на курсовую работу. 11

1. Рабочая программа курса “Математические основы информатики”

Предисловие

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

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

Содержание курса

Линейные оптимизационные модели

Понятие оптимизационных задач. Примеры формальных постановок оптимизационных задач. Задачи математического программирования. Место задач линейного программирования в классе задач математического программирования. Эквивалентные формы записи задач линейного программирования Геометрический смысл задач линейного программирования. Графическое решение задач линейного программирования. Теорема о выпуклости множества допустимых решений задачи линейного программирования. Теорема о выпуклости множества оптимальных решений задач линейного программирования. Симплекс метод решения задач линейного программирования. Искусственное начальное решение в задаче линейного программирования. Особые случаи применения симплекс-метода. Двойственность. Двойственные задачи линейного программирования для различных форм. Лемма о соотношениях линейных форм. Лемма о равенстве линейных форм. Лемма о взаимодвойственности систем линейных однородных алгебраических уравнений. Основная теорема двойственности. Следствие из основной теоремы двойственности о связи оптимальных решений прямой и двойственной задач линейного программирования. Теорема равновесия. Интерпретация двойственных оценок. Обобщенный прямой и двойственный симплекс метод.

Практические занятия

ЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ.

1.Различные эквивалентные формы записи задач линейного программирования. Геометрическая интерпретация.

2.Симплекс метод решения задач линейного программирования.

3.Искусственное начальное решение.

4.Особые случаи применения симплекс метода.

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

6.Связь оптимальных решений прямой и двойственной задач.

7.Двойственные оценки. Их интерпретация.

Литература (основная)

1.Ашманов С.А.Линейное рограммирование. М.: Наука,1981.

2.Ляшенко И.И., Шор Н.З. и др.Линейное и нелинейное программирование. Киев, Высшая школа, 1975.