Покажем, что любой базис (координаты экстремальной точки) содержит не более m неотрицательных переменных из общего числа переменных n+m. Это следует из того, что в каждой экстремальной точке пересекаются n граничных гиперплоскостей из m+n. Каждой из n пересекаемых плоскостей соответствует нулевое значение соответствующей свободной переменной (если плоскость относится к первым m ограничениям) или нулевое значение управляемой переменной (для плоскости ).

Итерация 1

Шаг 2. Так как нам нужно обеспечить наибольшее возможное значение x0, то выбранное пробное решение является явно плохим. Но его, несомненно, можно улучшить. Обратим внимание на строку 0. Во-первых, в нее входят, за исключением x0, только небазисные переменные. Во-вторых, каждый коэффициент в строке 0 определяет положительное (если перед ним стоит минус) или отрицательное (если перед ним стоит плюс) приращение x0 при увеличении на единицу соответствующей базисной переменной.

На шаге 2 ищется переменная, за счет которой можно улучшить значение целевой функции путем включения ее в базис. Выбор переменной осуществляется согласно следующему правилу: если в строке 0 имеются небазисные переменные, коэффициенты при которых отрицательны, следует выбрать переменную (обозначим ее через ) с наибольшим абсолютным значением стоящего перед ней коэффициента, то есть ту переменную, которая обеспечивает наибольшее удельное приращение значения целевой функции. Если все небазисные переменные строки 0 имеют положительные или нулевые коэффициенты, оптимальное решение уже получено.

В соответствии с данным правилом в базис следует ввести x4. Каждое единичное приращение x4 приводит к увеличению x0 на 11.

Шаг 3. Ищется предельное значение переменной, за счет которой можно улучшить значение целевой функции. Понятно, что чем больше x4, тем больше x0. Но беспредельно расти x4 не может, так как этому препятствуют уравнения в строках 1,2,3. В каждой из этих строк x4 растет за счет соответствующей базисной переменной. Наименьший рост x4 позволяет строка 3: до , при этом x7 обращается в 0.

В общем случае справедливо правило: рассмотрим отношения чисел, стоящих в правых частях уравнений, кроме нулевой строки, к соответствующим коэффициентам при новой базисной переменной (не обращая внимание на отношения, в которых знаменатель равен нулю или представляет отрицательное число). Наименьшее из этих отношений и есть значение новой переменной в очередном пробном решении. Та прежняя базисная переменная , которой соответствует наименьшее отношение, исключается из базиса, то есть следует положить . Если ни в одном из отношений знаменатель не является положительным числом, то имеем неограниченное оптимальное решение, так как может быть взято сколько угодно большим.

Теперь, когда известно, что x7 следует заменить в базисе на x4, перейдем к шагу 4.

Шаг 4. Перепишем систему уравнений таким образом, чтобы в строке 3 коэффициент при x4 был равен единице, а в строках 0,1,2 - нулю. Процедуру, с помощью которой это достигается, называют операцией замены базиса или операцией замены опорного плана.

Сначала разделим обе части уравнения в строке 3 на коэффициент при x4, то есть на 15:

В результате коэффициент при x4 в строке 3 равен 1. Обратим в нули коэффициенты при x4 в строках 0,1 и 2, действуя следующим образом:

а) умножим строку 3 на 11 и результат прибавим к строке 0;

б) умножим строку 3 на -1 и результат прибавим к строке 1;

в) умножим строку 3 на -2 и результат прибавим к строке 2.

В результате получим:

Удобство полученного представления линейной модели в том, что из нее сразу видны значения переменных нового базиса:

Прибыль x0 увеличилась на первой итерации с 0 до за счет новой базисной переменной x4: .

Итерация 2

Шаг 2. В базис следует ввести x1.

Шаг 3. Ищем отношения правых частей уравнений к соответствующим коэффициентам при x1. Они равны: 125/12, 1600/99, 100/3. Следовательно, из базиса должен быть исключен x5.

