Задача линейного программирования

Abdim59

Есть вот такая задача
 Объединение включает несколько химических предприятий. Каждое предприятие имеет возможность закупить 4 вида сырья по оптовой цене C(i) за единицу i-го вида сырья и приготавливать 3 вида смесей. Различные виды смесей в различных количествах a(p,i) содержат 3 ингредиента. Состав смеси i должен удовлетворять минимальным требованиям b(p,i) по включению ингредиента p(n). Максимально допустимое количество (в кг) сухих продуктов (в данной задаче первых 3-х используемых для составления смеси, равно 450кг. А использование 4-го вида сырья лежит в границах от 5 до 8 (включительно). Найти оптимальный состав смесей.
х(i,j) - количество i-го сырья в j-й смеси
  
Правильно ли я понимаю, что система получится такая:

И что-то я не пойму, что с ней дальше делать?

Abdim59

UP
Народ, очень надо! Помогите, плз. В долгу не останусь ;)

serengeti

попробуй посмотреть эту книжку: http://elib.hackers/books/1163
или кого-нибудь с четвёртого курса мм поискать :)

griz_a

В третьей сумме все правильно? a_{p,i} должно выноситься из-за знака суммирования?

a101

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

 
 Состав смеси i должен удовлетворять минимальным требованиям b(p,i) по включению ингредиента p(n)
 
Состав смеси - это величина нормированная на "количество" смеси или нет? То есть b(p,i) - это ограничение в "процентах" или в "килограммах". Дальше я буду считать, что b(p, i) - ограничение в "процентах".
 

 
А использование 4-го вида сырья лежит в границах от 5 до 8 (включительно).
 
Это на все вмеси вместе или на каждую? Как я понял, ты подразумеваешь что в сумме.
 
х(i,j) - количество i-го сырья в j-й смеси

Это тоже величина в килограммах или процентах? Одна из другой получается умножением на a_j. Буду считать, что в процентах.
Последний вопрос - a_j - это тоже неизвестные величины (как и x) или они фиксированы? Скорее всего это тоже неизвестные.
В "моем" понимании задачи система примeт вид.
\sum_{i=1}^4 x_{ij} = 1
x_{ij} >= b_{ij}
a_j (1 - x_{4j}) ( = a_j (x_{1j} + x_{2j} + x_{3j} ) <= 450 (вес сухой смеси меньше 450)
5 <= \sum_{j=1}^3 a_j x_{4j} <= 8
\sum_{i=1}^4 (C_i * \sum_{j=1}^3 a_j x_{ij}) -> min
 
ЗЫ
Сейчас подумаю, что с системой можно сделать. Если я что-то раньше понял не так, как нужно, то пиши )
ЗЫЫ
А значения b_{ij} нигде рядом не подписаны? ;)

3deus

