Линейная и целочисленная оптимизация

Записываем модель

Пусть $x$ - число холодильников, $y$ - число диванов; оба числа целые и неотрицательные.

Оцениваем выручку сверху

Ищем $\alpha$ и $\beta$ из системы $3\alpha + \beta = 5$ и $2\alpha + 2\beta = 4$. Из второго уравнения $\alpha + \beta = 2$, подстановка в первое даёт $2\alpha = 3$, то есть $\alpha = 1{,}5$ и $\beta = 0{,}5$. Оба множителя неотрицательны, значит оценка законна:

Выясняем, когда достигается равенство

Равенство возможно, только если оба неравенства обращаются в равенства: $3x + 2y = 60$ и $x + 2y = 40$. Вычитая второе из первого, получаем $2x = 20$, откуда $x = 10$ и $y = 15$; оба числа целые и неотрицательные - план допустим.

Проверяем план

Масса: $90 \cdot 10 + 60 \cdot 15 = 900 + 900 = 1800$ кг. Объём: $10 \cdot 1 + 15 \cdot 2 = 40$ м$^3$. Выручка: $50 + 60 = 110$ тыс. рублей.

Интерпретация. Фургон загружается полностью и по массе, и по объёму; никакой другой набор не даёт больше $110$ тысяч рублей за рейс. Для сравнения: «только холодильники» - это $20$ штук по массе и $100$ тыс. рублей, «только диваны» - $20$ штук по объёму и $80$ тыс. рублей.

Ответ: $10$ холодильников и $15$ диванов; наибольшая выручка $110$ тысяч рублей.

Считаем общую массу

Оценка снизу: меньше нельзя

За один рейс перевозится не более $6$ т, поэтому при $n$ рейсах $6n \geqslant 95$, то есть $n \geqslant 15\dfrac{5}{6}$. Число рейсов целое, значит $n \geqslant 16$. Ограничение по числу плит слабее: из $8n \geqslant 100$ следует лишь $n \geqslant 12{,}5$, то есть $n \geqslant 13$. Решает именно масса.

Оценка сверху: столько можно

Сделаем $14$ рейсов, в каждом из которых $2$ тяжёлые и $4$ лёгкие плиты: масса рейса $2 \cdot 2 + 4 \cdot 0{,}5 = 6$ т, число плит $6 \leqslant 8$ - обе нормы выполнены. За эти рейсы перевезены $28$ тяжёлых и $56$ лёгких плит. Оставшиеся $2$ тяжёлые и $14$ лёгких плит увезём двумя рейсами, в каждом $1$ тяжёлая и $7$ лёгких: масса $2 + 3{,}5 = 5{,}5 \leqslant 6$ т, число плит $8 \leqslant 8$ - нормы выполнены. Итого $14 + 2 = 16$ рейсов, и все $30$ тяжёлых и $70$ лёгких плит перевезены.

Интерпретация. Жёстче оказывается ограничение по массе, а не по габаритам. Меньше чем $16$ рейсами обойтись невозможно ни при какой раскладке, и $16$ рейсов реально достижимы - обе половины доказаны.

Ответ: $16$ рейсов.

Записываем модель

Пусть $x$ - число больших контейнеров, $y$ - число малых; оба целые неотрицательные.

Оцениваем сверху

Отдача на тонну: у большого контейнера $\dfrac{7}{4} = 1{,}75$, у малого $\dfrac{5}{3} \approx 1{,}67$. Наибольшая равна $1{,}75$, поэтому при $y \geqslant 0$ верно $5y \leqslant 5{,}25y$ и

Усиливаем оценку целочисленностью

Выручка выражается целым числом тысяч рублей, значит $R \leqslant 87$. Именно этот шаг делает оценку достижимой: план на $87{,}5$ тысячи не существует.

Предъявляем план

При $x = 11$, $y = 2$ масса груза равна $44 + 6 = 50 \leqslant 50$ т, а выручка $77 + 10 = 87$ тыс. рублей. Оценка достигнута. Проверка соседних планов: $x = 12$, $y = 0$ - масса $48$ т, выручка $84$; $x = 10$, $y = 3$ - масса $49$ т, выручка $85$; $x = 8$, $y = 6$ - масса ровно $50$ т, выручка $86$. Все хуже.

Интерпретация. «Жадный» план - грузить только более выгодные большие контейнеры - оставляет $2$ т грузоподъёмности неиспользованными и даёт лишь $84$ тыс. рублей. Замена одного большого контейнера на два малых полностью использует $50$ т и добавляет $3$ тыс. рублей выручки.

Ответ: $87$ тысяч рублей ($11$ больших и $2$ малых контейнера).