Шаг 4. Вначале выполним нормировку коэффициента при x1 в строке 1:

Исключим x1 из уравнений в строках 0, 2 и 3, выполнив действия:

а) умножим строку 1 на 9/5 и результат сложим со строкой 0;

б) умножим строку 1 на -33/5 и результат сложим со строкой 2;

в) умножим строку 1 на -1/5 и результат сложим со строкой 3.

В результате получим:

Третий пробный базис имеет вид:

Итерация 3

Шаг 2. В базис следует ввести x3.

Шаг 3. Ищем отношения правых частей уравнений к соответствующим коэффициентам при x3. Они равны: 25 (строка 1) и 55/7 (строка 3). Следовательно, из базиса должен быть исключен x4.

Шаг 4. Вначале выполним нормировку коэффициентов при x3 в строке 3:

Теперь исключим x3 из уравнений в строке 0,1 и 2, выполнив действия:

а) умножим строку 3 на 11/12 и результат сложить со строкой 0;

б) умножим строку 3 на (-5/12) и результат сложить со строкой 1;

в) умножим строку 3 на 13/12 и результат сложить со строкой 2.

В результате получим:

Итерация 4

Шаг 2. Так как в строке 0 все коэффициенты положительны, получено оптимальное решение:

Анализ моделей на чувствительность и двойственная задача

В большинстве случаев кроме оптимизации решения, ЛПР хочет знать, в каком интервале можно менять параметры в модели без существенного отклонения от найденного оптимума и без значительного нарушения структуры оптимального базиса. Исследование, позволяющее ответить на эти вопросы, называется анализом линейной модели на чувствительность, или анализом линейной модели при известном оптимальном решении.

На многие вопросы, связанные с анализом на чувствительность, можно ответить, располагая численными данными на заключительной симплексной итерации. Ниже описываются два метода анализа на чувствительность, применимые к задачам вида:

Сущность обоих методов будет полностью показана на рассмотренном ранее примере распределения ресурсов. Запишем для этой задачи исходную и заключительную системы уравнений:

(I)

и

(F)

где x0 подлежит максимизации.

Изменение целевой функции

Предположим, что у нас изменились некоторые коэффициенты целевой функции. Понятно, что полученное ранее оптимальное решение по-прежнему осталось допустимым. Но оно может быть уже не оптимальным.

Рассмотрим коэффициент при небазисных переменных x2 и x4 в строке 0 системы уравнений (F). Интуитивно ясно, что если уменьшить их удельную прибыльность, прежний заключительный базис останется оптимальным. Однако если прибыльность x2 и x4 получит достаточно большое положительное приращение, оптимальный базис может смениться.

Предположим, что коэффициент при x2 получает положительное приращение д, т.е. становится равным 5+д. Тогда строка 0 системы уравнений (I) примет вид:

При выполнении каждой итерации симплексного алгоритма мы прибавляли к строке 0 одну из остальных строк, предварительно умножив последнюю на некоторую константу. Следовательно, на заключительной итерации строка 0 системы уравнений (F) запишется в виде:

,

так как член - дx2 сохраняется в строке 0 на любой итерации.

Если , то коэффициент при x2 примет отрицательное значение. В этом случае прежнее решение уже не является оптимальным, так как в базис следует включить x2. Аналогично, если бы коэффициент при x4 увеличился бы на значение, превышающее , то прежнее решение перестало бы быть оптимальным. Следовательно, коэффициенты при небазисных переменных в строке 0 на этапе заключительной итерации показывают, в каких пределах могут принимать положительные приращения соответствующие коэффициенты в выражении для целевой функции без нарушения оптимальности ранее полученного решения.

Предположим, что существенно понизилась прибыльность переменной x1 или x3, каждая из которых входит в базис. Вполне возможно, что найденное базисное решение окажется при этом неоптимальным. Оказывается, что и при увеличении коэффициентов при x1 и x3 ранее полученное решение может также оказаться неоптимальным.

