Постановка задачи линейного программирования

Э.А. Кравцова

Информационные системы в методах оптимизации

Методические указания
по выполнению практических занятий

Дисциплина – «Методы оптимизации»

Специальности – 230700.62 «Прикладная информатика», 231000.62 «Программная инженерия», 230400.62 «Информационные системы и технологии», 080801«Прикладная информатика (в экономике)»,230105 «Программное обеспечение вычислительной техники и автоматизированных систем», 230100.62 «Информатика и вычислительная техника»

Допущено ФГБОУ ВПО «Госуниверситет-УНПК» для использования в учебном процессе в качестве методических указаний для высшего профессионального образования

Орел 2013
Авторы: старший преподаватель кафедры ИС Э.А.Кравцова

Рецензент: к.т.н., доцент кафедры ИС О. В. Конюхова

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

Методические указания предназначены для студентов очной формы обучения специальностей 230700.62 «Прикладная информатика», 231000.62 «Программная инженерия», 230400.62 «Информационные системы и технологии», 080801«Прикладная информатика (в экономике)»,230105 «Программное обеспечение вычислительной техники и автоматизированных систем», 230100.62 «Информатика и вычислительная техника».

Редактор

Технический редактор

Орловский государственный технический университет

Лицензия ИД 00670 от 5.01.2000

Подписано к печати Формат 60 84 1\16

Печать офсетная. Усл. печ. л.5,6. Тираж 10 экз.

Заказ №__________

Отпечатано с готового оригинал-макета

на полиграфической базе ФГБОУ ВПО «Госуниверситет - УНПК»

© ФГБОУ ВПО «Госуниверситет - УНПК», 2012

© Кравцова Э.А. 2013

СОДЕРЖАНИЕ

1.Линейное программирование: симплекс – метод 4

2.Специальные задачи линейного программирования 19

3. Решение целочисленных задач 23

4. Решение задач многокритериальной оптимизации 27

5. Сетевая модель, расчет основных параметров сетевого графика 31

6.Теория игр 48

Литература 54

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

Линейное программирование: симплекс-метод решения задач линейного программирования, геометрическая интерпретация задач

Постановка задачи линейного программирования

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

или , (1.1)

где - вектор переменных, - столбец свободных членов, - матрица системы ограничений.

Задачей линейного программирования в симметричной форме записи называется задача вида (в матричной форме записи):

или (1.2)

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

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

, (1.3)

причем столбец свободных членов удовлетворяет условию B³0. В системе ограничений m уравнений и n неизвестных, т.е. матрица A имеет размер m´n,вектор-столбец B – m´1, вектор-строка коэффициентов целевой функции C – 1´n. Алгоритм решения задачи (3.1) симплекс-методом будем сопровождать решением конкретного примера, а именно задачи

(1.4)

1) Получение начального опорного плана. Один из вариантов – преобразование расширенной матрицы системы ограничений к приведенному виду, выделение базисных и свободных переменных:

.

Здесь x₃, x₄ – базисные переменные, x₁, x₂– свободные переменные. При преобразованиях необходимо следить за тем, чтобы столбец свободных членов оставался неотрицательным. Начальный опорный план получается, если присвоить свободным переменным значения, равные нулю; при этом базисные переменные принимают значения, равные числам в соответствующей строке столбца свободных членов: X_оп1=(0;0;3;4).

2) По преобразованной системе ограничений составляют симплекс-таблицу. В верхней строке (заголовки столбцов) располагаются свободные переменные, в крайнем левом столбце – базисные переменные; крайний правый столбец – это столбец свободных членов, а самая нижняя строка является строкой целевой функции (об определении чисел D₁, D₂, D_f в этой строке речь пойдет ниже). Остальное содержимое таблицы – столбцы преобразованной матрицы, отвечающие соответствующим столбцам свободных переменных (см. таблицу 1.1).

