Лекция: Задачи о назначениях и о коммивояжере как частные случаи целочисленных ЗЛП.
При решении многих задач нецелочисленное решение не имеет смысла. Раздел математического программирования, в котором на экстремальные задачи налагается условие дискретности переменных при конечной области допустимых решений, называется дискретным программированием. При наличии условия целочисленности имеется в виду подраздел дискретного программирования — целочисленное программирование.
В экономике много задач с физической неделимостью объектов, предметов и факторов расчета. К примеру, нельзя построить 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)
Добавляется условие прохождение маршрута через все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках.
Определение: экстремальная задача линейного программирования, в которой на решение налагается целочисленность компонент, является задачей целочисленного программирования и называется целочисленной задачей.
Определение: экстремальная задача линейного программирования, в которой на решение налагается целочисленность нескольких компонент, является задачей целочисленного программирования и называется частично целочисленной задачей.