Ответим на вопрос: в каких пределах можно менять коэффициент при x1 не нарушая оптимальности найденного ранее решения. Для ответа на этот вопрос выполним операции, аналогичные только что проделанным. При этом строка 0 системы уравнений (I) примет вид:

,

а строка 0 в (F) запишется в виде:

Так как считаем, что x1 по-прежнему входит в базис, необходимо исключить x1 из строки 0 в системе (F). Для этого умножим строку 1 в (F) на д и прибавим к строке 0. В результате строка 0:

Отсюда следует, что при выполнении условия полученное решение остается оптимальным. При коэффициент при x2 принимает отрицательное значение. При отрицательным становится коэффициент при x4.

Рассмотренный прием анализа на чувствительность годен и в случае одновременного изменения коэффициентов при нескольких базисных переменных. При этом в строку 0 на последней итерации войдет несколько переменных приращений , каждое из которых влияет на способ выбора нового базиса. Чтобы базис остался оптимальным, должны удовлетворять системе неравенств, каждое из которых есть условие неотрицательности коэффициентов при соответствующей небазисной переменной в строке 0.

Изменение констант в правых частях ограничений

Их изменение может привести к тому, что прежний оптимальный базис будет недопустимым. Если он останется допустимым, то он по-прежнему будет оптимальным, так как коэффициенты в строке 0 не меняются.

Рассмотрим правую часть строки 2 системы (I). Произведем замену 120 > 120+д. Заметим, что остаточная переменная в данной строке x6 входит в базис и на первой и на последней итерации, то есть с коэффициентом +1. Поэтому д сохранится в правой части строки 2 без изменений. Таким образом, ранее полученное решение останется допустимым, если (см.строку 2 в F). Иначе x6 будет <0, что недопустимо.

Произведем теперь замену 15 > 15+д в правой части строки 1 системы уравнений (I). При каких значениях д полученный базис остается допустимым? В отличие от строки 2 строка 1 вычиталась в процессе выполнения симплексного алгоритма из других строк. Заметим, что появление д в правой части каждого уравнения сопровождается появлением x5 в левой части этого же уравнения с тем же коэффициентом. Следовательно, на последней итерации будем иметь:

(F1)

Чтобы базисные переменные x1, x6, x3 были неотрицательными, правые части строк (1), (2), (3) также должны быть неотрицательными. Отсюда следует, что прежнее оптимальное решение остается допустимым, если

При отрицательным становится x1, - x6.

Пусть д=1, что соответствует увеличению ресурса, описываемого строкой 2 на единицу. Из строки 0 системы (F1) видно, что значение целевой функции возрастает при этом на , причем прежний базис остается допустимым. То есть при увеличении данного ресурса на единицу дополнительная прибыль в оптимальном варианте составляет .

Рассмотренный анализ можно обобщить на случай варьирования одновременно нескольких констант в правых частях ограничений. Произведем одновременно следующие замены:

Если обратить в ноль все небазисные переменные, система уравнений (F) на последней симплексной итерации примет вид:

Коэффициенты дi (i=1,2,3) совпадают с коэффициентами при соответствующих остаточных переменных в (F). Базис остается допустимым, если x1, x6 и x3 неотрицательны. Следовательно, д1, д2 и д3 должны удовлетворять соответствующей системе неравенств.

Двойственность

Понятие двойственности является очень важным и полезным, так как позволяет связать в единую систему различные методы анализа на чувствительность. Рассмотрим две следующие задачи линейного программирования:

Назовем первую задачу исходной, а вторую - двойственной (по отношению к первой). В качестве примера рассмотрим задачу распределения ресурсов:

Двойственная задача имеет вид:

Грубо говоря, двойственная задача - это на 90 градусов повернутая исходная задача. Действительно:

1) j-й столбец коэффициентов в ограничениях исходной модели совпадает с j-й строкой коэффициентов в ограничениях двойственной задачи;

2) строка из коэффициентов целевой функции совпадает со столбцом из констант в правых частях ограничений двойственной модели;

