Экономико-математическое моделирование /
j=1; 4)
Вместо того, чтобы исследовать функцию f на min, будем исследовать на
f1= - f на max.
В ограничениях содержащих к левой части прибавим дополнительную не отрицательную переменную. В ограничениях содержащих - в левой части вычтем не отрицательную дополнительную переменную. Условие не отрицательности в равенство не переводится.
f1 = -f =х1 - 2х2 + х3 - х4 max
хj 0 (j =1; 7)
Вводимые дополнительные переменные имеют экономический смысл. В ограничении исходной задачи, отражается расход и наличие ресурсов, то числовое значение дополнительной переменной, показывает количество не израсходованного ресурса определенного вида.
Замечание: Если переменная хк не подчинена условию не отрицательности, ее нужно заменить на разность двух не отрицательных величин
xk = uk + vk .
Определение: Совокупность не отрицательных чисел х1, х2,..., хn , удовлетворяющих ограничениям задачи, называются допустимым решением или просто планом задачи.
План Х* = (х1*, х2*, ..., хn*) при котором целевая функция достигает своего экстремального значения, называется оптимальной.
Не нулевые допустимые решения задачи, называются базисными решениями, если соответствуют им векторы Аj образуют линейно не зависимую систему.
1.2 Симплекс - метод .
С самого начала укажем, что симплекс-метод в его непосредственной форме предназначен для решения канонической задачи линейного программирования.
Для работы по симплекс-методу требуется:
1. привести задачу к канонической форме;
2. представить ее в векторной форме;
3. заполнить первую симплексную таблицу;
4. проверить план на оптимальность;
5. если план не оптимален, то выбрать разрешающий элемент, произвести пересчет всех элементов симплексной таблицы и перейти к п.4
Производя расчеты по симплекс-методу, нет необходимости выписывать все вычисления подробно. Оказывается, весь процесс можно записать в виде последовательности однотипно заполняемых таблиц, причем каждому шагу будет отвечать переход к новой таблице.
Для построения первой таблицы из векторов Аj нужно выбрать несколько компонентов, которые образуют единичную матрицу . И если исходная система ограничений, содержит только неравенства или , то при введении дополнительных переменных, сразу получают базисные векторы, которые образуют первый базис в симплекс-таблицах.
Сб
Хб план С1
х1 С2
х2 .....
.... Сn
хn
j
0
1
2
...
n
В верхней строке записывают коэффициенты при переменных целевых функций. В столбцы х1, х2, ..., хn - заносят элементы векторов А1, А2,Аn. В столбец план - заносят компоненты вектора В. Столбец Хб - отображает переменные входящие в базис. Их индексы совпадают с индексами базисных векторов. Столбец Сб - коэффициенты при базисных переменных в целевой функции.
Проверка плана на оптимальность. Нижняя строка симплекс-таблицы j - называется индексной.
0 = Сб *В;
j = Сб*хj - Сj или j = Cб *Аj - Cj
Она служит для проверки опорного плана на оптимальность. Если все j 0, то все планы являются оптимальными.
Переход от одного базисного решения к другому, осуществляется исключением из базиса какого-нибудь из векторов и введением в него нового вектора.
1. В качестве разрешающего столбца выбирают столбец для которого элемент индексной строки р является самым маленьким отрицательным числом.
2. Находим отношения компонент столбца план к неотрицательным элементам разрешающего столбца.
3. Выбираем наименьшее из данных отношений. Строка с ним называется разрешающей.
4. На пересечении разрешающего столбца и разрешающей строки стоит разрешающий элемент аqp. Индексы q и p обозначают, что из базиса выводится Аq, а вместо него вводится Аp. Разрешающий элемент обычно обводят в таблице.
5. На месте разрешающего элемента в новой симплекс-таблице ставят 1, остальные элементы разрешающего столбца 0.
6. Все элементы разрешающей строки делят на разрешающий элемент.
7. Остальные элементы симплекс-таблицы пересчитывают по формулам Жордана-Гаусса.
Замечание: Если по индексной строке определили разрешающий столбец, но в нем все элементы не положительные, то задача не имеет решений.
Следующий этап - это определение оптимального плана из симплекс-таблицы Х* = (х1*, х2*, ..., хn*). Оптимальное решение выписывают из столбцов Хб и план. Столбец Хб - показывает, какие неизвестные отличны от 0. Столбец план - показывает, чему они равны.
0 - в последней симплекс-таблицы равно max значению целевой функции.
Алгоритм работы по симплекс-методу:
1. Выделяем исходный допустимый базис и заполняем первую таблицу.
2. Если в последней строке полученной таблицы, кроме, быть может, первого числа, нет положительных чисел, то базисное решение является оптимальным - задача решена.
3. Пусть среди указанных в пункте 2 чисел имеется положительное число( скажем, в столбце хj). Отмечаем столбец Хj вертикальной стрелкой. Просматриваем остальные числа этого столбца. Если среди них нет положительных чисел, то min f = - - задача решений не имеет.
4. Пусть среди просмотренных в п.3 чисел имеются положительные числа. Для каждого из таких чисел a составляем отношение , где b - первое число в той же строке (свободный член). Из всех таких отношений выбираем наименьшее. Пусть оно соответствует строке базисного неизвестного хi . Отмечаем эту строку горизонтальной стрелкой. Число , стоящее в отмеченной строке и отмеченном столбце, называется разрешающим элементом таблицы.
5. Переходим к новой таблице. Для этого отмеченную строку умножаем на ( чтобы на месте разрешающего элемента появилась единица) и пишем ее на месте прежней. К каждой из остальных строк таблицы прибавляем строку, полученную на месте отмеченной строки, умноженную на такое число, чтобы элемент, стоящий в отмеченном столбце, обратился в 0.
6. С новой таблицей возвращаемся к п.2
1.3 М-метод.
Для решения М-задачи можно воспользоваться симплекс-методом, поскольку указан допустимый базис.
При решении М-задачи могут представиться две возможности:
1. М-задача имеет решение, т.е. min F существует.
2. М-задача не имеет решения, min F =.
Решая М-задачу, мы стремимся получить оптимальное решение, в котором значения искусственных неизвестных равны нулю. Для того чтобы этого достичь, необходимо выбрать последовательность шагов таким образом, чтобы все искусственные неизвестные вышли из базиса, т.е. стали свободными. Тогда в базисном решении значения этих неизвестных и будут как раз нулями.
Таким образом, переходя при решении М - задачи от одного базиса к другому, мы стараемся в первую очередь выводить из базиса одно искусственное неизвестное за другим. Возможны, впрочем, и такие (досадные) случаи, когда в процессе решения приходится заменять одно искусственное неизвестное на другое (выбор разрешающего элемента по-другому не получается). Но общим направлением вычислительного процесса во всех случаях остается постепенный вывод искусственных неизвестных из базиса.
1.4 Двойственные задачи .
С каждой задачей линейного программирования связана другая задача, называемая двойственной по отношению к исходной. Совместное изучение данной задачи и двойственности к ней дает, как правило, значительно больше информации.
Задачи I и I’ называются двойственными друг другу. Смысл, который вкладывается в это название, состоит в следующем.
1. Если первая задача имеет размеры m x n ( m ограничений с n неизвестными), то вторая - размеры n x m.
2. Матрицы из коэффициентов при неизвестных в левых частях ограничений обеих задач являются взаимно транспонированными .
3. В правых частях ограничений в каждой задаче стоят коэффициенты при неизвестных в целевой функции другой задачи.
4. В задаче I все ограничения представляют собой неравенства типа , причем в этой задаче требуется достичь max f. Напротив, в задаче I’ все ограничения суть неравенства типа , причем требуется достичь min .
Двойственная задача заключается в минимизации общей оценки всего имеющегося количества ресурсов.
Взаимозависимость оптимальных решений пары двойственных задач определена следующими теоремами:
Теорема (основное неравенство). Пусть Х - какое-нибудь допустимое решение задачи I, т.е. любое решение системы, а Y - какое-нибудь допустимое решение задачи I’ - любое решение системы. Тогда справедливо неравенство
f(Х) (Y).
Следствие1 (достаточный признак оптимальности). Если для каких-то допустимых решений и задач I и I’ выполняется равенство
f( )=( ),
то есть оптимальное решение задачи
|
|