Газодобывающему предприятию требуется отремонтировать 15 газовых скважин. В наличии имеется 5 ремонтных бригад. Первая

Газодобывающему предприятию требуется отремонтировать 15 газовых скважин. В наличии имеется 5 ремонтных бригад. Первая бригада может отремонтировать 5 скважин, вторая и третья по 4, четвертая 3, пятая 2. Затраты в денежных единицах на ремонт каждой бригадой (строка) каждой скважины (столбец) определяются следующей таблицей: Назначить так бригады на скважины, чтобы суммарные затраты были минимальные.

В данном случае мы имеем задачу о назначениях, которая, как известно, в определенном смысле является разновидностью классической транспортной задачи.
Имеются 15 газовых скважин, подлежащих ремонту. Имеются также 5 ремонтных бригад, которые могут отремонтировать 5 + 4 + 4 + 3 + 2 = 18 скважин (здесь слагаемые ki, i = 1,…,5 соответствуют возможностям каждой из пяти бригад по количеству ремонтируемых скважин).
Известны также cij – затраты на ремонт при назначении i-й бригады на j-ю скважину. Эти данные приведены в таблице.
Необходимо распределить ремонтные бригады по скважинам так, чтобы ремонтировались все скважины, каждая скважина ремонтировалась только одной бригадой, каждой бригаде было назначено для ремонта то количество скважин, которое не превышает её возможности, а суммарные затраты на ремонт всех скважин были бы минимальными.
В данной задаче переменные имеют бинарный характер, то есть могут принимать только значения 0 или 1 (xij = 1 – бригада номер i назначена для ремонта скважины номер j; xij = 0 – бригада номер i не назначена для ремонта скважины номер j)

.
Целевой функцией являются суммарные затраты на ремонт, вычисляемые как сумма произведений затрат на ремонт конкретной скважины конкретной бригадаой на план назначений бригад на скважины.
В общем случае экономико-математическая модель задачи о назначениях формулируется так: найти совокупность значений переменных xij = 0,1, минимизирующих целевую функцию L(X) = i=15j=115cij·xij  min при ограничениях по назначениям ремонтных бригад j=115xij ≤ ki, i = 1,…,5, а также при ограничениях по назначениям на скважины i=15xij = 1, j = 1,…,15