3) столбец из констант, стоящих в правых частях ограничений исходной модели, совпадает со строкой из коэффициентов целевой функции двойственной модели;

4) направление знаков неравенств в исходной модели противоположно направлению знаков неравенств в двойственной модели, требование максимизации в исходной задаче заменено в двойственной модели требованием минимизации.

Имеют место две важные теоремы.

Теорема 1 - теорема двойственности: если исходная и двойственная ей задачи имеют допустимые решения, то:

1) существует оптимальное решение x*j (j = 1, n) исходной задачи;

2) существует оптимальное решение y*i (i = 1, m) двойственной задачи;

3) имеет место соотношение:

Если исходная задача имеет неограниченное оптимальное решение, соответствующая ей двойственная задача вообще не имеет допустимых решений.

Теорема 2 - теорема о дополнительной нежесткости: пусть x*j (j = 1,n) - решение исходной задачи, a y*i (i = 1,m) - решение соответствующей двойственной задачи. Оба решения являются оптимальными тогда и только тогда, когда:

Отсюда вытекает, что всякий раз, когда модель содержит ограничение, принимающее после подстановки оптимального решения вид строгого неравенства, соответствующая переменная двойственной задачи принимает нулевое значение.

Для решения двойственной задачи можно использовать рассмотренный выше симплексный алгоритм. Но если решена исходная задача, то решение двойственной задачи является избыточным, так как справедливо:

а) коэффициенты при остаточных переменных в строке 0 на последней симплекс-итерации при решении исходной задачи совпадают с оптимальными значениями переменных двойственной задачи;

б) коэффициент при xj в строке 0 на последней симплекс-итерации представляет собой разность между левой и правой частями j-ro ограничения двойственной задачи, соответствующего оптимальному решению последней.

В качестве примера опять рассмотрим задачу распределения ресурсов. Из (F) видно, что оптимальные значения переменных двойственной задачи следующие:

При этом значение целевой функции двойственной задачи совпадает с значением целевой функции исходной задачи:

Наконец, вычислим разность между левыми и правыми частями ограничений двойственной задачи.

Например, для второго и третьего ограничений находим:

,

то есть, получаем соответственно коэффициенты при x2 и x3 в строке 0 системы (F).

Приложение Б (справочное)

Руководство пользователя

Данная система разработана в среде разработки и технологии программ Delphi2009, которая ориентирована на работу в Windows. В основе идеологии Delphi лежит технология визуального проектирования и методология объектно-ориентированного программирования (программирования процедур обработки событий), применение которых позволяет существенно сократить время разработки и облегчить процесс создания приложений (программ, работающих в Windows).

Система представляет собой три Windows-приложения:

1) приложение для студентов (Контрольная АИУС.exe) - тренажер по алгоритму Симлекс-метода и генератор заданий на контрольную работу;

2) приложение для преподавателя (Проверка.exe) - модифицированное приложение Контрольная АИУС.exe, в котором реализован еще и блок «Проверка решения»;

3) приложение «Экзамен» (Экзамен.exe) - автоматизированная система для генерации заданий при проведении экзамена, проверки введенных решений и сохранения результатов.

После запуска программы Контрольная АИУС.exe выводится основное окно «АИУС Симплекс-метод» (рис. Б.1), которое позволяет студенту перейти к работе с тренажером, начать, либо продолжить выполнение контрольной работы, обратиться к модулю помощи через функцию «Справка» или узнать сведения о программе.

Для перехода к работе с тренажером необходимо использовать кнопку «Тренажер», которая находится в левом верхнем углу в панели управления. После чего в появившемся окне «Тренажер» предоставляется на выбор функции «Начать решение Симплекс-методом», «Начать анализ чувствительности» и «Начать решение двойственной задачи», каждая из которых соответствует указанному в названии разделу.

Рисунок Б.1 - Экранная форма основного окна приложения Контрольная АИУС.exe

