задача линейного программирования с минимальными затратами

У строительной компании 6 проектов, на каждый нужно $d_i$ рабочих. В начале проекта 1 у компании нет рабочих.

Каждый новый рабочий должен пройти курс безопасности, который стоит 300, и на 50 больше для каждого рабочего. Если нет нового рабочего, то и курса нет.

Увольнение рабочего не стоит денег, и его нельзя нанять повторно.

Учитывая, что зарплата рабочего составляет 100 за проект, сформулируйте задачу линейного программирования, которая минимизирует затраты на рабочих.

Что я пробовал:

Пусть $x_i$ будет количеством новых рабочих для проекта $i$.

Пусть $y_i$ будет количеством старых рабочих, оставшихся от предыдущих проектов до проекта $i$ (все нанятые рабочие - все рабочие, которые были уволены).

Пусть $z_i$ будет таким индикатором, что $z_i =0 \iff x_i>0$

Я пытаюсь решить следующую функцию:

$\min(\sum_{i=1}^6 150x_i + 300(1-z_i) + 100y_i)$

s.t:

\begin{align}
x_i,y_i,z_i &\ge 0 \\
z_i &\ge 1-x_i \\
y_i + x_i &\ge d_i \\
y_i &\ge y_{i-1} + x_i
\end{align}

Что-то мне не нравится. Основная причина в том, что я пытался использовать Matlab для решения этой проблемы, но это не удалось.

Что я сделал не так? Как я могу решить этот вопрос?


linear-programming integer-programming operations-research
person Roi Hezkiyahu    schedule 30.10.2020    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Когда я вижу это правильно, у вас есть две небольшие ошибки в ваших ограничениях.

Первый появляется, когда вы используете z_i >= 1-x_i. Это позволяет z_i постоянно принимать значение 1, что никогда не даст вам дополнительных затрат в размере 300. Вам нужно установить верхнюю границу z_i так, чтобы z_i не было 1, когда у вас x_i>0. Для этого ограничения вам понадобится что-то под названием big M. Для достаточно большого M вы должны использовать z_i <= 1-x_i/M. Таким образом, когда x_i=0 вы можете иметь z_i=1, в противном случае правая часть меньше 1 и из-за целостности z_i должна быть равна нулю. Обратите внимание, что вы обычно хотите выбирать M как можно более плотно. Так что в вашем случае d_i может быть хорошим выбором.

Вторая маленькая ошибка лежит в y_i >= y_{i-1} + x_i. Таким образом, вы можете увеличить y_i до y_{i-1} без необходимости устанавливать x_i. Чтобы заставить x_i увеличиться, вам нужно перевернуть неравенство. Кроме того, согласно тому, как вы определили y_i, это неравенство должно относиться к x_{i-1}. Таким образом, вы должны получить y_i <= y_{i-1} + x_{i-1}. Кроме того, вам нужно позаботиться о угловых случаях (например, y_1 = 0)

Я думаю, что с этими двумя изменениями все должно работать. Сообщите мне, помогло ли это вам. А если все равно не получается, возможно, я что-то упустил.

person SimonT    schedule 02.11.2020