Построение исходного опорного плана
А) правило северо-западного угла.
Начинаем заполнение с левой-верхней клетки, записываем в неё мах возможное кол-во поставки. Если запасы первого поставщика полностью израсходованы переходим ко 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-й работы. Необходимо определить, кого и на какую работу следует назначить, чтобы добиться максимальной суммарной производительности при условии, что каждое лицо может быть назначено только на одну работу.
Для составления математической модели обозначим через xij назначение i-го лица на j-ю работу. Тогда, так как количество лиц равно количеству работ и каждое из них может быть назначено только на одну работу, Xij принимает только два значения: единица, если i-e лицо назначается для выполнения j-й работы; нуль, если i-е лицо не назначается для выполнения j-й работы.∑(по м i=1)=1,∑(по м j=1) =1
При назначении i-го лица на j-ю работу производительность равна Cij xij. суммарная производительность Z=.∑(по м i=1)∑(по м j=1) Cij xij.
Таким образом, приходим к следующей задаче линейного программирования.
Найти максимальное значение линейной функции Z=.∑(по м i=1)∑(по м j=1) Cij xij. при ограничениях
Умножая линейную функцию на — 1, приводим задачу к транспортной, в которой объем запасов каждого поставщика и объем потребностей каждого потребителя равны единице.
Сущность метода дискретной оптимизации.
Постановка задачи программирования формулируется так же, как
и задача линейного программирования, но включается дополнительное требование, состоящее в том, что значения переменных, составляющих оптимальное решение, должны быть целыми неотрицательными числами. Найти минимальное значение линейной функции Z==.∑(по n j=1) Cj xj при ограничениях 
Предположим, что задача линейного программирования имеет многогранник решений, приведенный на рис. 
Если наложить требование целочисленности, то допустимое множество решений выродится в систему точек и уже не яв ляется выпуклым. Если добавить новые ограничения, связывающие внешние целочисленные точки, а затем в качестве многогранника решений использовать все выпуклое множество, ограниченное осями координат и новым контуром
то получим новую задачу линейного про граммирования со следующими свойствами:
1) новый многогранник решений содержит все целые точки, заключавшиеся в первоначальном многограннике решений; любая его угловая точка является целой;2) так как линейная функция достигает оптимума в угловой точке многогранника решений, то построением такого многогранника и обеспечивается целочисленность оптимального решения.
Метод Гомори.
метод решения поставленной задачи(см выше), предложенный Гоморй, основан на симплексном методе и состоит в следующем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту хг, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до получения нового оптимального плана. Если и он является нецелочисленным, то составляют следующее ограничение, 
Преобразуя это неравенство в уравнение, вычитая из его левой части целую неотрицательную дополнительную переменную хn+1, умножим уравнение на —1, добавим к последней симплексной таблице и, применяя двойственный симплексный метод, находим новый план. Если он не является целочисленным, то по последней симплексной таблице составляем новое дополнительное ограничение.
Если в оптимальном плане несколько дробных xi, то дополнительное ограничение составляют для max qi. Это ускоряет процесс получения оптимального целочисленного решения.
