2014 dxdy logo

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

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




 
 ЗЛП с нецелочисленным решением
Сообщение03.02.2012, 08:42 
Здравствуйте.

Имеется задача лин.программирования:
Предприятие оптовой торговли, исходя из специализации, может реализовать два вида товаров. Лимитируемые при этом ресурсы и нормы расхода на единицу реализуемых товаров представлены в таблице.

Изображение

Определить план реализации по видам товаров, при котором общая прибыль торгового предприятия будет максимальной.


Решением получилось такое: $\[
x_1  \approx 705.88,\,\,\,x_2  = 0
\]
$. Может ли быть такое? Ведь это количество единиц товара! И нецелое значение.

Спасибо.

 
 
 
 Re: ЗЛП с нецелочисленным решением
Сообщение03.02.2012, 10:48 
Аватара пользователя
NatNiM в сообщении #534397 писал(а):
Ведь это количество единиц товара!
А какие там "единицы"? Тонны?

А вообще, существует целочисленное линейное программирование. Там к симплекс-методу добавляются дополнительные построения, чтобы получить целочисленное решение. Ищите метод Гомори, если он Вам действительно нужен.

 
 
 
 Re: ЗЛП с нецелочисленным решением
Сообщение03.02.2012, 11:50 
Someone в сообщении #534418 писал(а):
NatNiM в сообщении #534397 писал(а):
Ведь это количество единиц товара!
А какие там "единицы"? Тонны?

Да, вы правы. Единицы там не указаны, но действительно могут быть тонны. Не подумала об этом.
Спасибо.

 
 
 
 Re: ЗЛП с нецелочисленным решением
Сообщение03.02.2012, 12:09 
Аватара пользователя
Вообще, тот факт, что быстрый, понятный и эффективный метод решения задач ЛП - симплекс-метод - может приводить к нецелочисленным решениям, а по смыслу задачи они недопустимы, и потребовал создания сложных и куда более медленных методов решения задач целочисленного линейного программирования. Кроме Гомори - ещё ветви и границы и некоторые другие.
Иногда везёт с постановкой задачи. Так, в транспортной задаче матрица коэффициентов абсолютно унимодулярна, решения целочислены, и "два землекопа и $\frac 2 3$" не получится.

 
 
 
 Re: ЗЛП с нецелочисленным решением
Сообщение03.02.2012, 12:50 
Но здесь и в самой постановке задачи, например, используется 1,5 человека/час.

 
 
 
 Re: ЗЛП с нецелочисленным решением
Сообщение03.02.2012, 16:31 
Аватара пользователя

(Оффтоп)

Тут все зависит от состояния мозгов у составителя задачи и принимающего. Но я бы здесь не увидел задачу целочисленного программирования особенно без особых указаний.

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group