21. Переход к новому опорному решению тз.

Итерации: После нахождения опорного плана перевозок, нужно применить

один из алгоритмов его улучшения, приближения к оптимальному.

2 2.. Циклы строятся только по заполненным клеткам. Точки самопересечения не явл-ся вершинами цикла.

Допустимое решение транспортной задачи Х=( ), i=1,2,,…,m, j=1,2,…,n является опорным тогда и только тогда, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

23. Метод потенциалов. Теорема. Если план х* явл-ся опт-м, то ему соответствует система (m+n) чисел, Ui* и Vj*,которые удовлетворяют условиям:

Ui*+Vj*=Сij (xij>0), Ui* + Vj*>Cij (xij=0). Док-во: числа Ui* и Vj* - потенцилы поставщиков и потребителей, соответственно. По условиям (1,2,3) ИЗ к ней можно поставить двойную задачу:

У словия новой задачи дают систему ограничений. Получим двойственную задачу, имеющую решение, если решается исходная задача. Ограничений неотриц-ти

на переменные Ui b Vj нет, и в силу 1й теоремы двойств-ти, пара ДЗ одновременно разрешима или нет.

Сумма потенциалов равна тарифу клетки Cij.

Для каждой заполненной клетки находим потенциалы из условия ui*+vj*=Cij (xij>0). Для незаполненных клеток находим оценки:

Sij=(ui+vj) – Cij. Sij<=0. Если сущ-т хотя бы одна оценка Sij>0, то полученное решение не является оптимальным. Среди полученных положительных оценок Sij выбираем наибольшую,для указанной клетки строится цикл. Затем строится новый цикл, в котором

в клетки с + и – добавляется λ, потенциал перемещается по циклу.

Вновь полученный план проверяем на оптимальность

24. Оценка свободной клетки. Для незаполненных клеток находим оценки:

S ij=(ui+vj) – Cij. Sij<=0

25. Критерий оптимальности. Переход к оценочной матрице. Sij=(ui+vj) – Cij. Sij<=0. Если сущ-т хотя бы одна оценка Sij>0, то полученное решение не является оптимальным. Составляется оценочная матрица С размерностью mxn, которая заполняется соответственно клеткам ТЗ полученными оценками (на месте заполненных клеток ставится 0). Если найдется хотя бы одна оценка Sij>0, план не является оптимальным. Среди полученных положительных оценок Sij выбираем наибольшую, для указанной клетки строится цикл. Опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.

26. Открытая модель тз. Сведение ее к закрытой модели.

Модель ТЗ называется моделью закрытого типа, если выполняется рав-во условие 1.

Модель ТЗ – закрытого типа, если выполняется одно из условий 2 или 3.

В о втором случае:

Bn+1=Σai – Σbj – эффект. Потребителя;

В третьем случае:

Am+1= Σbj – Σai – эф. Поставщика

При введении фиктивного поставщика/потребителя, соответствующие тарифы полагаем равными 0.

27. Постановка задачи целочисленного программирования.

Существует ряд задач оптимального планирования, в которых переменные могут принимать лишь целочисленные значения. Такие задачи связаны с определением количества единиц неделимой продукции, числа станков при загрузке оборудования, численности работников в структурных подразделениях предприятия и т.д. Если функция и ограничения в таких задачах линейны, то мы говорим о задаче линейного целочисленного программирования.

Задача линейного целочисленного программирования формулируется следующим образом: Найти такой план

X = (X₁, X₂, ..., X_n),

при котором линейная функция

принимает максимальное или минимальное значение при ограничениях

, i = 1, 2, ..., m

, j = 1, 2, ... n

 - целые числа .

AX≤B

X≥0

Z=CX

X – целое

28. Метод Гомори. 1. Решаем поставленную задачу одним из методов. Находим опт-решение. Если координаты полученного решения целочисленны – задача решена.

Если координаты нецелочисленны, строят правильное отсечение: a=[a]+{a};

0≤{a}≤1, # [-1,3]=2 {-1,3} = 0,7.

2. Пусть после некот-й итерации получено след-ее ограничение:

д ля того, чтобы xi принимало целочисленные значения, необходимо, чтобы выпол-сь усл-е 2.

Если на некотором шаге имеем несколько нецелых значений bi, то целесообразно выбирать строку с наиб. дробной частью.