C, PHP, VB, .NET

Тази задача е породена от реална такава. Всъщност е по-опростена, отколкото е реалната - в края на статията ще кажа защо.

Нека имаме "k" на брой производители p₁, ..., p_k и "i" на брой клиенти c₁, ..., c_i. Абсолютно задължително е всеки клиент да може да получи точно един продукт, т.е. общото производство на продукти трябва да е "i" на брой. Приемаме, че производителите могат да произвеждат продуктите със сходно качество, т.е. нямаме ефекта както на нормалния пазар един производител да прави качествени, а друг калпави стоки - продуктите им са с еквивалентно качество. Въпреки това клиентите имат свои предпочитания - те предпочитат повече един производител спрямо друг на базата на субективни критерии, мода и т.н. За съжаление не е винаги възможно клиентите да получат обслужване от която фирма поискат, защото производителите имат свой капацитет - p₁ нормално може да произведе p'₁ стоки, p₂ нормално може да произведе p'₂ стоки, и т.н. Защо казваме "нормално" - защото е допустимо даден производител да се натовари повече от своя капацитет, но в такъв случай той започва да "претупва" производствения процес и съответно качеството на стоката започва да спада. Прието е, че при до 100% от натоварването си качеството е отлично, а по-нагоре равномерно до 100+X% качеството ще падне до нула и производителя ще произвежда пълен боклук, т.е. ще прецаква клиентите си (точната стойност на X приемаме за фиксирана - константна). Поради тази причина регулаторът е създал система, с която цели да разпределя клиентите към производителите. Всеки клиент подава молба, в която описва своите топ 3 производители (но не е задължително, че в крайна сметка ще получи продукт от някой от тях - може да бъде разпределен и служебно ако неговите желания не могат да се удовлетворят). След това всеки клиент бива оценен по обективни критерии и получава c'₁, ..., c'_i на брой точки. На базата на тези точки се изготвя класиране и клиентите се разпределят към даден производител.

Задача. Предложете начин за разпределение (кой клиент от кой производител ще получи продукт), при което да се получи максимално качество за всички клиенти погледнато като цяло, което разпределение същевременно да покрива доколкото се може повече личните предпочитания на клиентите.

Моите размишления: Задачата е сравнително лесно решима ако капацитетът на производителите (p'₁ + p'₂ + ... + p'_k) превишава или е равен на броя на клиентите (i). В този случай може да се направи класиране както за училищата след 7-ми клас - според броя точки до запълване на капацитета на конкретното училище (капацитет на производител), след това второ и накрая трето класиране (в зависимост от останалите места в другите му желания), а тези, които не са приети в нито едно от желанията си, да се разпределят служебно в училище, което все още има свободен капацитет (такива ще има винаги, защото капацитетите превишават броя на учениците). Тоест един вариант, което е и моето предложение за решение, тук е:

• Запълване на капацитета на най-предпочитаните производители според желанията на клиентите;
• Всички останали, които не са класирани по свое желание, се разпределят равномерно според наличните капацитети на производителите.

По-неприятният момент настъпва когато p'₁ + p'₂ + ... + p'_k < i. В този случай ние имаме нужда от повече продукти, отколкото е общия капацитет на производителите - ще имаме неминуема деградация на качеството. Въпросът е, че тази деградация трябва да се минимизира. Дерзайте... Ето няколко груби варианти за първоначална насока на ръзсъжденията:

• Математически максимум за качество - първо запълваме капацитета на всички производители. След това "жертваме" един производител и преразпределяме всички останали клиенти към него. Така постигаме максимум качество, но... удовлетвореността на клиентите естествено ще е под въпрос (всички разпределени към жертвания производител ще са недоволни);
• Равномерно разпределение без значение от капацитета - броя клиенти се разделя на броя производители и всеки производител получава по равно клиенти с останалите производители. В този случай оптималност не е гарантирана заради различните капацитети на различни производители. Може някой производител с малък капацитет да се претовари значително, включително до невъзможност да изпълни задачата (... е, това го няма в условието), докато производител с голям капацитет да остане незапълнен (така със сигурност ще се наруши оптималността);
• Равномерно разпределение според капацитетите - делим общия брой на клиентите на общия сбор от капацитетите, т.е. i/(p'₁ + p'₂ + ... + p'_k). Полученият коефициент е "коефициент на претоварваме", който всеки производител трябва да направи. Тоест производител j ще трябва да обслужи p'_j*i/(p'₁ + p'₂ + ... + p'_k) на брой клиенти. Без да съм правил задълбочен анализ, струва ми се че има хляб в тази идея, но още на първо четене е ясно, че оптималността не е или не винаги е тук. Представете си огромно число i - такова, че коефициента на претоварване стане огромен. В такъв случай всички производители ще се претоварят и качеството на всички ще деградира до 0. Очевидно е, че има решения, при които общото качество няма да е 0, независимо колко на брой са клиентите;
• Максимално допустим праг - фиксира се "магическо число", например "производител не може да произвежда повече от X продукта", което число се определя според броя клиенти с известни допълнителни бройки над капацитета. По този начин се предотвратява прекомерно претоварване на даден производител, но обслужва максимално добре личните предпочитания на клиентите. Тук проблемът е да се намери точната стойност на X;
• Пазарен принцип - всеки да бъде разпределен както той желае, а в крайна сметка се приема, че с времето пазара ще урегулира нещата и те ще се самонагодят към оптималното решение (тук обаче има презумпция, че клиентите желаят качествена стока на всяка цена - това не е гарантирано, а освен това не е ясно колко време ще отнеме тази практика, дали няма да има нелоялна конкуренция и т.н.);
• Други - предложете ги...

П.П. В реалната задача става въпрос за още по-сложен сценарий защото:

• Колкото и да се стараем, качеството на продуктите все пак е различно при различните производители;
• Продуктите всъщност са от няколко различни типа - някои от тях съвместими, други напълно несъвместими (не можете да дадете на клиент искащ продукт от един тип друг продукт, който е несъвместим с него);
• Възможно е клиент категорично да не желае конкретен производител - тогава независимо от качеството на продукта резултата ще е негативен;
• В горната задача съм изказал лично предположение, че при 100+X% натоварване при всички качеството спада до 0. Реално за всеки различен производител този праг е различен, при това е много трудно да бъде определен!