Задачи о назначениях и о коммивояжере как частные случаи целочисленных ЗЛП

При решении многих задач нецелочисленное решение не имеет смысла. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования - целочисленное программирование.

В экономике много задач с физической неделимостью объектов, предметов и факторов расчета. К примеру, нельзя построить 1,7 здания, 6,1 завода, 1,07 автомобиля, произвести 1,7 замера, осуществить 3,4 путешествия, купить 4,5 туристических путевок.

Задача о назначении: имеет n исполнителей, которые могут выполнять n различных работ. Известна полезность , связанная с выполнением i-м исполнителем j-й работы , . Необходимо назначить исполнителей на работы так, чтобы добиться максимальной полезности, при условии, что каждый исполнитель может быть назначен только на одну работу и за каждой работой должнен быть закреплен только один исполнитель.

Математическая модель задачи примет вид:

(42.1)

Каждый исполнитель назначается только на одну работу:

(42.2)

На каждую работу назначается только один исполнитель:

(42.3)

Условия неотрицательности и целочисленности:

, , , . (42.4)

Задача коммивояжера: коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

Математическая модель задачи:

(42.5)

(42.6)

(42.7)

Условия неотрицательности и целочисленности

, , , . (42.8)

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

Определение: экстремальная задача линейного программирования, в которой на решение налагается целочисленность компонент, является задачей целочисленного программирования и называется целочисленной задачей.

Определение: экстремальная задача линейного программирования, в которой на решение налагается целочисленность нескольких компонент, является задачей целочисленного программирования и называется частично целочисленной задачей.