Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Методы оптимизации.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
3 Мб
Скачать
☆

2.1.2 Симплекс-метод

Запишем расширенную задачу ЛП в матричном виде:

(2.8)

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

Если задачу (2.5) расширить, то она примет вид:

(2.9)

Базисное допустимое решение здесь очевидно. Базисными являются дополнительные переменные , а – небазисные или свободные переменные. Вектор решения имеет вид: . Чтобы улучшить это решение следует ввести в базис одну из небазисных переменных, а одну из базисных исключить. Таким образом определяются координаты очередной вершины симплекса. А ввод в базис и исключение из него преследуют цель максимизации целевой функции. В начальной точке она равна нулю. Для того, чтобы выбрать переменную для включения в базис, целевую функцию надо выразить через свободные переменные и выбрать ту, у которой максимальный по модулю коэффициент со знаком плюс. В нашем примере это переменная . Допустимое решение с участием переменной будет иметь вид:

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

в котором базисными переменными являются , а свободными .

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

Целевую функцию надо вновь выразить через небазисные переменные:

.

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

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

Из приведенного решения следует, что третий производственный процесс применять нецелесообразно, а доход при реализации оптимального плана составит 90$. При этом остаются неиспользованными 10,5 часов рабочего времени, т.е. оно не является дефицитным ресурсом.

После рассмотрения числового примера изложим классические вычислительные основы симплекс-метода.

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

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

(2.10)

Умножение слева формул (2.10) на матрицу дает возможность выразить базисные переменные через небазисные:

(2.11)

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

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

Решение будет базисным при и невырожденным при . Если роль небазисных переменных выполняют первоначальные переменные, а роль базисных – дополнительные, то такое базисное решение называется опорным.

Итак, пусть имеется хотя бы опорное базисное решение (оно всегда существует):

(2.12)

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

,

а базисные переменные примут следующие значения:

где -й столбец матрицы .

Новое решение будет иметь вид:

(2.13)

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

Таким образом, значение функции цели изменилось от исходного на величину

(2.14)

В последнем выражении коэффициент при переменной , равный

, (2.15)

называется симплекс-разностью для этой переменной.

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

или покоординатно

(2.16)

В выражении (2.16) это я координата базисного решения.

До какого значения можно увеличивать ? Ответ на этот вопрос следует из анализа неравенства (2.15). Ясно, что если положительны, то оно выполняется когда . Если же , то оно выполняется не для любых , а только для тех, которые удовлетворяют условию

Таким образом, чтобы выполнить условие неотрицательности переменных, возможно увеличивать переменную только до значения

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

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

  1. для всех небазисных переменных вычисляются симплекс-разности по формуле (2.15);

  2. определяется максимальная симплекс-разность. Если она положительна, то переходим к пункту 3), в противном случае выполнение алгоритма закончено, и оптимальное решение получено;

  3. в базис вводится переменная и выводится из него , для которой

Практическое решение задач ЛП наиболее целесообразно с использованием табличного процессора Excel, который содержится в офисном программном обеспечении Microsoft. Здесь мы рассмотрим работу табличного процессора при решении известной уже задачи (2.9). Решение задачи состоит из двух этапов. На первом этапе вводятся данные и настраиваются формулы таким образом, чтобы при произвольных значениях искомого вектора , компьютер вычислял текущее значение функции цели и фактические значения ограничений на каждой итерации. На втором этапе проводится моделирование параметров задачи с использованием оптимизатора табличного процессора – функции поиска решения.

Первоначально следует запустить Microsoft Excel. Затем необходимо настроить функцию поиска решений. Для этого из главного меню Сервис-Надстройки надо выбрать Поиск решения (рисунок 2.1).

Рисунок 2.1 – Выбор надстройки Поиск решения.

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

На рабочем листе Excel в соответствии с математическим описанием задачи следует определить место для варьируемых параметров, ввести формулы для функции цели и граничных условий (Рисунок 2.2). В качестве начальных значений искомых переменных вектора в варьируемые ячейки следует ввести нули. После ввода данных и ограничений Excel пересчитает все формулы и наша задача будет выглядеть так как показано на рисунке 2.3.

Рисунок 2.2 – Формульное сопровождение задачи ЛП.

Рисунок 2.3 – Вид экрана задачи ЛП, после ввода всех параметров.

На этом первый этап решения задачи можно считать законченным и следует перейти ко второму этапу. Запускаем Сервис-Поиск решения и настраиваем его параметры исходя из условия задачи (рисунок 2.4).

Рисунок 2.4 – Параметры оптимизатора Поиск решения.

Устанавливаем координаты целевой ячейки в $H$7. Будим искать максимальное значение функции цели, оно у нас выбрано по умолчанию. Изменяемые ячейки – это варьируемые переменные вектора , они расположены в блоке с координатами $A$5:$F$5. Ограничения вводятся с использованием кнопки Добавить (рисунок 2.5).

Рисунок 2.5 – Добавление ограничений.

Выбираем блок ячеек, в которых вычисляются фактические значения ограничений, он имеет координаты $H$9:$H$11. Ставим знак равенства и выбираем блок с заранее заданными значениями самих ограничений - $J$9:$J$11. Нажимаем кнопку OK.

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

Рисунок 2.6 – Настройка параметров поиска решения.

Выставляем птицы на пунктах Линейная модель и Неотрицательные значения, тем самым выполняем нижнее условие задачи (3.9). Возвращаемся в Поиск решения и запускаем его на выполнение кнопка Выполнить. Через секунду Excel найдет решение нашей задачи, о чем будет свидетельствовать окно результатов поиска решения рисунок 2.7. В нем предлагается вывести на отдельных листах три отчета по результатам, устойчивости решения и пределам, а также сохранить найденное решение. Бывают случаи, когда решение не может быть найдено и оптимизатор заполнит варьируемые ячейки последними значениями, на которых он остановился по алгоритму, тогда решение не следует сохранять.

В нашем случае решение найдено. Все ограничения и условия оптимальности выполнены. Максимум целевой функции достигается при значении 90 при этом , , и вектор решения полностью совпадает с рассчитанным выше оптимальным вектором числового примера.

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

Рисунок 2.7 – Результаты поиска решения.