Разбор сетевой задачи из книги (линейное программирование): "эквивалентные задачи"

Здравствуйте!

Изучаю книгу Х. Таха: "Введение в исследование операций".

В качестве одного из примеров и вариантов применения метода линейного программирования (пример 6.3.2). в книге рассматривается задача нахождения кратчайшего пути между двумя точками. "Фишкой" задачи являлось то, что длина дуги задана НЕ классической длинной (или стоимостью), а вероятностью "успеха" (т.е. числом менее единицы). В книге этот "успех" интерпретируется как "вероятность НЕ БЫТЬ остановленным полицейским". Хотим эту вероятность максимизировать.

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

1. Каковы условия логарифмирования выражений (уравнений)? И вообще есть ли такие условия...Т.е. когда можно логарифмировать, а когда нет...Параметры должны быть обязательно положительными или есть еще что-нибудь...

2. В книге написана вот такая фраза "с точки зрения математики задача макс. вероятности p эквивалентна задаче максимизации величины log p". Вот это и не понятно, почему "эквивалентна" и когда вообще можно говорить об эквивалентности...
Прием известный и часто его встречаемый, когда мы заменяем функцию на другую, более простую или известную, смотрим максимум или минимум на ней, а потом распространяем свои выводы на неизвестную функцию ....

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

Но не хватает кругозора: когда так можно делать, какие функции эквивалентны и как это доказывается? Можно ли увидеть примеры?

0

Сообщение от litvinj вероятности p эквивалентна задаче максимизации величины log p". Вот это и не понятно, почему "эквивалентна" и когда вообще можно говорить об эквивалентности...

Эквивалентность здесь понимается в след. смысле.
Если две функции f(x), g(x) имеют одинаковый характер монотонности (например, на интервале (a,b) обе озрастают, а на интервале (b,c) обе убывают), то они имеют одну и ту же точку максимума (точку b).
Пример. Функции f(x) = x, g(t) = ln(t), q(x)=ln(f(x))=ln(x) возрастают на отрезке [1,2] и имеют одну и ту же точку максимума х=2 на отрезке [1,2]. Это замечание позволяет заменить сложную задачу на экстремум более простой.

0

Сообщение от litvinj 1. Каковы условия логарифмирования выражений (уравнений)? И вообще есть ли такие условия...

Формально, логарифм по основанию можно взять от любого строго положительного числа. Так как вероятности (крайние значения р не берём), то логарифм по основанию >1 будет <0.

Сообщение от litvinj когда вообще можно говорить об эквивалентности...

Можно говорить о такой эквивалентности, когда функция от р монотонно возрастает на промежутке изменения р. Если основание логарифма >1, то так и есть.
Повикипедьте график логарифмической функции . Или вспомните 10-й класс школы, когда это учится.

0