2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Как сформулировать задачу линейного программирования ?
Сообщение23.10.2006, 17:51 


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

 Профиль  
                  
 
 
Сообщение23.10.2006, 18:38 
Заслуженный участник
Аватара пользователя


03/03/06
648
ishak

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

 Профиль  
                  
 
 
Сообщение24.10.2006, 10:38 


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

 Профиль  
                  
 
 
Сообщение24.10.2006, 12:44 
Заслуженный участник
Аватара пользователя


03/03/06
648
ishak

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

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

 Профиль  
                  
 
 
Сообщение24.10.2006, 13:17 


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

 Профиль  
                  
 
 
Сообщение24.10.2006, 14:04 
Заслуженный участник
Аватара пользователя


03/03/06
648
ishak писал(а):
Цитата:
Такой F1 существует и может быть найден ,на мой взгляд, и без наложения дополнительных ограничений.Предполагаю, симплекс- метод здесь не пригоден.
А поставить ,действительно, можно любую задачу с экономическим смыслом или без.


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

 Профиль  
                  
 
 
Сообщение24.10.2006, 16:18 


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

 Профиль  
                  
 
 
Сообщение24.10.2006, 20:06 
Заслуженный участник
Аватара пользователя


03/03/06
648
ishak

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: zhoraster, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group