Исследование операций

Министерство науки и высшего образования Российской Федерации

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

высшего образования

«Пермский национальный исследовательский политехнический университет»

Электротехнический факультет

Кафедра ИТАС

ОТЧЁТ ПО ПРАКТИЧЕСКОЙ РАБОТЕ № 4

ИССЛЕДОВАНИЕ ОПЕРАЦИЙ

Выполнил: студент

Группа

Проверил:

Доцент,

Кандидат технических наук

Гольдштейн А. Л.

ПЕРМЬ 2023

Задание: решить задачи методом ветвей и границ. Корневую задачу решить симплекс-методом, остальные графически. Построить дерево решений.

Задание варианта:

L=13x1 – 6x2 → max

12x1 + 11x2 ≤132

4x1 – 5x2  ≤ 20,5

∀xj ≥ 0, цел.

Решение:

Необходимо найти такие x1 и x2, которые удовлетворяют всем условиям и доставляют максимум критерию L, причём x1 и x2 должны быть целыми числами.

В список задач помещаем исходную задачу без требования целочисленности.

Модель корневой задачи:

L=13x1 – 6x2 → max

 [pic 1]

Из списка задач берём задачу и решаем её симплекс-методом.

В качестве рекорда z принимаем значение, равное -M, т.к. не все коэффициенты критерия положительны.

Приводим её к каноническому виду:

L=13x1 – 6x2 → max

 [pic 2]

,  – дополнительные переменные.[pic 3][pic 4]

Из этого получаем искусственное (недопустимое) базисное решение: x3 =132, x4 = 20,5 (остальные переменные равны нулю). Соответственно базис состоит из одноименных векторов условий.

В первую строку таблицы заносятся коэффициенты при x из L.

L=13x1 – 6x2 =0 x0+13 x1-6 x2+0 x3+0 x4.

Csi – коэффициенты в L при базисных переменных (базисные переменные – x3 , x4 ).

132 x0=12x1 + 11x2 +1x3+ 0x4;

20,5 x0=4x1 - 5x2 +0x3+1x4.

zj – вычисляется по формуле:

[pic 5]

[pic 6]

[pic 7]

[pic 8]

[pic 9]

[pic 10]

Оценки Δj вычисляются по формуле:

[pic 11]

где  – коэффициенты из первой строки таблицы.[pic 12]

[pic 13]

[pic 14]

[pic 15]

[pic 16]

[pic 17]

Если нет отрицательных оценок, значит, выполнился признак оптимальности. На этом этапе признак оптимальности не выполняется.

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

Заполняется столбец θ. Значения вычисляются делением элементов столбца A0 на положительные элементы направляющего столбца.

[pic 18]

[pic 19]

По минимальному значению θ определяется направляющая строка k: minθi=θk. Если получилось несколько θ, то выбирается любая из них. На пересечении направляющих строки и столбца находится направляющий элемент.

Изменяется базис в позиции направляющей строки. Базисным становится вектор, соответствующий направляющему столбцу, т.е. A1. И изменяется соответствующий коэффициент в таблице 1.