Вся проблема в неясной формулировке. По-моему спрашивается следующее.
================
Объединение включает несколько химических предприятий. Каждое предприятие имеет возможность закупить 4 вида сырья по оптовой цене C(j) за единицу j-го вида сырья и приготовить 3 вида смесей q = 1, 2, 3. Различные виды смесей в различных количествах
 x (j,q) содержат 3 ингридиента (сырья) из четырех j = 1, 2, 3, 4. Состав смеси q должен удовлетворять минимальным требованиям b (j,q) по включению ингридиента j. Максимально допустимое количество (в кг) сухих продуктов (в данной задаче первых 3-х используемых для составления смеси q = 1, 2, 3 равно 450кг. А использование сырья j = 4 лежит в границах от 5 до 8 (включительно) КИЛОГРАММ. Найти оптимальный состав смесей по итоговой стоимости.
=============
Но все равно не понятно, зачем писать "объединение предприятий" ?
Теперь нетрудно составить систему уравнений и неравенств и условие оптимальности.

a101

Опс, в моем понимании (если a_j - переменные) это не получается задачей линейного программирования судя по получившейся системе. А вот если взять x_{ij} как массу ингридиента в смеси (то есть умножить их все на a_j то получится
 
\sum_{i=1}^4 x_{ij} = a_j
x_{ij} >= a_j * b_{ij}
\sum_{i=1}^3 x_{ij} <= 450
5 <= \sum_{j=1}^3 x_{4j} <= 8
\sum_{i=1}^4 C_i * (\sum_{j=1}^4 x_{ij}) -> min
 
Вот теперь это задача линейного программирования.
При этом, если b_{ij} это ограничение не на состав, а на количество ингридиента смесли, то первые два уравнения
\sum_{i=1}^4 x_{ij} = a_j
x_{ij} >= a_j * b_{ij}
надо заменить на одно
x_{ij} >= b_{ij}
При этом a_j перестанут использоваться.

3deus

Пусть j_q отсутствующий компанент в смеси q, т.е. x_{j_q,q} = 0. Поскольку задача симметрична по q, то j_q выбираются произвольно, лишь бы j_1, j_2 и j_3 были различны.
Система:
(1) x_{1,q} + x_{2,q} + x_{3,q} + x_{4, q} <= 450
(2) x_{j,q} >= b_{j,q} для j <> j_q (или просто b_{j_q,q} := 0)
(3) 5 <= x_{4, q} <= 8
q = 1, 2, 3
Условие оптимальности:
sum_{ j, q} C_j * x_{j,q} -> min
Итак, требуется найти минимум линейной функции на многограннике M в R^{9}.
Можно перебрать вершины M.
 

3deus

Поскольку задача симметрична по q, то j_q выбираются произвольно, лишь бы j_1, j_2 и j_3 были различны.
Еще уточнение, в условии задачи не сказано, но видно предполагается (в силу "особости" сырья j = 4 что {j_1, j_2, j_3} = {1, 2, 3}, след-но, можно считать j_q = q .

3deus

Можно перебрать вершины M.
Чтобы найти вершины M полезно заметить, что M = M_1 x M_2 x M_3, где многогранники M_1, M_2 и M_3 одного и того же типа N = N (b_1, b_2) в 3-мерном пространстве вида:
N = {(x_1, x_2, x_3): x_1 + x_2 + x_3 <= 450,
     5<= x_3 <=8, x_1 >= b_1, x_2 >= b_2}.
Поэтому вершины N, а значит и вершины M, выписываются в явном виде.
Так как N - компакт, то M - компакт, и имеет видимо не более 6 ^ 3 = 216 вершин.
 

Abdim59

Всем откликнувшимся спасибо. Условие действительно "непонятное". По результатам переговоров с преподом оно уточнилось в виде системы:

Все a, b и С мы задаем руками.
Кто-нибудь может помочь с этим вопросом?

3deus

Тут все понятно. Ищите вершины многогранника, заданного неравенствами, заменяя неравенства на равенства и решая системы линейных уравнений. Получаете конечное множество точек и подставляете их в линейную функцию в поисках наименьшего её значения.
Точка в которой это значение достигается - оптимальная.
P.S. Мотающийся череп на вашей картинке мешает думать. :grin:

a101

Что за индекс p в третьей строчке? Идет суммирование по предприятиям? Они больше нигде не встречаются? Если да, то на всех предприятиях мы должны производить одно и тоже или на каждом предприятие свое? И откуда условие, что предприятий ровно 3 взялось. Может нужно задачу решить отдельно для каждого предприятия (так будет попроще :) )?
PS
Не знал, что можно легко пообщаться с преподом в 2 часа ночи :o

Abdim59

прошу прощения, возможно я уже спрашиваю чушь... Но для каждого случая (для заданный a,b,C) все неравенства одновременно надо заменить на равенства, так? После этого решить систему уравнений. И у нее будет несколько решений которые и будут вершинами многогранника, заданного этими уравнениями?

a101

Не совсем. У тебя не будут в этой задаче все неравенства равенствами. Учитывая, что размерность у тебя 12 (4 * 3) то оптимальное решение задается какими-то 12 равенствами. Вот только их искать задолбает.
Можно, конечно, руками реализовать симплекс метод, но такое ощущение, что вначале систему можно упростить.

3deus

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

a101

В общем, если данных много с которыми тебе надо найти решение, воспользуйся какой-нить программой. Их довольно много. Если нужно будет посчитать все руками для одного набора (правда почему бы этот набор не выложить в форум то воспользуйся этим:
http://ru.wikipedia.org/wiki/%D0%A1%D0%B8%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4

Думаю будет примерно понятно как искать твое оптимальное решение. Я бы добавил, что если b_pi относительно невелики и С_i одного порядка, то скорее всего решение будет лежать в точке на грани \sum x_{4i} = 5 и не лежать на гранях из первого уравнения (что сумма ограничена сверху). Условие, когда оптимальная точка лежит в другом месте существует, но это надо извратиться и специально тебе так параметры подобрать.

PS
Хотя если бы ты написал пример входных параметров - тебе бы было более легко помогать.

Abdim59

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

Abdim59

В общем, если данных много с которыми тебе надо найти решение, воспользуйся какой-нить программой.
Дык в общем-то и надо написать прогу, которая принимает входные данные, и выдает оптимальное решение.
Примера входных данный не дадено природой :(

a101



Дык в общем-то и надо написать прогу
Хм... Может с этого и надо было начинать первый пост? Просто об этом никаких слов. Можно еще уточнить на чем требуется написать.

Попробуй сделать то, что написано по моей ссылке. Если сам хочешь писать прогу.

Abdim59

Сорри, я посчитал это очевидным :( Потому как не представлял себе, зачем человеку может понадобиться перебрать столько значений руками (то есть это уже не учебная задача получается, а изврат на мой взгляд. Чтобы освоить симплекс-метод руками, дают задачи намного меньшей размерности).
По делу. Писать на чем - не важно (надеюсь на асме никому не придет в голову это сделать, и на 1С тоже - две крайности на мой взгляд). Предпочтение, конечно, С и Делфи.
Вот насчет написать сам - очень неуверен, что справлюсь - давно дебугер не включал уже :) Если кто сможет помочь - you are welcome :)

a101

Мне писать лень. :( Я больше пофлудить люблю.

Вообще можно взять реализованный симплекс метод на любом языке (google довольно бодро выдает ссылки) и написать обертку, которая передает туда уже нужную систему линейных уравнений (полученную из нашей подставновкой параметров).

3deus

О, я кажется придумал.
Неравенства (1) и (2) задают конкретный многогранник N, у него легко в явном виде найти все одномерные "ребра", т.е. отрезки и лучи в пространстве R ^ {12}. Поэтому вершины искомого многранника М можно вычислить как точки пересечения этих лучей и отрезков с "переменной" гиперплоскостью, заданной в 3-ей строке ! :)
Теперь нужно придумать удобный способ задания этих "константных" лучей и отрезков в программе.

Abdim59

Ну да, на уровне "в теории" и "пофлудил" это действительно выглядит просто :)
Но я что-то на такой подвиг сейчас не способен - и время потрачу, и не напишу ничего :(
В любом случае спасибо!
ЗЫ Есть тут прогеры, которые хотят пива или мож чего другого?

Abdim59

прикольно :)
сенкс :)
долго втыкал - видимо время суток сказывается... :)

