Послеоптимизационный анализ решения задач

Методические указания к лабораторным работам

по дисциплине "Информационные системы на предприятии"

Екатеринбург

2006

УДК 519.8 (075.8)

доцент, к.т.н. В.А.Пухов

ПОСЛЕОПТИМИЗАЦИОННЫЙ АНАЛИЗ РЕШЕНИЯ ЗАДАЧ (ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ)

Методические указания к лабораторным работам по дисциплине

“Информационные системы на предприятии ”/

. Екатеринбург: 2006. 18 с.

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

Библиогр.: 6 назв. Прил. 1.

Подготовлено кафедрой “

Ó , 2006

Введение

Настоящая работа является первой частью методических указаний к лабораторным работам по дисциплине «Информационные системы на предприятии», читаемой для студентов 3 курса на кафедре Информатика и информационные технологии.

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

Проведенные вычисления, графические работы, анализ полученных результатов должны быть оформлены в виде отчета в соответствии со стандартными требованиями, предъявляемыми к отчетам и пояснительным запискам [1]. Сведения из теории, содержащиеся в данных методических указаниях, в отчет включать не рекомендуется.

Введение 3 Лабораторная работа № 3. Послеоптимизационный анализ решения задач линейного программирования 4

1 Теоретический обзор 4

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

1.1.1 Построение двойственной задачи 4

1.1.3 Двойственные оценки и их назначение 5

1.2 Послеоптимизационный анализ решения ЗЛП 6

1.2.1 Определение диапазонов допустимых изменений коэффициентов при переменных в целевой функции F. 6

1.2.2 Определение диапазонов допустимых изменений параметров , i=1,…,n. 7

2 Порядок выполнения лабораторной работы 8

3 Задания для лабораторного практикума 9

Литература 15

Приложение. Рекомендации по использованию excel и matlab 16

4 Решение задач математического программирования средствами EXCEL 16

4.1 Ввод условий задачи линейного программирования 16

4.2 Работа в диалоговом окне Поиск решения 17

4.3 Анализ оптимального решения. 17

Лабораторная работа № 3. Послеоптимизационный анализ решения задач линейного программирования

Цель лабораторной работы: Использование методов линейного программирования для решения конкретных экономических задач и

проведения послеоптимизационного исследования оптимального решения.

1 Теоретический обзор

Основная задача линейного программирования формулируется следующим образом:

max (1)

при ограничениях

(2)

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

1.1.1 Построение двойственной задачи

Пусть имеем общую задачу линейного программирования, записанную в произвольной форме

max

(3)

Двойственная задача по отношению к задаче (3) запишется в виде

min

(4)

При построении двойственной задачи соблюдаются следующие правила:

1. каждому i-му ограничению задачи (3) соответствует переменная y_i задачи (4), и, наоборот, каждому j-му ограничению двойственной задачи (4) соответствует переменная x_j задачи (3);

2. матрица системы ограничений двойственной задачи получается из матрицы системы ограничений прямой задачи транспонированием;

3. свободные члены ограничений задачи (3) являются коэффициентами при соответствующих переменных целевой функции двойственной задачи (4); аналогично коэффициенты целевой функции задачи (3) совпадают со свободными членами системы ограничений двойственной задачи (4);

4. если целевая функция прямой задачи максимизируется, то целевая функция двойственной задачи минимизируется;

5. в задаче (3) ограничения-неравенства следует записывать со знаком ≤, а для задачи (4) – со знаком ≥;

6. если на j-ю переменную задачи (3) наложено условие неотрицательности, то j-е ограничение задачи (4) будет неравенством. В противном случае j-е ограничение будет равенством; аналогично связаны между собой ограничения задачи (3) и переменные задачи (4).