Как сформулировать задачу линейного программирования ?

[ishak]

Допустим, вектор целевой функции F - вектор единичный.
Требуется найти не только оптимальный вектор Х при заданном векторе
ограничений В и заданном векторе целевой функции F0, но и вектор F1
при котором Х остается оптимальным и целевая функция FХ(скалярное произведение)
достигает своего максимума.Т.е. дополнительно к решению классической задачи
лин.программирования требуется еще найти вектор F1 "ближайший" к полученному
вектору Х. Заранее благодарен за ссылки и комментарии.

[reader_st]

ishak

Я не знаю как остальным, а мне что-то не понятно. Вы не могли бы привести исходную формулировку задачи.

[ishak]

Допустим, мы решили задачу линейного программирования и нашли решение Х при заданном единичном векторе целевой функции F0.
Очевидно , что найденный Х останется оптимальным для некторого множества единичных векторов целевой функции.Требуется найти
такой F1 из этого множества, для которого при заданном Х целевая функция FX(скалярное произведение) достигает своего максимума.
Известна ли такая постановка задачи и методы ее решения ?

[reader_st]

ishak

Насчет постановки задачи я Вам ничего сказать не могу. Поставить можно любую задачу, а методов решения сколько угодно. Скалярное произведение линейная функция, т.к. вектор X уже известнен, то накладывая ограничения на F1, скажем положительность, можно по-моему, получить линейную задачу.Т.е.
$FX \quad \to \max$
при
$F\ge 0.$

Во второй задаче, которую, если я правильно понял и записал, Вы просто изменили коэффициенты перед неизвестными(они равны соответствующим значениям X)

[ishak]

Ограничения на F1 возможны , но не необходимы. Такой F1 существует и может быть найден ,на мой взгляд, и без наложения дополнительных ограничений.Предполагаю, симплекс- метод здесь не пригоден.
А поставить ,действительно, можно любую задачу с экономическим смыслом или без.

[reader_st]

ishak писал(а):

Цитата:

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

Здесь я не согласен. Если исходная задача имела некий смысл, кроме математического, в том что ее просто надо решить, то ограничения на F1 накладываться должны. Иначе можно получить недопустимое решение. Относительно симплексного метода. Если ограничения Вы не накладываете, то это уже задача просто на нахождения максимума и решить ее можно используя численные методы безусловной минимизации(при линейной-то целевой функции), а если ограничения есть, то у Вас есть алгоритм, который дает Вам решение и отказываться от него, в пользу численных методов я бы не стал, если решение конечно можно найти.

[ishak]

Почему не нужны дополнительные ограничения для F1?
Возьмем 2-мерный случай. Проведем оси х1 и Х2 .
Два ограничения -неравенства задаются двумя пересекающимися прямыми.
Пусть Точка пересечения прямых и есть решение Х при некотором F0.
В точке пересечения прямых проведем два вектора, каждый из которых ортогонален соответствующей прямой. Эти два вектора и ограничивают область возможных значений для целевого вектора и F0 ,конечно, "лежит между" ними (иначе задача не ограничена). Если вектор найденного решения Х "лежит между " ними,то F1 коллиненарен Х. Если Х "не лежит между" ними ,то F1 коллинеарен ближайшему вектору-ограничителю.
Этот пример графического решения для Х и F1 приведен для того ,чтобы показать с одной стороны ненужность дополнительных ограничений (хотя они и возможны), с другой стороны неприменимость (на мой взгляд) симплекс-метода.

[reader_st]

ishak

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