Для того чтобы найти значение D_I (в рассматриваемом примере i=1,2), воспользуемся правилом: вектор из коэффициентов при базисных переменных в целевой функции скалярно умножить на i-й столбец симплекс-таблицы и вычесть из найденного числа коэффициент целевой функции при соответствующем свободном переменном. Для D_f скалярно перемножаются вектор коэффициентов при базисных переменных целевой функции и столбец свободных членов:

;

;

.

Итак,таблица 1.2 представляет собой окончательный вид первой симплекс-таблицы.

Замечание. Следует обратить внимание на то, что D_f – это значение целевой функции при найденном начальном опорном решении: D_f=f(0,0,3,4)=1. Числа же D₁, D₂ – оценки, которые будут учитываться при проверке этого решения на оптимальность.

3) Построенное начальное опорное решение является оптимальным, если все оценки D_I неотрицательны (причем в случае положительности всех оценок решение единственно!). Если среди этих оценок есть отрицательная, но среди чисел в ее столбце нет положительных, то исходная задача не имеет решения в силу неограниченности целевой функции. Наконец, если в каждом столбце с отрицательной оценкой есть хотя бы один положительный элемент, то необходимо осуществить переход к новому опорному плану (который затем снова проверяется на оптимальность).

4) Переход к новому опорному плану проводится по следующей схеме.

- Выбирается ведущий столбец (столбец с отрицательной оценкой). Если отрицательных оценок несколько, то выбирается столбец с отрицательной оценкой, наибольшей по модулю. В рассматриваемом примере ведущим будет первый столбец (D₁=-6)

- Выбирается ведущая строка. Для этого определяется наименьшее из симплексных отношений (т.е. отношений свободных членов к соответствующим положительным элементам ведущего столбца). В примере оба числа в первом столбце положительны, поэтому: , ведущей будет вторая строка.

- На пересечении ведущих строки и столбца определяется ведущий (разрешающий) элемент (в примере это 2, соответствующая ячейка таблицы 3.2 заштрихована).

- В заголовках меняются местами переменные, соответствующие ведущим строке и столбцу (в примере меняются местами x₁ и x₄).

- Ведущий элемент заменяется значением, обратным этому элементу (в примере ½).

- Все остальные элементы ведущей строки делятся на ведущий элемент, а все остальные элементы ведущего столбца делятся на ведущий элемент, взятый со знаком «-» (см. таблицу 1.3, в которую внесены описанные выше изменения, а не найденные пока числа заменены греческими буквами).

- Оставшиеся элементы находят с помощью «правила многоугольника» (здесь Х – вычисляемое значение, - соответствующий элемент «старой» таблицы, B – ведущий элемент, A и C – оставшиеся вершины четырехугольника с диагональю ). Для разбираемого примера имеем:

; ; ; .

Итак, получена новая симплекс-таблица (таблица 1.4), которая определяет новое опорное решение (свободные переменные x₂, x₄; их значения будут равны нулю; базисные переменные x₁, x₃; их значения – соответствующие числа из столбца свободных членов: x₁=2, x₃=1). Значение функции на этом опорном решении – в правом нижнем углу, т.е. X_оп2=(2;0;1;0), f(2,0,1,0)=13.

5) Построенное новое опорное решение требуется снова проверить на оптимальность и, если необходимо, повторить операцию перехода. В рассматриваемой задаче, однако, все оценки стали положительными, и, следовательно, X_оп2=(2;0;1;0)=X_оптим, f_max=f(2,0,1,0)=13.

Замечание 1. Задачи, в которых решается задача на минимум, легко свести к рассмотренному случаю. Для этого, сохранив систему ограничений, исследуем задачу с целевой функцией .

Замечание 2. Бывают ситуации (например, когда система ограничений несовместна), когда начальное опорное решение построить невозможно; в этом случае исходная задача не имеет решения.

1.3. Задания для самостоятельной работы.

Решить задачи линейного программирования.

1) 2)

3) 4)

5) 6)

7) 8)

9) 10)

11) 12)

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: