2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3  След.
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 13:45 
Заслуженный участник
Аватара пользователя


13/08/08
14494

(Оффтоп)

Joker_vD, какой райцентр? Какие свиньи?
Вы определённо не в теме :-)
Это же олигархическая деревня. Там и школы элитные, специализированные. На 25 персон. При этом персонала человек 200. В классе 3-4 ученика. Урок ведут одновременно 6 преподавателей, психолог, юрист, гувернёры и гувернантки. Ну и прочая обслуга. Преподаватели одеты и загримированы соответственно теме урока. Геометрию ведут Пифагор с Эвклидом, физику — Эйнштейн и Паскаль. На уроки зоологии приводят изучаемых животных. У каждой школы своя обсерватория, спортивный комплекс. Поле для гольфа вот одно на всех.


А что такое аморфная задача?
Я думал, Вы всерьёз про амфорную. Это название действительно было в Древней Греции. Вино и масло разливали в амфоры и надо было для определённого объёма жидкости подобрать набор амфор, в которые она бы вместилась. По существу, это и есть Ваша задача. Диофант Александрийский и начал свои исследования с амфорных задач. Но там была ещё куча особенностей, связанных с "требованиями богов". Например, он уже использовал то, что при заданной форме объём амфоры зависит от куба размера, а площадь расписываемой поверхности от квадрата.

Ну в общем, теория этих задач уже достаточна развита в линейном программировании.

+++ Я имел в виду тему http://dxdy.ru/topic43521.html

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 13:49 


25/03/10
590
Да не, это я пример попробовал составить жизненный. Говорю же задача аморфная. В начальном сообщении я формулировал с автобусами: как рассадить такое-то количество людей по стольким-то таким-то типам автобусов.

-- Сб июн 23, 2012 13:51:31 --

Поискал по форуму. Нашел только новое сообщение нового участника, без ответов: http://dxdy.ru/topic60253.html. Но Он спрашивает про точное равенство, а в моей задаче действительно перекрываться могут числа и даже должны, если не слишком сильно.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 14:56 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Вы хотите решить три разные задачи.
Первая: найти число натуральных (с нулём) решений некоторого диофантового уравнения (двойного неравенства).

Вторая: построить некоторый алгоритм, который построит все эти решения.

Третья: найти на множестве решений экстремум некоторой функции.

Для третьей задачи вовсе не обязательно решать первые две. Более того, количество решений может быть очень велико, а методы решения экстремальных задач как раз призваны, чтобы существенно сократить число проверяемых вариантов.

Например, в задаче нахождения максимума функции $f(n,m)=64+243n-3n^2+310m-4m^2$ для натуральных $n, m:  n+m=499$ нет необходимости проверять все 500 вариантов.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 18:39 


25/03/10
590
А как составить из начальных данных функцию, максимум которой потом искать?

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 18:54 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Вот для этого и нужно вначале разработать математическую модель задачи.
На примере школ. У нас есть три варианта: 50+50, 50+25+25, 25+25+25+25, но как из сравнивать?
В реальной жизни, естественно, влияют и расположение школ, и стоимость их постройки и куча других параметров, но у Вас же упрощённая модель. То есть желательно оценить каждый вариант одним числом, получающимся по некоторой формуле.
Возможно, каждая 50-местная школа приносит 3 очка, а 25-местная — 2. Тогда варианты оцениваются в 6, 7 и 8 очков. Побеждает третий.
А если каждая 50-местная школа приносит 5 очков, а 25-местная — 2, то варианты оцениваются в 10, 9 и 8 очков. Побеждает первый.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 19:30 


25/03/10
590
gris в сообщении #588264 писал(а):
У нас есть три варианта: 50+50, 50+25+25, 25+25+25+25, но как из сравнивать?

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

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 19:35 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Формула чего? Количества решений? Зачем Вам количество?
Формулу каждого варианта в зависимости от его номера? Мне кажется, что она если и существует, то настолько же пригодна, как формула n-ного простого числа.
Вы бы уж показали свою практическую задачу.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 19:39 


25/03/10
590
Формула не количества решений, а сами решения - те варианты, на которое одно число можно разложить на другие.

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

(Оффтоп)

Представьте очень большое число и много маленьких чисел. Требуется представить варианты разложения большого числа на маленькие.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 19:50 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Да я понимаю.
Можно составить алгоритм, а наверняка он уже и описан достаточно подробно, по которому будут подбираться варианты, потом оцениваться. Но их может быть очень много, особенно при приближённом равенстве суммы.
А если целевая функция хорошая (выпуклая, линейная), то не будет необходимости их все рассматривать.
Вот пример: разменять миллион плюс-минус сто рублей старинными монетами в 1,2,3 и 5 коп. Сколько там вариантов? Уж наверняка много.
А надо, например, минимизировать совокупную себестоимость всех монет (а себестоимость однотипных монет не прямо пропорциональна их номиналу). Или совокупную разность между количеством монет разных номиналов. В этом случае задачу можно и врукопашную решить.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 20:10 


25/03/10
590
gris в сообщении #588278 писал(а):
Можно составить алгоритм, а наверняка он уже и описан достаточно подробно, по которому будут подбираться варианты, потом оцениваться.

К сожалению, я не знаю как составить алгоритм и не знаю где он описан.

gris в сообщении #588278 писал(а):
Но их может быть очень много, особенно при приближённом равенстве суммы.

Да, мне нужно именно приближенное равенство. Но не думаю что вариантов уж слишком много. Опишу чуть ближе к делу форму задачи.

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

gris в сообщении #588278 писал(а):
А если целевая функция хорошая (выпуклая, линейная), то не будет необходимости их все рассматривать.

Ну, хотелось бы по шагам. Сначала получить варианты на первом шаге. А на втором уж выбирать.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 20:18 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Ну так тем более одной совокупной мощностью не обойтись. Знаем мы эти локации. Потребление неравномерное, со скачками, расположены тоже неравномерно, стоимость прокладки кабелей везде разная, стоимость строительства подстанций разная, да ещё не везде их построишь. Да, это задача сложная.
Нахождение всех вариантов распределения мощности такой пустяк по сравнению с прочими расчётами.

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 20:26 


25/03/10
590
Да, да, да! Но как хоть пустяк-то решить?

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение23.06.2012, 20:38 
Заслуженный участник
Аватара пользователя


13/08/08
14494
Я бы без особых раздумий нашёл максимальное число подстанций каждого типа, покрывающих суммарную мощность плюс процентов пять. Потом запустил кратный цикл, в котором бы тупо суммировал мощности и выводил те варианты, которые близки к итоговой цифре. Алгоритм дико неэффективный, да компу всё равно делать нечего. Самое простое, что можно придумать.

Вот Вам пример. Разложить примерно тысячу на слагаемые 27, 59 и 134.

Код:
N=1000; K=0;
m1=27; m2=59; m3=134;
for (k1=0;k1<40;k1++) {
   for (k2=0;k2<17;k2++) {
      for (k3=0;k3<9;k3++) {
         NK=k1*m1+k2*m2+k3*m3;
          if (Math.abs(NK-N)<3) {K=K+1;trace (NK+"="+k1+"*"+m1+"+"+k2+"*"+m2+"+"+k3+"*"+m3)}
}}}
trace ("Всего "+K+" вариантов")


Код:
998=2*27+16*59+0*134
998=3*27+11*59+2*134
998=4*27+6*59+4*134
998=5*27+1*59+6*134
999=8*27+11*59+1*134
999=9*27+6*59+3*134
999=10*27+1*59+5*134
1000=13*27+11*59+0*134
1000=14*27+6*59+2*134
1000=15*27+1*59+4*134
1001=19*27+6*59+1*134
1001=20*27+1*59+3*134
1002=24*27+6*59+0*134
1002=25*27+1*59+2*134
998=32*27+0*59+1*134
999=37*27+0*59+0*134
Всего 16 вариантов

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение24.06.2012, 01:31 


25/03/10
590
Ой как здорово, вот это да!!! Я думал как написать что-то подобное, но у меня не получилось( А у в вашем коде даже учитывается не только точное разложение, но и близкое к 1000!

-- Вс июн 24, 2012 01:33:31 --

Я только не понял откуда эти ограничители взялись, откуда эти цифры:
Код:
k1<40;
k2<17;
k3<9;

и ещё хотел спросить на каком языке ваш код? Я только Паскаль обыкновенный знаю, но если пойму алгоритм, то переложить смогу, но все равно интересно где такой элегантный код пишется?

-- Вс июн 24, 2012 01:35:16 --

gris в сообщении #588305 писал(а):
Код:
Всего 16 вариантов

Алгоритм же 15 выдал, откуда 16?

-- Вс июн 24, 2012 01:37:45 --

Я правильно понял, что вы именно следующим:
gris в сообщении #588305 писал(а):
Код:
Math.abs(NK-N)<3)

указали чтобы и близкие к 1000 (от 1998 до 1002) разложения проделывал, да?

 Профиль  
                  
 
 Re: Комбинации школ из 50 и 25 мест для 100 учеников
Сообщение24.06.2012, 02:11 
Заслуженный участник


09/09/10
3729

(Оффтоп)

Это Си/Си++, и элегантного в этом языке мало.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 37 ]  На страницу Пред.  1, 2, 3  След.

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



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

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


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

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