|
менных, не входящих в базис, не станут отрицательными. Это и есть признак оптимальности текущего базисного решения. Вычислительные процедуры симплекс-метода состоят из следующих шагов. Шаг 0. Используя линейную модель стандартной формы , определяют начальное допустимое базисное решение путем приравнивания к нулю небазисных переменных. Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2. Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое значение (стать небазисной) при введении в состав базисных новой переменной. Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1. При решении задач линейного программирования с двумя переменными удобно использовать графический симплексный метод. При большем числе переменных необходимо применение рассмотренного алгебраического аппарата [108, с. 40]. Экстремальная задача, переменные которой принимают лишь целочисленные значения, называется задачей целочисленного программирования. Задача целочисленного программирования, в котором как целевая функция, так и функции в системе ограничений являются линейными, сводится к нахождению переменных, принимающих только целые значения. Для определения оптимального плана задачи (13) (16) при целочисленном программировании требуются специальные методы. В настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори, в основе которого лежит описанный выше симплексный метод. 75 |
которой симплекс-разность положительна и максимальна, и вводят ее в базис с исключением одной переменной из базисного реп1ения и вектора из базиса. Эти вычисления повторяются до тех пор, пока симплекс-разности для всех переменных, не входящих в базис, не станут отрицательными. Это и есть признак оптимальности текущего базисного решения. Вычислительные процедуры симплекс-метода состоят из следующих шагов. Шаг 0. Используя линейную модель стандартной формы , определяют начальное допустимое базисное решение путем приравнивания к нулю небазисных переменных. Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый' базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2. Шаг 2. Из числа переменных текущего базиса выбирается исключаемая переменная, которая должна принять нулевое значение (стать небазисной) при введении в состав базисных новой переменной. Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход шагу 1. При решении задач линейного программирования с двумя к переменными удобно использовать графический симплексный метод. При большем числе переменных необходимо применение рассмотренного алгебраического аппарата [6, с. 140]. Экстремальная целочисленные программирования. задача, переменные называется которой задачей принимают лишь значения, целочисленного 90 Задача целочисленного программирования, в котором как целевая функция, так и функции в системе ограничений являются линейными, сводится к нахождению переменных, принимающих только целые значения. Для определения оптимального плана задачи (23) (26) методы. при В целочисленном программировании требуются специальные настоящее время существует несколько таких методов, из которых наиболее известным является метод Гомори, в основе которого лежит описанный выше симплексный метод. Нахождение методом Гомори решения начинают задачи с целочисленного программирования методом определения симплексным оптимального плана задачи без учета целочисленности переменных. После этого составляют дополнительные ограничения для переменных, которые в оптимальном плане задачи имеют максимальное дробное значение. Данный «,' итерационный процесс, продолжается до получения оптимального плана задачи при условии целочисленности переменных [75, с. 313]. Информация, которую можно получить с помощью симплекс-метода, не ограничивается лишь оптимальными значениями переменных. Симплексметод фактически позволяет дать экономическую интерпретацию полученного решения и провести анализ модели на чувствительность. Для решения задач по отысканию оптимального варианта планировки рабочих мест (оборудования) роботизированных технологических модулей и предметно-замкнутых участков часто применяются методы математического программирования с применением ЭВМ. Значение оптимизации размещения оборудования определяется тем, что последовательность расстановки рабочих мест существенно влияет на величину транспортных расходов, прямоточность и ритмичность производственного процесса, длительность обработки и производственного цикла, а следовательно, производительность и себестоимость продукции. Решение задачи планировки оборудования является многовариантным. Число возможных вариантов планировки определяется количеством 91 |