Оглавление:
Параметризация целевой функции
Рассмотрим алгоритм метода взвешенных сумм на примере параметризации целевой функции для задачи ЛП с одним критерием (см. разд. 5.2).
Исходная задача имеет вид
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1971.png)
задан вектор изменения , который определяет изменения координат целевой функции; вводится параметризованный (суммарный) градиент целевой функции
т.е.
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1976.png)
Отсюда находим последовательность параметрически оптимальных крайних точек (и ребер) при изменении от 0 до
. Точка
называется параметрически оптимальной, если она максимизирует величину
для некоторого значения
. При использовании метода взвешенных сумм вводится выпуклая комбинация векторов
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1987.png)
Тогда
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1988.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1989.png)
Между обоими подходами существует прямая связь:
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1990.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1991.png)
так как
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-1992.png)
Однако в первом случае вектор не достигает вектора
(только к нему стремится), во втором —
при
.
В поставленной задаче требуется определить критические значения или
и
, при которых новые базисы (крайние точки) становятся параметрически оптимальными (т.е. происходит смена базиса). Задача решается в три этапа:
- Находим допустимую крайнюю точку из области
— для решения симплекс-методом задачи ЛП
при
.
- Решаем задачу ЛП
при
— получаем исходный параметрически оптимальный базис.
- Заменяем градиент
на
и находим остальные параметрически оптимальные базисы (крайние точки), варьируя значения
от 0 до 1. При этом строка
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2018.png)
В процессе решения могут быть следующие варианты:
- Все небазисные элементы
. Отсюда — исходная точка уже оптимальна.
- Существуют внебазисные положительные элементы
,
т.е. найдется выпуклая комбинация, при которой ; небазисную переменную, соответствующую этому элементу, переводим в базис.
Берем тот элемент , который первым стал больше 0 при увеличении значения
.
Ближайшим большим критическим значением будет
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2057.png)
Значение , при котором дробь минимизируется, указывает на небазисную переменную, переводимую в базис, чтобы продолжить параметризацию по
.
Задача:
Для
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2060.png)
рассмотрим задачу параметрического ЛП с ограничениями
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2062.png)
(рис. 5.19).
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2063.png)
Решение:
Оптимальную исходную симплекс-таблицу (табл. 5.13) задачи ЛП
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2065.png)
дополним строкой где
— координаты вектора
стоящие в базисных
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2089.png)
столбцах; — элементы
-го столбца матрицы. Здесь
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2093.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2094.png)
слабые переменные.
Для небазисных переменных
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2095.png)
т.е. множество
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2096.png)
Критическое значение:
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2098.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2099.png)
при
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2100.png)
переменную надо перенести в базис (в таблице помечен генеральный элемент);
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2103.png)
Вектор ортогонален ребру
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2106.png)
строка
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2107.png)
Получаем табл. 5.14.
Здесь
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2108.png)
Только для столбца удовлетворяются условия
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2110.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2111.png)
Новое критическое значение
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2113.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2114.png)
переводим
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2115.png)
в базис;
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2117.png)
Вектор ортогонален ребру
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2118.png)
строка
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2119.png)
имеет вид
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2121.png)
Вводим в базис получаем
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2123.png)
Здесь
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2124.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2125.png)
процесс завершен.
В процессе ршения получили следующие подмножества множества , относящиеся к различным параметрически оптимальным крайним точкам и ребрам:
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2128.png)
Задача:
Методом взвешенных сумм проанализировать задачу МКЛП:
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2129.png)
при ограничениях
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2130.png)
(рис. 5.20).
Решение:
В данном случае суммарный градиент целевой функции
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2132.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2133.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2136.png)
Найдем подмножества Ё, принадлежащие различным параметрически оптимальным крайним точкам и ребрам. Решим задачу ЛП
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2137.png)
и добавим в полученную оптимальную симплекс-таблицу строки для
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2139.png)
(табл. 5.16). После решения задачи ЛП мы имеем начальную параметрически оптимальную крайнюю точку
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2140.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2141.png)
Анализируем строку
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2142.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2143.png)
Поскольку небазисные элементы строки должны быть неположительны в параметрически оптимальной крайней точке для всех
из подмножества
, соответствующего точке
, то имеем
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2148.png)
где
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2149.png)
или. учитывая
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2150.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2152.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2153.png)
Из этой системы получили
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2155.png)
Множество изображено на рис. 5.21.
Переводим в базис и переходим путем замещения методом Жордана в точку
= (2, 4) (табл. 5.17).
Для определения составим систему неравенств:
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2161.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2162.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2163.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2165.png)
Решив систему, получим
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2166.png)
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2167.png)
Множество изображено на рис. 5.22. Далее переходим в точку
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2169.png)
(табл. 5.18).
![Параметризация целевой функции](https://lfirmal.com/wp-content/uploads/2020/04/image-2171.png)
Эта теория взята со страницы лекций по предмету «математическое программирование»:
Предмет математическое программирование
Возможно эти страницы вам будут полезны: