Вырождение основной задачи ЛП

⇐ ПредыдущаяСтр 2 из 9Следующая ⇒

Если в опорном решении задачи хотя бы 1 базисная переменная принимает 0-ое значение, то это решение называется вырожденным, а задача ЛП, имеющая хотя бы 1 вырожденное решение – вырожденной задачей. Вырождение наступает в тех случаях, когда при выборе разрещ элемента получается несколько одинаковых минимальных симплексных отношений. В этом случае в след. симплекс таблице в столбце свободных членов появится хотя бы 1 ноль. Вырождение в больших зад-х может привести к зацикливанию, т.е. через некоторое число шагов мы м прийти к опорному решению которое было уже получено раньше. Чтобы избежать зацикливания, разрещ элемент нужно выбирать по опр правилу, а именно: для тех строк разрещ столбца, где получились одинаковые миним симплексные отношения, нужно составить отношения элементов, стоящих в столбце за разрещ столбцом, к элементам разрещ столбца. Наименьшее отношение с учетом знака даст разрещ строку.

М-д искус-го базиса (М-метод)

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

Тmax= Zmax-M∑y_i ; Tmin= Zmin+M∑y_i

Эта задача реш-ся в симп.табл., но для удобства цел. функ. разбивают на 2 строки. В 1-ую записывают оц-ки, кот. не содер-т коэф.М, во 2-ую – оц-ки по кажд. перем-й, содер-щей коэф.М

Расчет эл-ов этих 2-ух строк произ-ся по формуле а₀_j= ∑ С_i*а_ij – C_j, где j=1…n, a_ij – коэф. j-го столбца, С_i- коэф. при бп в урав-ии Z, C_j – коэф. при св.п в урав-и Z, но есть различия. При расчете оц-к М строки коэф С_j во внимание не берется, а М выносится как общий множ-ль. Для того, чтобы Т=Z, нужно, чтобы y_i=0. Поэтому пока у_i не равно 0 разреш-щий столбец выбир-ся по оц-кам во 2-ой строке (исп-ся алгоритм СМ). После того как все у_i=0 дальнейший расчет будет вестись по 1-ой индексной строке. Причем, когда у_i будет выводится из базиса, его выбрасывают из симп. табл, а в след. табл. не будет бывшего разрешающего столбца.

Теорема М-метода

1. Если в оптим. реш-ии М задачи все искус-ые перем-е у_i=0, то это реш-е будет явл-ся оптим. реш-м Z задачи.

2. Если в оптим. реш-ии М задачи хотя бы 1 из искус-х перем-х отлич-ся от нуля, то Z задача не имеет реш-я по причине не совместности с-мы огр-й.

3. Если М задача оказ-ся не разрешима, т.е. Тmax→∞, Tmin→-∞, то исходная задача также неразрешима по причине либо не совместности с-мы огр-й, либо неогран-ти цел. функ.

12Симметрич. ДЗ

В ИЗ цел функция – Z, перем-ые – х. В ДЗ цел.фукн.- W, перем-е –u.

Правило построения ДЗ: 1) число огран-й ДЗ= числу перем-х в ИЗ и наоборот; 2) матрица коэф. при перем-х в ДЗ получена путем транспонирования матрицы коэф. при перем-х в ИЗ; 3) знаки нерав-в с-мы огран-й ДЗ противоп-ы по смыслу знакам нер-в с-мы огран-й ИЗ; 4) в кач-ве св. чл огран-й ДЗ вытупают коэф-ы при соот-х перем-х в урав-х цел. функ. ИЗ. А в кач-ве коэф-в в урав-и цел. функ. ДЗ выст-ют св. чл соот-х огран-й ИЗ; 5) цел. функ. ДЗ меняет свое знач-е на сходное (была мах, стала мин); 6)если ИЗ на мах и в с-ме огр-й есть разнородные нер-ва, то их надо привести к типу ≤. Если ИЗ на мин, то к типу≥.

Основная теорема двойст-ти

