Методом ветвей и границ найти решение задачи, состоящей в определении максимального значения функции

2.51 Методом ветвей и границ найти решение задачи, состоящей в определении максимального значения функции

при условиях

x_j – целые (j=)

Р е ш е н и е. Находим решение сформулированной задачи симплексным методом без учета условия целочисленности переменных. В результате устанавливаем, что такая задача имеет оптимальный план Х₀= (18/5, 3/5, 0, 0, 24/5). При этом плане F= (X₀)=39/5.

Так как в плане Х₀ значения трех переменных являются дробными числами, то Х₀ не удовлетворяет условию целочисленности, и следовательно, не является оптимальным планом исходной задачи.

Возьмем какую-нибудь переменную, значение которой является дробным числом, например х_1. Тогда эта переменнаяв оптимальном плане исходной задачи будет принимать значение, либо меньшее или равное трём:, либо больше или равно четырём: .

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

(I) (II)

Задача (I) имеет оптимальный план  на котором значение целевой функции . Задача (II) неразрешима.

Исследуем задачу (I). Так как среди компонент оптимального плана этой задачи есть дробные числа, то для одной из переменных, например x₂, вводим дополнительные ограничения:

Рассмотрим теперь следующие две задачи:

(III)

(IV)

Задача (IV) неразрешима, а задача (III) имеет оптимальный план (3, 1, 3, 3, 3), на котором значение целевой функции задачи

Таким образом исходная задача целочисленного программирования имеет оптимальный план Х^*= (3, 1, 2, 3, 3). При этом плане целевая функция принимает максимальное значение .

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

Дадим геометрическую интерпретацию решения задачи (50)-(53). На рис. 2.6 показана область допустимых решений задачи (50)-(52).

Из него видно, что данная задача имеет оптимальный план(18/5, 3/5, 0, 0, 24/5). В то же время  не является планом задачи (50)-(53), поскольку три переменные имеют дробные значения. Возьмем переменную х₁ и рассмотрим задачи (I)и (II).

Как видно из рис. 2.7задача (I) имеет оптимальный план (3, 3/2, 0, 9/2, 3/2), а из рис.2.8 следует, что задача (II) неразрешима.

Поскольку среди компонент плана есть дробные числа, выберем переменную х₂ и рассмотрим задачи (III) (IV). Задача (III) имеет оптимальный план(3, 1, 2, 3, 3) (рис. 2.9), а задача (IV) неразрешима (рис. 2.10).

Итак, Х^*= (3, 1, 2, 3, 3) является оптимальным планом задачи (50)-(53). При этом плане .

Решение задачи, правые части которых содержат параметр.

Алгоритм решения задачи (60)-(62) подобен рассмотренному выше алгоритму решения задачи (57)-(59).

Полагая значение параметра t равным некоторому числу t₀, находим решение полученной задачи линейного программирования (60)-(62). При данном значении параметра t₀ либо определяем оптимальный план, либо устанавливаем неразрешимость задачи. В первом случае найденный план является оптимальным для любого, где

и числа q_iиp_i определены компонентами оптимального плана и зависят от t₀:

Если при t = t₀ задача (60)-(62) неразрешима, то, либо целевая функция задачи (60) не ограничена на множестве планов, либо система уравнений не имеет неотрицательных решений. В первом случае задача неразрешима для всех , а во втором случае определяем все значения параметра , для которых система уравнений (61) несовместна, и исключаем их из рассмотрения.

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

Итак, процесс нахождения задачи (60)-(62) включает следующие основные этапы:

1⁰. Считая значение параметра t равным некоторому числу , находят оптимальный план или устанавливают неразрешимость полученной задачи линейного программирования.

2⁰. Находят значения параметра , для которых задача (60)-(62) имеет один и тот же оптимальный план или неразрешима. Эти значения параметра t исключают из рассмотрения.

3⁰. Выбирают значения параметра t из оставшейся части промежутка  и устанавливают возможность определения нового оптимального плана находят его двойственным симплекс-методом.

