XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 15
Текст из файла (страница 15)
Снова, согласно (3.15), (3.16), вычисляем матрицу-строку симплекс-разностей: (И4 аь) = Г, — ГьА4 А, = (-3 — 2). Так как симплекс-разности всех небазисных переменных отрит цательны, допустимоебазисноерешениеУ=(200 300 200 0 О) является оптимальным решением. На рис. 3.3 приведено гра- з. СИМПЛЕКС-МЕТОД з.а ,2, Симплекс-метод при известном допустимом овзисном решении 103 102 фическое решение и указана последовательность исследования крайних точек множества С допустимых решений при реализации симплекс-метода. О1 х1=400 О2 х =300 ОЗ х1ехз=о00 Оь х=о Оь х2=0 р . з.з Замечание 3.3. Пусть для задачи линейного программирования в стандартной форме известно начальное базисное решение. В этом случае вся процедура нахождения оптимального решения с использованием симплекс-метода состоит в последовательной реализации следующих шагов (см.
пример 3.4). Ш аг 1. Для известного начального базисного решения У формируют матрицы Уь, У„Аь, А„Гь, Г, и определяют матрицу Аь Шаг 2. Вычисляют матрицу-строку симплекс-разностей Г, — Г6А„'А,. Если все элементы этой матрицы-строки являются неположительными, то начальное базисное решение является оптимальным решением и вычисления завершены. В противном случае, если 66', — максимальная положительная симплекс-разность, то в новый базис вводят небазисный столбец а, матрицы А. Ш аг 3.
Определяют вектор А 1п„и множество индексов 1 его положительных координат. Определяют номер 1 столбца а1 матрицы А, выводимого из базиса, и максимальное значение у, " нового базисного переменного у,: гпах ('46 ьз)1 ° ('46 В)1 (А61нс)1 'е1 (А1,1а„); Шаг 4. Вычисляют новые значения старых базисных переменных: У;=(Аь В)1 — (Аь а) у ьх 1. Затем выписывают новое допустимое базисное решение при так у„= у,, которое называют начальным базисным решением, и возвращаются к шагу 1. Замечание 3.4.
Процедуру решения задач линейного программирования симплекс-методом удобно оформлять в виде сильтьлеьсс-тпаблитЬ, основой которых являются уравнение (3.11) и представление целевой функции в виде (3.13). Каждая симплекс-таблица отражает одну итерацию симплекс-метода состоящую из четырех шагов (см. замечание З.З). Пример 3.5, Рассмотрим задачу линейного программирования ,1'(х„х2) = бх, + 2х2 -+ шах; 2х1+ 4х2 < 9, Зхь+ х2 < б, х1 > О, х2 > О. Эта задача относится к частному случаю задач линейного программирования, в котором допустимое базисное решение можно найти непосредственно из ограничений (об этом сказано в начале параграфа). Запишем рассматриваемую задачу в стандартной форме: з (У1 У2 ..
Уз У4) = бу1 + 2У2 + 0 уз + 0 уд — + шах; 2У1 + 4У2 + 1 Уз+ 0 у4 = 9, ЗУ1 + 1 ' У2+ 0 Уз+ 1 ' У4 б уь>0, 1с=1 4 где у1 — х1 у2 — х2, а уз и у4 — новые переменные. з.г. Симплекс-метод при известном допустимом безменом решении 105 3. СИМПЛЕКС-МЕТОД 104 Здесь в соответствии с (3.10) в качестве начального донустимого базисного решения можно использовать вектор У = , т = (О 0 9 6), которому соответствует значение целевой функции /= О. Таким образом, уз, у» — базисные переменные, и можно заполнить первую симплекс-таблицу, соответствующую нулевой итерации симплекс-метода (табл.
3.1). Таблица 3.1 В табл. 3.1, как и в любой другой симплекс-таблице, выделены столбцы „Итерация", „Базисные переменные", „Значение" и столбцы, соответствующие переменным модели. В столбце „Итерация" указан номер итерации, Табл. 3.1 соответствует нулевой итерации, поэтому в первом столбце проставлено значение О. Рассмотрим процесс заполнения таблицы, исключая пока ее последнюю строку. Перепишем ограничения задачи линейного программирования в следующем виде: 6 = 3 У1 + 1 уг+ О уз + 1 У4. В результате получим последние столбцы симплекс-таблицы, начиная со столбца „Значение".
Остается заполнить столбец „Базисные переменные". В симплекс-таблице базисным переменным всегда соответствуют столбцы единичной матрицы. В табл. 3.1 это столбцы уз и у4. В столбце 1~ единица стоит на пересечении с первой строкой. Поэтому в первой строке в столбце „Базисные переменные" записано уз. В столбце у» единица стоит на пересечении со второй строкой таблицы. Поэтому во второй строке в столбце „Базисные переменные" записано У4.
Осталось заполнить последнюю строку табл. 3.1. Целевая функция задачи линейного программирования в стандартной форме имеет вид з (У1 Уг Уз,у») = бу1+2уг+Оуз+ ОУ4 и зависит только от свободных переменных У1, уг. В столбцах у1, уг, уз, у» записываем коэффициенты при этих переменных в целевой функции. Отметим, что коэффициенты при переменных у1 и уг являются их симплекс-разностями (3.16), соответствующими начальному базису (уз, У4).
В столбце Знав чение записываем нуль как значение функции / в начальном базисном решении, взятое с противоположным знаком. В столбец „Базисные переменные" записываем — /. Итак, заполнение первой симплекс-таблицы, соответствующей нулевой итерации симплекс-метода, требует представления задачи линейного программирования в стандартной форме. При этом начальное базисное решение выбирают в форме (3.10). В симплекс-таблице есть вся необходимая информация о начальном базисном решении (столбцы „Базисные переменные" и к1 „Значение ) и данные для построения нового допустимого базисного решения (значения симплекс-разностей, записанные в последней строке под свободными переменными).
Наибольшая положительная симплекс-разность равна 6 и соответствует переменному у1, которое будет новым базисным переменным. Оба элемента 2 и 3, расположенных на пересечении строк, соответствующих старым базисным переменным у з, У4, и столбца, соответствующего новому базисному переменному У1, положительны. Поэтому вычисляем 9/2 = 4,5 и 6/3 = 2. Наименьшее из двух полученных чисел равно 2 = '" и соот- 1 ветствует старому базисному переменному У4, которое нужно вывести из нового допустимого базисного решения. ф Строку симплекс-таблицы, соответствующую выводимому б азисному переменному, называют ведущей сттерокой симу»ле»ес-зтеаблиць»4а ее элемент, расположенный на пересечении 3 СИМПЛЕКС-МЕТОД 100 Тпблица З.У ~(зы х2) = Зз1 — х2 — ~ шах; 2х2 — з2 (4, х2 — 2х2 ( 2, з1+х2 (5, з1>0, х2>0, Зу, — у2-4 шах; 2У2 — Уз+уз = 4, У2 — 2У2+ У4 — — 2, у! + у2 + уб = 5, Уь > О, Й = 1, 5.
со столбцом, соответствующим новому базисному переменному, называют веду424иле элемеееууаом силетьиезсс-тлабли44ьс (в табл. 3.1 ведущий элемент выделен полужирным шрифтом). Пример 3.6. Вернемся к задаче линейного программирования, рассмотрение которой начато в примере 3.5. Используя табл. 3.1, продолжим решение задачи линейного программирования, построив новую симплекс-таблицу (табл.
3.2), имеющую столько же строк и столбцов с теми же наименованиями. В столбце „Итерация" записываем номер итерации 1. Старое базисное переменное уз остается в базисе. Поэтому в столбце „Базисные переменные" это переменное записываем в той же первой строке. Старое базисное переменное у4 меняем на новое переменное у„запись — Г' сохраняется — столбец и Базисные переменные" заполнен. Новому базисному переменному у, на итерации 1 соответствует столбец единичной матрицы, причем единичный элемент этого столбца должен стоять на месте ведущего элемента новой симплекс-таблицы (см. пример 3.5).
Чтобы добиться этого, разделим все элементы ведущей строки на ведущий элемент, получив тем самым новую ведущую строку, соответствующую новому базисному переменному у2. Все остальные элементы столбца у1 должны быть равны нулю, включая элемент, стоящий на пересечении с последней строкой новой симплекс-таблицы. Для этого из первой строки табл. 3.1 вычитаем новую ведущую строку, умноженную на 2, а из последней строки 3.2.
Симплекс-метод прн известном допустимом базисном решении 107 табл. 3.1 вычитаем новую ведущую строку, умноженную на б. А так как все симплекс-разности, записанные в последней строке табл. 3.2 в столбцах свободных переменных, являются неположительными, то новое допустимое базисное решение т У=(2 0 5 0) является оптимальным решением и ему соответствует значение целевой функции ~ = 12. Прежде чем переходить к анализу возможностей определения начального базисного решения, обсудим еще одну задачу линейного программирования для иллюстрации специфических особенностей практического использования симплекс-метода. Пример 3.7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