1. Если 1 из ДЗ имеет опт-ое реш-е, то др. также имеет опт-ое реш-е, причем Хопт=Uопт, Zmax=Wmin; 2. Если 1 из ДЗ неразреш-а по причине неогран-ти цел.функ., то др. задача не имеет допуст. реш-й

Решая 1 из ДЗ СМ в последней симплекс. табл.мы найдем реш-е и др. задачи. Для этого необ-о привести с-му к канон. форме к единич. базису (при этом св.чл м.б. «-») и записать соот-е во взаимосвяз-ые пары, т.е. бп ДЗ соот-т св.п ИЗ и наоборот. Зная соот-е перем-х по результатам последней симплекс.табл. ИЗ можно записать реш-е ДЗ, при этом: 1. перем-е ДЗ, соот-щие св. п послед.сим.табл. ИЗ, приравн-ся к оц-кам соот-щих св.п ИЗ; 2. перем-е ДЗ, соот-щие бп послед. сим.табл. ИЗ, приравн-ся к нулю.

13ТРАНСПОРТНАЯ ЗАДАЧА

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

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

С_ij – стоимость перевозки единицы груза, а_i – запас груза у i – го поставщика (i =1…m), b_i- потребность в грузе j- потребителя (j=1…n), х – кол-во груза от i-го поставщика к j –потребителю.Постановка задачи (на мин-ую стоимость перевозки груза): найти значение переменных x_ij обеспечивающих целевой функции и удовлетворяющих системе ограничений: 1. Сумма всех грузов перевезенных от i-поставщика д.б. равна запасу груза у этого поставщика. 2. Сумма всех грузов, доставляемых j- потребителю д.б. равна потребности этого потребителя. 3. Неотрицательность переменных. Т.е.:

1 i=1…m

2 j=1…n

3 x_ij 0 i=1…m, j=1…n

Причем, для того чтобы решить транспортную задачу, сумма запасов однородного груза у поставщиков должна быть равна сумме потребностей в этом грузе потребителей (закрытая модель).

В случае невыполнения этого условия (открытая модель) необходимо произвести некоторые преобразования (введениефиктивного поставщика илипотребителя) и получить закрытую модель.

Алгоритм решения транспортной задачи состоит из двух шагов:

- составление первоначального опорного плана каким-либо методом (минимального элемента в таблице, северо-западного угла, аппроксимации);

- улучшениеэтого плана и доведение его до оптимального методом потенциалов.

Рассмотрим алгоритм составления первоначального опорного плана методом аппроксимации. Данный метод особенно эффективен для задач малой размерностью, так как в большинстве случаев приводит к оптимальному решению.

В распределительной таблице добавляются нулевой столбец (слева) и нулевая строка (сверху).

В нулевую строку записываются разности, полученные в соответствующих столбцах путем вычитания наименьшей стоимости из следующей за ней по величине. В нулевой столбец заносят разности, полученные аналогично в строках. Из всех полученных разностей выбирается наибольшая. При этом могут встретиться два случая:

1. Одна наибольшая разность. Тогда в соответствующей строке (столбце) обычным образом заполняется клетка, в которой стоит наименьшая стоимость, и рассчитываются новые разности.

2. Несколько одинаковых наибольших разностей. В этом случае в соответствующей строке (столбце) находим клетку, в которой стоит наименьшая стоимость, и проверяем, будет ли этот показатель наименьшим в противоположном ряду.

Для строки противоположным рядом будем считать столбец, а для столбца - строку.

Здесь возможны следующие моменты:

- условие выполнено для одной клетки. Тогда с нее начинаем заполнение таблицы;

- условие выполнено для нескольких клеток. Тогда заполняется та, которой в противоположном ряду соответствует большая разность. Если противоположные разности равны, то заполняем обе клетки;

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

Дата добавления: 2018-02-15; просмотров: 644; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 123 4 5 6 7 8 9 Следующая ⇒

Мы поможем в написании ваших работ!