Связь между решениями прямой и двойсвт.задач при реш.прям.задачи симплекс методом

Пусть х=(х1,х2,..,хn)-некот.планисх задачи 1-3,а векторн.у=(у1,у2,..,уn)план двой-й задачи4-5тогда знач-е усл.фу-и исх.задачи.При плане х всегда не превосходит зн-й усл.фу-идв.задачи при плане у. f(y)=F(x)

Если зна-я усл.фу-й 1и4 равны для нек.плановF(x^*)=f(y^*)тогда х*явл.оптим.планомисх.задачи а у*двойств.

 

11. первая и вторая теорема двойственности.примеры применения теоремдвойст-и.

1 теор.двойст-и.Если одна из пары дво-й задачи 1-3 или 4-5имеет оптимплан,то и др.тоже имеет оптим план и зн-я усл.фу-й для этих оптим.планов равны между собой Fmax=Fmin.F(x*)=f(x*)

Если усл.ф-ии одной из пары дв.задачи не огранич.дляисх.задачи сверху для ов.снизу,тодр.задача вообще не им.планов.

 

2.вторая теор.двойстве-и.план х*=(х1*,х2*,..,хn*)задачу 1-3,и план дв.задачиy*=(y1*,y2*,..,ym*)явл.оптим-м для своих задач тогда и только тогда,когда для люб.индексаjвып-ся равенство: Vj(j=1n).

F=2x1+7x2->max

 

12.Транспортная задача.сост.трансп.таблицы.плантранспортн.задачи.закр.(сбалансир-я) и открытая(несбалан-я)

1)всякое неотриц-е рещениесист-ы огранич-я(2)опред-я матрица х наз-я транспортной задачей.

• Транспортная задача называется закрытой, если a = b. Если же

a ≠ b, то транспортная задача называется открытой.

Х*=(хij*)при кот.целевая фу-ях1 приним.своёминим.знач-е наз-я оптимальным планом ТЗ.

Если общая потреб.в грузе в пунктах наз-я равна запаса груза в пунктах отпр-я то такая тзназ-я закрытой или сбалансир-й

13. Сост.опорного плана транспортной задачи

Методом северо-зап-ого угла и методом

Миним-о элемента.

методом северо-зап-ого угла

На каждом этапе максимально возможным

числом заполняют левую верхнюю клетку

оставшейся части таблицы. Заполнение таким

образом, что полностью выносится груз из

или полностью удовлетворяется потребность.

1) Полагают верхний левый элемент матрицы X

x 11 = min(a 1,b1)

Возможны три случая:

а)если a1 < b1, то х11=а1 и всю первую строку начиная со второго элемента заполняют нулями.

б)если a1 > b1, то Х11=b1, а все оставшиеся элементы первого столбца заполняют нулями.

в)если a1 = b1, то х11 = a 1 = b 1, и все оставшиеся элементы первых столбца и строки заполняют нулями.

На этом один шаг метода заканчивается.

2) Пусть уже проделано к шагов, кm-й шаг состоит в следующем.

Определяют верхний левый элемент незаполненной части матрицы X. Пусть это элемент хl, m.

Тогда полагают хl,m = min(аkl, bkm),

где аkl = al - Σxlj

bkm = bm - Σxim

Если аkl<bkm, то заполняют нулями l -ю строку начиная с (m + 1)-го элемента. В противном случае заполняют нулями оставшуюся часть m-го столбца.

Метод минимального элемента позволяет построить

начальный опорный план транспортной задачи и является

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

специфику матрицы С=(cij)m,n. В отличие от метода

северо-западного угла данный метод позволяет сразу

получить достаточно экономичный план и сокращает

общее количество итераций по его оптимизации.

Схема метода: элементы матрицы С нумеруют начиная

от минимального в порядке возрастания, а затем в этом

же порядке заполняют матрицу Х0.

Пусть элементом с минимальным порядковым номером

оказался элемент x0ij.

Тогда полагают x 0 ij = min (ai, bj)

Возможны три случая:

а) если min (ai, bj) = ai, то оставшуюся часть i-й строки

заполняют нулями; (a1, b1) = bj, то

оставшуюся часть j-ro столбца заполняют

нулями.

б) если min (a1, b1) = bj, то оставшуюся часть j-ro столбца заполняют нулями.

в) если ai = bj, то оставшуюся часть строки и столбца

заполняют нулями.

Далее этот процесс повторяют с незаполненной частью

матрицы.

Пусть элементом с k -м порядковым номером оказался

ХklmТогда хklm = min(akl, bkm),

гдеа k l = al - Σxglj, g = 1..l-1

bkm = bm - Σxuim, u = 1..k-1

Возможны три случая:

а) аkl<bkm, тогда хklm = аkl и оставшуюся часть строки l заполняют нулями;

б) аkl>bkm, тогда хklm = bkm и остаток столбца m заполняют нулями;

в) аk = bkm, тогда оставшуюся часть строки l и столбца m заполняют

нулями.