Решения задачи планирования производства симплекс методом — страница 9

  • Просмотров 1631
  • Скачиваний 9
  • Размер файла 496
    Кб

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

в энергосистеме, число вычислительных машин в управляющем комплексе и многие другие. Задача линейного целочисленного программирования формируется следующим образом: найти такое решение (план) X = (x1,x2,...,xn), при котором линейная функция (1) принимает максимальное или минимальное значение при ограничениях =bi, i=1, 2…,m. (2) хj  0, j=1, 2,...,n.(3) xj — целые числа (4) 2. Обзор основных алгоритмов решения задач ЛП 2.1 Целочисленное линейное

программирование - метод отсечений Гомори Целочисленное линейное программирование (сокращенно ЦЛП) занимается задачами линейного программирования с целочисленными переменными, общая задача формулируется следующим образом: найти max{сх|Ах ≤ b; х - целочисленный}. ЦЛП может рассматриваться так же, как поиск точки решетки, принадлежащей многограннику или как решение системы линейных уравнений с целыми неотрицательными

переменными. Иными словами, в ЦЛП рассматриваются совместные ограничения неотрицательность и целочисленность. 2.1.1 Отсечения С помощью отсечений выделяют целочисленные части полиэдров. Метод отсечений был разработан в конце 1950-х годов Гомори для решения целочисленных линейных программ с помощью симплекс-метода. Метод отсечений оказался полезным и с теоретической точки зрения он дает возможность описать целочисленную

оболочку полиэдра. Далее описывается метод отсечений Гомори, дающий алгоритм решения задач целочисленного линейного программирования. Данный метод, который также носит название метода отсекающих плоскостей, предназначен для решения ЦЗЛП (целочисленной задачи линейного программирования) в канонической форме. Описываемая ниже версия алгоритма предназначена для решения полностью целочисленных задач, т.е. таких, у которых все

параметры aij, cj, bi – целые. 2.1.2 Описание алгоритма Приведем обобщенную схему алгоритма Гомори. Структурно он делится на так называемые большие итерации. Каждая большая итерация содержит этапы: 1.Сначала задача решается методами линейного программирования (малые итерации), обычно симплекс-методом, и анализируется результат, если результатом являются целые числа, то на этом решение заканчивается, а если дробные, то производят