Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Вычислительная процедура симплексного метода
Чтобы получить представление о сущности симплексного метода, рассмотрим следующую задачу. Задача 8.12. В авторемонтном предприятии, выпускающем неоднородную продукцию, руководитель стремится определить, какими должны быть уровни производства для каждого узла и агрегата в течение некоторого наперед заданного периода. Эти уровни ограничены технологическими и другими «внутренними» для данного предприятия условиями, приведенными в табл. 8.18. В рамках этих ограничений руководство данного предприятия пытается оптимизировать целевую функцию. В данном случае целью является получение максимальной прибыли, т. е. максимизировать Z=4X1+5X2+9X3+llX4->max (8.76) Таблица 8.18 Технологические условия производства продукции
при ограничениях Обозначим через Х0 значение целевой функции и введем в рассмотрение свободные переменные. В результате получим следующую систему уравнений: где все переменные могут принимать лишь неотрицательные значение. Введение в рассмотрение переменной Х0 позволяет записать выражение для целевой функции в виде уравнения. Задача шага 1 заключается в том, чтобы выбрать первоначальное допустимое решение системы уравнений (8.78). Существует множество таких решений, однако удобнее всего начать с Х0=0, Х5=15, Х6 = 120, Х7 = 100 при нулевых значениях остальных переменных. Другими словами, строится первое пробное решение с помощью только свободных переменных. Назовем его исходным базисным решением, а переменные X0, Х5, Xg, Х7 - базисными переменными или сокращенно базисом. Остальные переменные логично назвать внебазисными (небазисными) переменными. Так как под X0 понимается в задаче прибыль, то предложенное пробное решение является не очень выгодным. Но его можно улучшить. Обратим внимание на коэффициенты при тех переменных, которые фигурируют в строке 0 и которые в предложенном выше пробном варианте не являются базисными (т. е. на коэффициенты при Х1, Х2, Х3, Х4). Каждый коэффициент в этой строке определяет величину положительного приращения при увеличении значения соответствующей переменной на единицу. Таким образом, каждый коэффициент в строке О определяет положительное (если перед ним стоит знак минус) или отрицательное (если перед ним стоит знак плюс) приращение Х0 при увеличении на единицу соответствующей небазисной переменной.
Шаг 2 симплексного метода устанавливает правило, позволяющее определить, какие переменные должны войти в очередной пробный базис. Правило 1 (максимизация). Если в строке 0 имеются небазисные переменные, коэффициенты при которых отрицательны, следует выбрать переменную (обозначим ее через X j) с наибольшим абсолютным значением стоящего перед ней коэффициента, т. е. ту переменную, которая обеспечивает наибольшее удельное приращение значения целевой функции. В случае, когда все небазисные переменные строки О имеют положительные или нулевые коэффициенты, оптимальное решение можно считать полученным. В соответствии с правилом 1 в базис следует ввести переменную Х4, так как каждое единичное приращение Х4 приводит к увеличению значения X0 на 11. Увеличение значения Х4 возможно лишь за счет уменьшения значений базисных переменных в каждой строке, содержащей Х4 с положительным коэффициентом. Так, например, при увеличении Х4 на единицу: значение Х5 должно быть уменьшено на 1, чтобы удовлетворялось ограничение, приведенное в строке 1; значение Х2 должно быть уменьшено на 2, чтобы удовлетворялось ограничение, приведенное в строке 2; значение Х7 должно быть уменьшено на 15, чтобы удовлетворялось ограничение, приведенное в строке 3. Сколь велико должно быть значение Х4, чтобы значение одной из выбранных вначале базисных переменных достигло своей нижней границы, т. е. нуля. Такой предел для Х4 равняется 100/15 = 6,67, при Х7 = 0. Следовательно, в базис нужно включить Х4, исключив из него Х7. Обобщая вышеизложенное, сформулируем следующее правило для шага 3. Правило 2: а) рассмотрим отношения чисел, стоящих в правых частях ограничений (7.55), к соответствующим коэффициентам при новой базисной переменной X j (не обращая внимание на отношения, в которых знаменатель равен нулю или представляет собой отрицательное число);
б) выберем отношение с наименьшим значением - в очередном пробном решении X j приравнивается именно этому значению. Пусть наименьшее из всех отношений правых частей (8.78) к соответствующим коэффициентам при Xj соответствует переменной Хк, входившей в предыдущее решение; тогда в очередном пробном решении следует положить Хк = 0. Результаты вычислений приведены в табл. 8.19. Таблица 8.19 Итерация 1
Шаг 4. Перепишем соотношения (8.78) таким образом, чтобы в строке 3 коэффициент при Х4 был равен единице, а в строках 0,1 и 2 - нулю. Процедуру, с помощью которой это достигается, называют операцией замены базиса. Сначала разделим обе части уравнения в строке 3 на коэффициент при Х4, т. е. на 15 Обратим в нули коэффициенты при X4 в строках 0, 1,2, действуя по следующей схеме: 1) умножить строку 3 на 11 и результат прибавить к строке 0; 2) умножить строку 3 на - 1 и результат прибавить к строке 1; 3) умножить строку 3 на - 2 и результат прибавить к строке 2. В результате получим Полученное уравнение (8.80) эквивалентно уравнению (8.78). Его удобство заключается в том, что, полагая X1 = X2 =...= Х6 = Х7 = 0, сразу можно определить значения переменных для нового пробного базисного решения. X0=220/3; Х5=25/3; Х6=320/3; Х4=20/3. Прибыль для нового пробного решения равняется прибыли при предыдущем пробном базисе плюс значение новой базисной переменной, умноженной на удельный вклад новой базисной переменной, в приращении прибыли: Смысл правила 2 становится теперь более ясным. Если бы вместо Х7 из первоначального базиса исключить Х5 (или Х6), то Х4, Х7, Х6 (или Х5) приняли бы отрицательное значение, что противоречит предположению о том, что ни одна из переменных не может быть отрицательной. Итерация 2. Завершив первую итерацию, следует вернуться к шагу 2, с тем, чтобы определить, является ли полученное решение оптимальным. Если оптимум еще не достигнут, необходимо в соответствии с симплексным алгоритмом приступить к следующей итерации. Согласно правилу 1, возможность улучшить решение существует. Таблица 8.20
При этом в очередной базис можно включить либо Х1, либо Х2, либо Х3. На основании правила 1 выбор падает на X1, так как эта переменная обеспечивает наибольшее удельное приращение для значения целевой функции. В соответствии с табл. 8.20 в очередном пробном решении Х5 следует заменить на X1. С учетом произведенной замены необходимо преобразовать систему уравнений (8.80). Вначале выполним нормировку коэффициента при Х1 в строке 1: Затем исключим X1 из уравнений в строках 0, 2, 3, действуя по следующей схеме: 1) умножить строку 1 на 9/5 и результаты сложить со строкой 0
2) умножить строку 1 на -33/5 и результаты сложить со строкой 2; 3) умножить строку 1 на -1/5 и результаты сложить со строкой 3. В результате получим: Третье пробное базисное решение дало следующие результаты: Итерация 3. Завершив вторую симплекс-итерацию, видим (строка 0), что решение может быть улучшено за счет Х3. Определим, какая переменная должна быть исключена из базиса. Пронормируем коэффициент X3 в строке 3 путем деления обеих частей соответствующего уравнения на 7/12 и исключим Х3 из уравнений в строках 0, 1 и 2 следующим образом: 1)умножить строку 3 на 11/12 и результат сложить со строкой 0; 2) умножить строку 3 на 5/12 результат сложить со строкой 1; 3)умножить строку 3 на 13/12 и результат сложить со строкой 2. В результате получим: В строке 0 все коэффициенты положительны, следовательно, согласно правилу 1, полученное решение является оптимальным (табл. 8.21).
Таблица 8.21 Итерация 3
Коэффициенты при переменных в окончательном варианте строки 0 иногда называют скрытыми издержками. Каждый коэффициент определяет отклонение значения целевой функции от оптимального при увеличении значения соответствующей небазисной переменной на единицу. Таким образом, предприятие будет иметь прибыль 695/7 при выпуске продукции по технологическому процессу 1 и 3. В кратком изложении симплексный метод состоит в следующем: Шаг 1. Выбирается исходный базис. Шаг 2. Используется правило 1. Если рассматриваемое пробное решение не является оптимальным, осуществляется переход к шагу 3. В противном случае вычисления прекращаются. Шаг 3. Выполняется процедура, предписанная правилом 2. Шаг 4. Сменяется базис, после чего возвращаются к шагу 2.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-01-14; просмотров: 127; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.221.239.148 (0.022 с.) |