|
|
Отыскание максимума линейной функцииВ основе симплексного метода решений задач линейного программирования лежит с некоторыми дополнениями метод последовательных исключений, представляющий собой совокупность удобных вычислительных алгоритмов, построенный на последовательном применении тождественных (симплексных) преобразований системы уравнений. Добавляя к левой части неравенств (*1) некоторую неотрицательную величину yi³0 (i= 1, 2, 3), называемую выравнивающей или базисной переменной, превратим их в уравнения:
Каждая из переменных y1, y2, y3 входит только в одно уравнение и зависит от переменных x1 и x1, которые мы называем свободными. Системе соответствует исходной базисное решение x1 = x1 = 0, y1 = 350, y2 = 392, y3 = 408 и Z = 0. Выполняем первое тождественное преобразование системы уравнений (*2). Выбираем разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z строке, ибо теоретически установлено, что при этом можно ожидать при прочих равных условиях большего увеличения функции Z. Правую часть уравнений делим на элементы разрешающего столбца и выбираем наименьшее положительное отношение, соответствующее разрешающей строке (уравнению). На пересечении выделенных столбца и строки стоит разрешающее число. Первое уравнение делим на разрешающее число и выписываем получившееся уравнение. Умножая это уравнение последовательно на остальные элементы разрешающего столбца 14, 6 и -10 и вычитая соответственно из 2-го, 3-го и 4-го уравнений системы (*2), придем к следующей системе (*3):
Подобное тождественное преобразование, при котором выбор разрешающего числа производится по указанному правилу, будем называть симплексным преобразованием. Таким образом, симплексное преобразование выполняется по следующему правилу: 1. Выбирается разрешающий столбец, соответствующий наименьшему отрицательному элементу в Z – строке. 2. Выбирается разрешающая строка, которая соответствует наименьшему положительному из отношений элементов правой части уравнений на соответствующие элементы разрешающего столбца. На пересечении разрешающего столбца и разрешающей строки стоит разрешающее число. 3. Элементы разрешающей строки делятся на разрешающее число. 4. Вычисляем элементы всех остальных строк по формуле:
Из системы (*3) находим второе допустимое базисное решение x2 = y1 = 0, x1 = 25, y2 = 42, y3 = 258, которому соответствует новое увеличенное значение функции Z = 250. Таким образом, процесс последовательных симплексных преобразований является процессом последовательного улучшения решения. При этом: 1. Если в Z-строке найдется хотя бы один отрицательный элемент и a) в разрешающем столбце найдется хотя бы один положительный элемент, то можно улучшить решение; b) если же разрешающий столбец не содержит положительных элементов, то функция Z неограниченно возрастает. 2. Если все элементы в Z-строке неотрицательны, то достигнуто оптимальное решение. Это и есть достаточные условия существования оптимально плана. В системе (*3) коэффициент при x2 в Z-строке отрицательный, поэтому второй столбец будет разрешающим. Находим, что вторя строка будет разрешающей. Далее проводим симплексное преобразование системы (*3) согласно указанному алгоритму. Так как в Z-строке все элементы неотрицательны, то данный план является оптимальным. При этом у1 = y2 = 0; y3 = 120; x1 = 20; x2 = 14 и Zmax = 270. Выполнение симплексных преобразований связано с кропотливым и часто довольно громоздкими вычислениями. Эти вычисления можно в значительной степени упростить, используя для решения так называемые симплексные таблицы. Каждое симплексное преобразование системы сводится к переходу от одной симплексной таблицы к другой.
Итак, соответственно исходной системе уравнений (*2) составляем первую симплекс-таблицу. Таблица *1
Первый столбец – это столбец базисных переменных, во втором столбце стоят свободные коэффициенты правой части уравнений (*2), в первой строке располагаются все переменные, последний столбец – это контрольный столбец и коэффициенты в нем равны сумме коэффициентов по всей строке. Из табл. *1 имеем первое допустимое решение системы (*2): x1 = x1 = 0, y1 = 350, y2 = 392, y3 = 408 и Z = 0. Переход ко второй симплекс-таблице (табл. *2)
Таблица *2
После заполнения табл. *2 следует проверить правильность ее заполнения, для чего суммируем коэффициенты по строкам и эта сумма должна быть равна коэффициентам, стоящим в соответствующих клетках контрольного столбца. Из табл. *2 второе допустимое решение будет x2 = y1 = 0, x1 = 25, y2 = 42, y3 = 258, которому соответствует новое увеличенное значение функции Z = 250. Нетрудно видеть, что эта таблица соответствует системе (*3), а опорное решение x2= 0, x1 = 25 соответствует вершине D (25, 0) многоугольника решений. Так как в Z-строке имеется отрицательный элемент, то улучшаем решение, для чего составляем симплексную табл. *3. Для простоты вычислений следует помнить, что в новой таблице на месте элементов разрешающего столбца (кроме разрешающего элемента) стоят нули. Если в разрешающей строке стоят нули, то в новую таблицу соответствующие столбцы переносятся без изменения.
Таблица *3
Так как в Z-строке нет отрицательных элементов, то данное решение будет оптимальным. Табл. *3 соответствует системе уравнений (*4) и оптимальному решению y3 = 120; x1 = 20; x2 = 14 и Zmax = 270. Итак, оптимальный план предполагает выпуск 20 единиц изделия А и 14 единиц изделия В, при этом будет получена максимальная прибыль равная 270 руб., а ресурсы оборудования оказались в избытке в количестве 120 станко-часов. ТРАНСПОРТНАЯ ЗАДАЧА
  Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...  ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...  Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...  ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|
14
или 
