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

[marie-la]

Есть 4 завода, каждый может производить один из 3 видов машин. Даны стоимости, минимальные количества машин каждого вида. Нужно минимизировать стоимость производства. Поставить задачу целочисленного программирования, если каждый завод может производить только один вид машин. У меня что-то линейное условие производства всех машин не выходит. То есть пусть $x_{11},x_{12},x_{13}$ - количества машин первого, второго, третьего видов, производимые первым заводом. Тогда как потребовать, чтоб только одно из этих чисел было ненулевым?

[пианист]

Не совсем понял условие, но я бы искал переменные - признак отнесения продукции к заводу, binary.
Требуем равенство единице соответствующей суммы.

[marie-la]

пианист в сообщении #1559326 писал(а):

Не совсем понял условие, но я бы искал переменные - признак отнесения продукции к заводу, binary.
Тогда условие - равенство единице суммы.

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

[waxtep]

Если каждый из заводов может обеспечить минимальную потребность в любом из видов машин, то, кажется, нет необходимости ставить ЗЛП. Достаточно выбрать минимальную стоимость из $24$ сценариев вида "завод #2 простаивает, завод #1 делает машины вида #3..." и т.п. Желательна более детальная постановка, если там все не так просто.

[пианист]

marie-la
В Ваших обозначениях $x$ не является переменной (правда, формулу совсем не понял). Задана она или нет, это уже какое условие задачи, смотря по тому, присоединяюсь к уважаемому waxtep

[marie-la]

Пусть задана матрица затрат на продукцию $P$ размерности $4\times 3$. Каждый завод может производить не более чем один вид продукции. Производство каждого вида машин должно быть не меньше $C$. При этих условиях нужно поставить задачу линейного целочисленного программирования (в задании сказано Pure Integer Linear Programming, PILP) для минимизации стоимости производства. Я ввела бинарные переменные $y_{ij},i=1,...,4,j=1,...,3$ - индикаторы производства заводом продукции, и неотрицательные целочисленные переменные $x_{ij},i=1,...,4,j=1,...,3$ - размеры производства. Тогда получаем
$\sum_{i,j} P_{ij}x_{ij}\rightarrow \min$
$\sum_{i}x_{ij}\geq C, j=1,2,3$
$\sum_{j} y_{ij}\leq 1, i=1,2,3,4$
$x_{ij}y_{ij}=x_{ij}, i=1,...,4,j=1,...,3$
Последнее условие нужно, чтоб индикаторы производства были единичными для тех же видов машин, где ненулевые размеры производства. Вот оно меня и смущает - это условие нелинейное, а как линейным сделать, непонятно. Решать задачу мне не нужно, а только сформулировать ЗЛП.

-- 05.07.2022, 09:04 --

пианист в сообщении #1559356 писал(а):

marie-la
В Ваших обозначениях $x$ не является переменной (правда, формулу совсем не понял). Задана она или нет, это уже какое условие задачи, смотря по тому, присоединяюсь к уважаемому waxtep

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

[B@R5uk]

marie-la, я так понял, иксы у вас являются константами, указывающими производительность производства каждого завода, а игреки — искомые индикаторные переменные, принимающие значения из множества ноль-один. Вот возьмём ваше самое первое соотношение, которое нужно якобы минимизировать. Почему в него не входят искомые переменные? По какой величине его минимизировать, если оно равно константе (так как все величины в нём константы)?

[пианист]

Странная какая-то задача :о
Раз изделий три, завода четыре, на одном заводе можно делать одно изделие, и для каждого изделия минимальный выпуск, какое-то из изделий будет производиться на двух заводах - выбираем самый дешевый вариант, и все переносим туда. Т.е. из четырех работают три завода, производство получается просто домножением игрека на $C$, икс не нужен, но на игрек еще одно условие.
Как-то так.

[B@R5uk]

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

[marie-la]

пианист в сообщении #1559375 писал(а):

Странная какая-то задача :о
Раз изделий три, завода четыре, на одном заводе можно делать одно изделие, и для каждого изделия минимальный выпуск, какое-то из изделий будет производиться на двух заводах - выбираем самый дешевый вариант, и все переносим туда. Т.е. из четырех работают три завода, производство получается просто домножением игрека на $C$, икс не нужен, но на игрек еще одно условие.
Как-то так.

Да, вроде так и есть, спасибо!

-- 05.07.2022, 13:24 --

B@R5uk в сообщении #1559396 писал(а):

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

Нет условия на максимальное производство завода, так что все правильно

[B@R5uk]

marie-la в сообщении #1559397 писал(а):

так что все правильно

Вам виднее. Вы же не привели полную дословную формулировку задачи.