3deus

у него легко в явном виде найти все одномерные "ребра", т.е. отрезки и лучи в пространстве R ^ {12}.
Так как N можно представить в виде декартова произведения : N = N_1 x N_2 x N_3 x N_0, причем трехмерные многогранники N_1, N_2 и N_3 одного и того же типа. А Ребро (луч или отрезок) N получается как ребро 3-мерного множителя N_0, ... или N_3, дек. умноженное на вершины отстальных многогранников-множителей.

Abdim59

Так как N можно представить в виде декартова произведения : N = N_1 x N_2 x N_3 x N_0, причем трехмерные многогранники N_1, N_2 и N_3 одного и того же типа. А Ребро (луч или отрезок) N получается как ребро 3-мерного множителя N_0, ... или N_3, дек. умноженное на вершины отстальных многогранников-множителей.
Вот только что я прочитал "бла-бла-бла".... :(
Нельзя ли чуть разжевать?

3deus

Ой, все намного проще ! Никаких лучей нет. N_0, ... , N_3 - компакты, так как иксы неотрицательны. А задать ребра-отрезки N естественно как пары точек - удобно искать пересечение отрезка-ребра с нашей "переменной" гиперплоскостью в R^{12}.

Abdim59

Сорри, у меня с пространственным многомерным мышлением напряженка, поэтому уточню.
Правильно ли я понимаю, что ты предлагаешь разбить N^12 в прямую сумму 4-х подпространств по соответствующим тройкам кординат из первых четырех уравнений системы (первые 2-е строчки). Из этих же уравнений при добавлении условий неотрицательности в явном виде получаются 4 компакта, координаты их вершин из уравнений вычисляются, так?
После этого мы (зная все коэффициенты, которые задаются руками) ставим равенство в 3-м уравнении, получаем гиперплоскость в N^12. И так у нас получается, что все вершины нашего многоганника есть подмножество следующего множества: координаты вершин компактов и координаты пересечения ребер с гиперплоскостью? (вот в этом моменте я как-то больше всего для себя сомневаюсь...)
Дальше надо просто в этих точках посчитать линейную функцию (следя за выполнением неравенства из ур-я 3) и выбрать экстремальную точку?
Так?

Abdim59

Так, уже сам вижу, что лажу написал.
С поиском ребер засада неправильная....
Насколько я понимаю, у нас получится 4 компакта из 4-х неравенств и ребрами будут прямые произведения опять же... Блин, немного не догоняю. Можно чуть расжевать вот этот момент?

Abdim59

UP
Люди, подскажите хоть, как взять прямую сумму этих четырех компактов, плз... То есть я найду в каждом из подпространств координаты вершин этих многогранников, а как потом найти координаты вершин их прямой суммы?

stm7543347

с четвёртого курса мм
Нам линпрог в девятом классе рассказывали...

3deus

координаты вершин компактов и координаты пересечения ребер с гиперплоскостью? (вот в этом моменте я как-то больше всего для себя сомневаюсь...)
Подсказка.
 Лемма. Пусть в n-мерном евклидовом пространстве имеется n-мерный многогранник М и гиперплоскость Н, ограничивающая полупространство Р. Тогда вершина х многогранника N = (M пересечь с P которая лежит на Н, является пересечением H и ребра мног-ка М.
Доказательство леммы индукцией по n.
Шаг индукции n -> n-1. Наша вершина х лежит на гиперграни Г, содержащейся в гиперплоскости Т. Поэтому по лемме для гиперплоскости Н' = (Н пересечь с Т) и n-1-мерного многогранника Г, лежащего в пр-ве Т, находим искомое ребро мног-ка Г, которое также является ребром M.
Всё.
Таким образом, вершина М - это или вершина N или пересечение "переменной" гиперплоскости с ребром мног-ка N.
Оставить комментарий
Имя или ник:
Комментарий: