Ряд определений:
Столбец симплекс таблице ассоциированные с вводимой переменной будем называть ведущим столбцом.
Строку соответствующей исключаемой переменной будем называть ведущей строкой.
Элемент таблицы находящийся на пересечении ведущего столбца и ведущей строки будем называть ведущим элементом.
После того как определены включаемые и исключаемые переменные следующие итерации поиск нового базисного решения осуществляется исключение переменных. Этот процесс изменения базиса включает вычислительные процедуры 2х типов:
Формирования ведущего уравнения - новая ведущая строка равна предыдущую ведущую строку делим на ведущий элемент.
Формирования всех остальных уравнений включая Z уравнений – новое уравнение равно разности предыдущего уравнения и произведения коэффициента ведущего столбца предыдущего уравнения на новую ведущую строку.
Пусть A’ij элемент который нудно найти.
Aij элемент предыдущей таблицы стоящей на том же месте.
Ars ведущий элемент.
Arj элемент стоящий в том же столбце но в ведущей строке.
Ais элемент стоящий в той же строке но в ведущем столбце.
A’ij=(Aij*Ars-Ais*Arj)\Ars правило прямоугольника.
Aij…..Ais
Arj….Ars
В симплекс методе используются 2условия:
условие оптимальности - включаемой переменной в задачах на максимум(минимум) является не базисная переменная имеющая в Z уравнений наибольший отрицательный(положительный) коэффициент. В случае равенства таких коэффициентов для нескольких не базисных переменных выбор делается произвольно. Если все коэффициенты при не базисных переменных в Z уравнении не отрицательны(не положительны) то полученное решение оптимально.
условие допустимости – в задачах на максимум и на минимум в качестве исключаемой переменной выбирается та базисная переменная для которой отношение постоянной в правой части соответствующего ограничения к положительному коэффициенту ведущего столбца минимально. В случае равенства этого отношения для нескольких базисных переменных выбор делается произвольно.
21.02.2012
Двойственность и анализ моделей на чувствительность. Определение двойственной задачи.
Прямая задача линейного программирования в стандартной форме записывается так. Экономическая интерпретация прямой задачи может быть следующей: сколько и какой продукции Хi и от единицы до N необходимо произвести что бы при заданных стоимостях Ci(стоимость) от 1 до N и заданных запасов ресурсов Bj от 1 до N максимизировать выпуск продукции в стоимостном выражении.
Двойственная задача это вспомогательная задача линейного программирования формулируемая с помощью определённых правил непосредственно из прямой задачи.
Двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:
каждому ограничению прямой задачи соответствует переменная двойственной задачи.
Каждой переменной прямой задачи соответствует ограничение двойственной задачи.
Коэффициенты некоторой переменной фигурирующих в ограничениях в прямой задачи становятся коэффициентами ограничения двойственной задачи.
Коэффициент фигурирующий при той же переменной в выражении для целевой функции прямой задачи становится постоянной правой части этого же ограничения двойственной задачи.
Экономическая интерпретация двойственной задачи: какова должна быть цена единицы каждого из ресурсов что бы при заданных количествах ресурсов Bj от 1 до N и величиной стоимости единицы продукции Ci от 1 до N минимизировать общую стоимость затрат.
Пусть двойственная задача имеет M переменных (у1,у2….уn) и N ограничений соответствующих N. Тогда двойственная задача в общем виде (в тетради).
Условие двойственной задачи формулируется следующим образом:
Прямая задача, целевая функция, ограничения: функция стремится к максимуму, <=. К минимуму, >=.
Двойственная задача, целевая функция, ограничения: к минимуму, >=. К максимуму, <=.
в двойственной задачи переменных Yj называют двойственными оценками или учетными неявными ценами.
Вычислительные процедуры:
На каждой симплекс итерации как для прямой так и для двойственной задачи столбцы левой и правой части ограничений вычисляются следующим образом: столбец итерации i=произведению обратной матрицы на итерации i на столбец исходной модели.
На каждой итерации элементы строки целевой функции прямой задачи определяются соотношением: элемент при Xi в строке целевой функции= разности левой и правой частей соответствующего ограничения двойственной задачи.
значение двойственных переменных на каждой итерации определяются: значение двойственной переменной на итерации i=произведению вектор строки исходных коэффициентов целевой функции при базисных переменных прямой задачи на итерации i на обратную матрицу итерации i.