После нажатия одной из указанных кнопок появится соответствующее окно либо «Тренажер - Симплекс-метод», либо «Тренажер - Анализ чувствительности», либо «Тренажер - Двойственная задача». В окне «Тренажер - Симплекс-метод» и «Тренажер - Двойственная задача» в левом верхнем углу будет отображена исходная модель задачи, а в окне «Тренажер - Анализ чувствительности» отображается результат заключительной итерации решения задачи Симплекс-методом. Процесс работы с приложением «Тренажер» сопровождается подсказками о необходимости ввода тех или иных данных. Нажатие кнопки «Проверить» или «ОК» после ввода данных позволяет проверить верность полученных значений. В случае положительного прохождения проверки, система автоматически обновляет данные для запроса и последовательно продолжает весь курс раздела «Линейное программирование».

Из основного окна приложения Контрольная АИУС.exe можно перейти к методическим указаниям к контрольной работе по дисциплине АИУС. Для чего в панели управления выбрать в меню «Справка» раздел «Help». Появившееся окно «Simplex» является приложением формата Windows-справки. Для навигации по разделам необходимо пользоваться проводником в левой части окна.

Система позволяет начать выполнение контрольной работы. В основном окне приложения Контрольная АИУС.exe нажать кнопку «Новая контрольная работа». После чего в появившемся окне «Данные студента» вводятся ФИО, группа и e-mail студента в соответствующие поля. Если все данные введены, кнопка «Получить задание» станет активной. При нажатии указанной кнопки выводится сообщение о создании и сохранении файла с заданием в директории приложения. Нажав кнопку «ОК» перейдете к выполнению контрольной работы.

Окно «Контрольная работа» разделено на две горизонтальные части. В верхней части отображаются исходные данные к контрольной работе, а также кнопки «Вперед» и «Назад» для переключения между разделами контрольной работы. Нижняя часть ограничена рамкой, имеет название соответствующее разделу контрольной работы и поля для ввода. Все поля снабжены комментариями о том, какие данные необходимо ввести. При закрытии окна все введенные данные автоматически сохраняются в файл.

При необходимости продолжить выполнение контрольной работы нажмите кнопку «Продолжить выполнение контрольной работы». В появившемся диалоговом окне открытия файлов выберите папку соответствующую инициалам и группе студента выполнявшего задание. Внутри папки лежат файл с датами последнего редактирования. Выбрав соответствующий файл задания, переходим к окну «Контрольная работа» в котором будут выведены исходное задание и уже сохраненные результаты.

После завершения выполнения контрольной работы директорию с инициалами и группой студента в названии необходимо отправить преподавателю.

Запуск приложения Экзамен.exe вызывает окно «Экзамен по дисциплине АИУС» (рис. Б.2). В указанном окне требуется ввести данные студента (ФИО, группа), после чего активной становится кнопка «Выполнить экзамен».

Рисунок Б.2 - Экранная форма основного окна приложения Экзамен.exe

После нажатия кнопки «Выполнить экзамен» появится окно экзамена, в заголовке которого указывается фамилия, имя и группа студента выполняющего экзамен. Окно содержит несколько вкладок с номером задания. Количество и формирование заданий определяется в файле настроек преподавателем. На каждой вкладке заданий представлены исходные данные, само задание и поля для ввода ответа. Поочередно переключаясь между вкладками необходимо вводить ответы. После того, как все ответы будут введены, требуется в панели управления окна нажать кнопку «Завершить проверить». Нажатие это кнопки блокирует дальнейшее изменение введенных ответов. Система автоматически проверяет все ответы и выводит правильные варианты ответа во всех заданиях. В нижней части окна будет отображена панель с общим количеством правильно выполненных заданий и указание о верности, либо ошибочности каждого задания. Возможность переключения между вкладками заданий сохраняется, что позволяет посмотреть и сравнить введенные ответы, с теми, что получила система. Преподаватель на основе этих данных выставляет баллы или оценку за экзамен.

Размещено на Allbest.ru