4⁰. Определяют множество значений параметра t, для которых задача имеет один и тот же новый оптимальный план или неразрешима. Вычисления проводят до тех пор, пока не будут исследованы все значения параметра .

2.66. Для каждого значения параметра найти максимальное значение функции

при условиях

Р е ш е н и е . Считая значение параметра t в системе уравнений (81) равным нулю, находим решение задачи (80)-(82) (табл. 2. 41).

Таблица 2.41

Как видно из табл. 2.41, при t =0 есть оптимальный план задачи. Однако  является оптимальным планом и тогда среди его компонентов не окажется отрицательных чисел, т.е. при 5-3t0; 7+4t0;

13+t или при  Таким образом, если  то- оптимальный план задачи (80)-(82), при котором

Исследуем теперь, имеет ли задача оптимальные планы при . Если , то 5-3t<0 и следовательно, X=(0,5 – 3t, 7+4t, 13+t, 0) не является планом задачи. Поэтому при  нужно перейти к новому плану, который был в то же время оптимальным. Это можно сделать в том случае, когда в строке вектора Р₂ имеются отрицательные числа . В данном случае это условие выполняется. Поэтому переходим к новому опорному плану, для чего введем в базис вектор Р₁ и исключаем из него вектор Р₂ (табл. 2.42).

Таблица 2.42

Как видно из табл. 2.42, -оптимальный план задачи для всех t, при которых  Следовательно, если является оптимальным планом исходной задачи, причем .

Если t>17/2, то не является планом задачи, так как третья компонента 17 – 2t есть отрицательное число. Поскольку среди элементов 1-й строки табл. 2.42 нет отрицательных при t>17/2 исходная задача неразрешима.

Исследуем теперь разрешимость задачи при t< -7/4. В этом случае Х= (0,5 -3t, 7+4t, 13+t, 0) (см. табл.2.41) не является планом задачи, так как третья компонента 7+4t есть отрицательное число. Чтобы при данном значении параметра найти оптимальный план (это можно сделать, так как в строке вектора Р₃ стоит отрицательное число -1/2), нужно исключить из базиса вектор Р₃ и ввести в базис вектор Р₅ (табл. 2.43).

Таблица 2.43

Как видно из табл. 2.43,  является оптимальным планом задачи для всех значений параметра t, при которых

Таким образом, если , то задача (80)-(82) имеет оптимальный план , при котором

Из табл. 2.43 так же видно, что при t<4 задача неразрешима, поскольку в строке вектора Р₄ нет отрицательных элементов.

Итак, если , то задача не имеет оптимального плана; если оптимальный план, а  если , то - оптимальный план, а если , то - оптимальный план, а  если , то задача неразрешима.

Похожие работы

Методы исследования операций

Скачать

41740

5

1

... , 6)  сетевого планирования и управления, 7)  выбора маршрута, 8)  комбинированные. Из перечисленных выше методов математического программирования наиболее развитым и законченным является линейное программирование. В его рамки укладывается широкий круг задач исследования операций. Линейное программирование Несмотря на требование линейности целевой функции и ограничений, в рамки линейного ...

Методы решения управленческих задач в АПК: регрессионный анализ

Скачать

23615

1

3

... рассматриваемый период можно признать успешной. 3 Парная линейная регрессия   Для характеристики влияния изменений Х на вариацию У служат методы регрессионного анализа. В случае парной линейной зависимости строится регрессионная модель Уi = a0 +a1 *Xi + εi, I=1, …,n где n — число наблюдений; a0 ,a1 — неизвестные параметры уравнения; εi, — ошибка случайной переменной У. ...

Технический словарь

Скачать

232852

0

0

... с приглашением по запросу (в машинной графике)required parameter обязательный параметрrequired space обязательный пробел (в системах подготовки текстов)requirements specification 1. техническое задание 2. описание требований к программному средствуrerun перезапуск, повторный запускreschedule переупорядочивать очередь (о диспетчере операционной системы)reschedule interval период переупорядочения ...

Автосервис. Формирование стратегии и сценарный анализ в условиях неопределенности

Скачать

154080

26

0

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