- •Глава 2. Оптимизационные задачи экономики
- •2.1. Основы линейного программирования (лп)
- •2.1.1 Формализация задачи
- •2.1.2 Симплекс-метод
- •2.2. Введение в квадратичное программирование
- •2.2.1 Задачи квадратичного программирования (кп)
- •2.2.2 Задачи выпуклого программирования
- •3.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). Ясно, что если
положительны, то оно выполняется когда
.
Если же
,
то оно выполняется не для любых
,
а только для тех, которые удовлетворяют
условию
Таким образом, чтобы выполнить условие неотрицательности переменных, возможно увеличивать переменную только до значения
При
базисная переменная
первой обратиться в нуль. Тогда вновь
найденный вектор
будет новым базисным решением (он даст
координаты новой вершины симплекса), в
котором базисную переменную
заменит ставшая теперь базисной
переменная
.
Подытоживая сказанное, отметим, что симплекс-метод сходится за конечное число шагов, так как выпуклый многогранник имеет конечное число вершин. Один шаг симплекс-метода заключается в следующем:
для всех небазисных переменных вычисляются симплекс-разности по формуле (2.15);
определяется максимальная симплекс-разность. Если она положительна, то переходим к пункту 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 – Результаты поиска решения.
