Сущность метода дискретной оптимизации.

Построение исходного опорного плана

А) правило северо-западного угла.

Начинаем заполнение с левой-верхней клетки , записываем в неё мах возможное кол-во поставки. Если запасы первого поставщика полностью израсходованы переходим ко 2-му с запасом груза А, если потребитель1 остался неудовлетворённым на Х единиц , сравниваем этот остаток Х с запасами2-го поставщика и записываем в первую клетку второй строки. У поставщика 2 осталось А-Х груза и заполняем клетки второй строки пока груз второго поставщика пока все его запасы не будут полностью израсходованы. Спускаемся на строку ниже и продолжаем заполнение опорного плана пока не будут удовлетворены все потребители.

Б) Метод мин. Элемента.

Выбирается наименьший тариф и в первую очередь заполняется именно эта клетка, при этом в клетку записывается мах возможное кол-во поставки. За тем рассматривается следующая по тарифу значение и поступается аналогично.

В)Метод Фогеля.

1.Находим разницу между 2-мя минимальными тарифами по строкам и по столбцам.2. Выбираем наибольшую разницу и работаем с этой строчкой(столбцом)3.В этой строчке(столбце) находим клетку с мин. Тарифом и записываем в неё мах возможное кол-во поставки.4. заново проделываем операции 1-3.

Исследование построенного плана на оптимальность.

1. Находим значения потенциалов поставщиков и потребителей Ui+Vj=Cij

2. Вычисляем оценки свободных клеток по формуле Sij=Cij-(Uij+Vij). Если все оценки свободных клеток >0 то построенный план-оптимальный. Если они >=0 то план оптимальный, но не единственный .

25. Транспортная задача по критерию времени. Нахождение мин. Возможное время перевозки. Решается методом запрещённых клеток.1. ”закрываем” несколько клеток с мах временем и начинаем заполнять методом мин. Элемента, если невозможно обойтись без закрытых клеток , открываем их .2.Далее строим цикл для уменьшения мин. Времени, начинаем с заполненной клетки с наибольшем временем, которую хотим освободить, т.е. с ''-'' строим цикл,так же как и в обычной транспортной задаче, но здесь поворачивать на90 градусов мы можем и в пустых клетках при условии, что будем их заполнять, т.е. со знаком '''+'' .3. строим циклы по уменьшению времени до тех пор пока это будет возможно. Мин . возможным временем перевозки будет являться самое большое время стоящее в заполненной грузом клетке.

Задача о контейнерных перевозках.

Задача о назначении.

Пусть имеются m лиц Аi(i=1,2,...m) которые могут выполнять Вj(j=1,2...m) различных работ работ. Известна произ­водительность (Сij)'-го лица при выполнении j-й работы. Необходимо определить, кого и на какую работу следует назначить, чтобы добиться максимальной суммарной про­изводительности при условии, что каждое лицо может быть назначено только на одну работу.

Для составления математической модели обозначим через x_ij назначение i-го лица на j-ю работу. Тогда, так как количество лиц равно количеству работ и каждое из них может быть назначено только на одну работу, Xij при­нимает только два значения: единица, если i-e лицо назна­чается для выполнения j-й работы; нуль, если i-е лицо не назначается для выполнения j-й работы.(по м i=1)=1 ,( по м j=1) =1

При назначении i-го лица на j-ю работу производительность равна Cij x_ij. суммарная производительность Z=.(по м i=1)( по м j=1) Cij x_ij.

Таким образом, приходим к следующей задаче линейно­го программирования.

Найти максимальное значение линейной функции Z=.(по м i=1)( по м j=1) Cij x_ij. при ограничениях

Умножая линейную функцию на — 1, приводим задачу к транспортной, в которой объем запасов каждого поставщи­ка и объем потребностей каждого потребителя равны еди­нице.

Сущность метода дискретной оптимизации.

Постановка задачи программирования формулируется так же, как

и задача линейного программирования, но включается до­полнительное требование, состоящее в том, что значения переменных, составляющих оптимальное решение, долж­ны быть целыми неотрицательными числами. Найти минимальное значение линейной функции Z==.(по n j=1) Cj x_j при ограничениях Предположим, что задача линейного программирования имеет многогранник решений, приведенный на рис. Если наложить требование целочисленности, то допустимое множество решений выродится в систему точек и уже не яв ляется выпуклым. Если добавить новые ограниче­ния, связывающие внешние целочисленные точки, а за­тем в качестве многогран­ника решений использовать все выпуклое множество, ограниченное осями коор­динат и новым контуром

то получим но­вую задачу линейного про граммирования со следую­щими свойствами:

1) новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка является целой;2) так как линейная функция достигает оптимума в угловой точке многогранника решений, то построением такого многогранника и обеспечивается целочисленность оптимального решения.

Метод Гомори.

метод решения поставленной задачи(см выше), предложенный Гоморй, основан на симплексном методе и состоит в следую­щем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности. Если оптималь­ный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту х_г, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычис­ления симплексным методом продолжают до получения но­вого оптимального плана. Если и он является нецелочис­ленным, то составляют следующее ограничение, Преобразуя это неравенство в уравнение, вычитая из его левой части целую неотрицательную дополнительную переменную х_n+1, умножим уравнение на —1, добавим к последней симплексной таблице и, применяя двойственный симплексный метод, находим новый план. Если он не яв­ляется целочисленным, то по последней симплексной таб­лице составляем новое дополнительное ограничение.

Если в оптимальном плане несколько дробных x_i, то до­полнительное ограничение составляют для max q_i. Это уско­ряет процесс получения оптимального целочисленного ре­шения.