Метод ветвей и границ (контрольная)

  • Просмотров 2097
  • Скачиваний 273
  • Размер файла 57
    Кб

Министерство образования Р.Ф. Тюменский государственный нефтегазовый университет Институт нефти и газа Кафедра менеджмента В отраслях ТЭК Контрольная работа по Дисциплине «Экономическая математика, методы и модели» Вариант №4 Выполнил: студент гр. МОс2 Ваганова А.Р. Проверил: Захаров А.В Тюмень 2002 г. Метод ветвей и границ. Рассмотрим задачу, состоящую в определении максимального значения функции при условиях Как и при

решении сформулированной задачи методом Гомори, первоначально находим симплексным методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X0. Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение задачи и Если же компонент плана Х0 имеются дробные числа, то Х0 не удовлетворяет условию целочисленности и необходимо осуществить

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

плане её значение будет по крайней мере либо больше, либо меньше или равно ближайшему меньшему целому числу числу Найдем рассмотренными выше методами решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих 4: 1.      2.      (I) и (II). 3.      решение. Если же значение целевой функции больше на плане, среди компонент которого есть дробные числа, то следует взять

одно из таких чисел и для задачи, план которой рассматривается, необходимо построить две задачи, аналогичные (I) и (II). 4.      I) и (II). Таким образом, описанный выше интеграционный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х0 задачи (32)-(34), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет