11. Стандартная форма модели задач ЛП и ее особенности

Стандартная форма имеет следующий вид.

Найти максимум или минимум целевой функции z:
z = С1x1 + … + Сnxn → max (min) (1)
При выполнении следующих ограничений:
а11 Х1 + а12 Х2 + … +  а1n Хn   ≤  а1

а21 Х1 + а22 Х2 + … +  а2n Хn   ≤  а2

…………………………………………..

am1 Х1 + аm2 Х2 +… + аmn Хn  ≥  аm

хj ≥ 0, j = 1, k,  k ≤ n
Особенности стандартной  формы модели задачи ЛП следующие:

1.    система ограничений представлена в виде неравенств (нежестких условий)

2.    условия неотрицательности накладываются на все переменные

3.    целевая функция стремится либо к max, либо к min

12. Каноническая форма модели задач ЛП и ее особенности

Каноническая форма имеет вид:

Найти минимум целевой функции z:
z = С1x1 + … + Сnxn → min
При выполнении следующих ограничений:

а11 Х1 + а12 Х2 + … + а1n Хn = а1

а21 Х1 + а22 Х2 + … + а2nxn = а2

…………………………

am1x1 + аm2 X2 +… + аmn Xn = am

Xj  ≥0, j = 1, n
Особенности канонической формы следующие:

1.    Система ограничений представлена в виде уравнений (жестких условий).

2.    Условия неотрицательности накладываются на все переменные

3.    Целевая функция стремится к

В некоторых источниках целевая функция задачи ЛП, представленной в канонической форме, стремится к максимуму. Это делается для удобства решения  задачи по алгоритму, разработанному на максимум целевой функции.

13. Возможный, допустимый, оптимальный опорный план задачи, ОДЗ задачи ЛП


Определение 1. Значения неизвестных переменных, удовлетворяющие всем ограничениям задачи линейного программирования, называются допустимыми значениями переменных или планами.

Определение 2. Множество всех планов задачи линейного программирования называется областью допустимых значений переменных (ОДЗ).

Определение 3. План задачи линейного программирования, при котором целевая функция принимает минимальное (или максимальное) значение на ОДЗ называется оптимальным.

14. Виды записей задач ЛП: развернутая, свернутая, матричная, векторная.

Модели задач ЛП могут быть записаны в различных видах.

1. Развернутый вид записи модели

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,
Xj ≥ 0, j = 1, n.
2. Свернутый вид:

                        ,

Xj ≥ 0, j = 1, n.
3. Модель задачи ЛП в матричном виде:

                  X ≥ 0

Где 

               а11    а12    …    а1n                         X1                           a1

  A=        a21    a22    …    a2n   ,           X=     X2  ,            A0 =    a2

               …      …     …     …                           …                            …

               am1  am2  …    amn                          X3                           am

 

4. Модель задачи ЛП в векторном виде:





X ≥ 0

Где    

          Х1                  a11                   a12                  a1n                  a1

  Х2    ,      a21   ,       a22    ,     a2n   ,      a2

          …                   …                     …                   …                    …

          Хn                  am1                  am2                am2                 am

15.
Переход от стандартной и общей формы задач ЛП к канонической. Теорема связи

Для перехода от общей или стандартной формы к канонической используют следующие приёмы.

1. Преобразование переменных. Если какая-то переменная  Xk неположительна (Xk ≤ 0), то вводят новую переменную Xk ', так что Xk ' =  –Xk . Очевидно, что  Xk ' ≥ 0. После этого в каждом ограничении и целевой функции переменную  Xk заменяют на [ – Xk '].

Если какая-то переменная Хt может принимать любые значения, то её заменяют разностью двух неотрицательных переменных Хt’ и Хt’’,  т. е. полагают, что  хt = Хt’ –  Хt’’, где Хt’ 0 ≥ и Хt’’  ≥ 0.

2. Преобразование ограничений. Если какое–либо из ограничений в модели имеет вид неравенства, то оно преобразуется в равенство прибавлением (если неравенство имеет тип ≤) или вычитанием (если неравенство имеет тип ≥) из его левой части. Эти переменные называют балансовыми. Балансовые переменные входят в целевую функцию с коэффициентами нуль. Балансовая переменная принимает значение индекса последовательно после уже имеющихся. Если, например, система ограничений имеет 5 переменных, то первая балансовая переменная будет Х6, а вторая – Х7 и т.д.

16.  
Переход от канонической формы модели ЗЛП к стандартной
Для перехода от канонической формы к стандартной можно каждое из

уравнений заменить системой неравенств:


Другой способ состоит в приведении системы уравнений к специальному виду и дальнейшему исключению некоторых переменных.
С помощью метода Жордана-Гаусса выделяем в каждом уравнении базисную переменную. Такое выделение осуществляется с помощью эквивалентных (элементарных) гаусовских преобразований. К ним относятся:

а) умножение любого уравнения на константу отличную от нуля;

б) прибавление к любому уравнению любого другого уравнения, умноженного на любую константу.

Исходную систему линейных уравнений перед преобразованием удобно записывать в виде матрицы или таблицы:

Далее находим х₁, х₂ … х_n . Далее подставляем в целевую функцию z выражениех₁ и х₂ … х_n.

Записываем задачу в стандартной форме.
17. Понятие гиперплоскости полуплоскости, опорная гиперплоскость.

18.  Геометрич. интерпретация системы ограничений и целевой функции в задачи ЛП

19. Выпуклое множество: крайние (угловые) точки множества. Выпуклый многогранник

Определение Множество М называется выпуклым, если вместе с любыми двумя точками, принадлежащими данному множеству, оно содержит и отрезок их соединяющий.






                        Выпуклое множество

Определение Точка х множества М называется угловой или крайней, если она не является внутренней ни для какого отрезка, целиком принадлежащего данному множеству.

Теорема 1. Любую точку отрезка можно представить в виде выпуклой комбинации его угловых точек.

х = λ₁ А + λ₂ В

λ₁, λ₂ ≥ 0                выпуклая комбинация точек угловых точек А и В

λ₁ +  λ₂ = 1
Теорема 2. Любую точку выпуклого замкнутого множества можно представить в виде выпуклой комбинации его угловых точек.

20. алгоритм графического метода решения задач ЛП

Алгоритм графического метода.

1. Проверяется, находится ли исходная ЗЛП в стандартной форме, если нет, то задачу необходимо преобразовать к стандартной форме.

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

3. Строится область допустимых значений переменных для ЗЛП.

4. Строится направляющий вектор c .

5. Через ОДЗ проводится исходная изоцель (перпендикулярно направляющему вектору).

6. Проводится мысленное перемещение исходной изоцели в направлении вектора c , если определяется максимальное значение целевой функции, или в противоположном направлении, если определяется её минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ и будут оптимальными точками задачи.

7. Для того, чтобы определить координаты оптимальной точки, необходимо решить систему соответствующих линейных уравнений.

8. Для нахождения оптимального значения целевой функции необходимо оптимальные значения переменных подставить в целевую функцию и вычислить её значение.
20. алгоритм графич. метода решения задач ЛП

Алгоритм графического метода.

1.    Последовательным построением каждого из условий системы ограничений задачи осуществляется построение ОДЗ.

2.    Строится направляющий вектор С по коэффициентам при переменных целевой функции.

3.    Перпендикулярно направляющему вектору через начало координат проводится исходная изоцель.

4.    Проводится мысленное перемещение исходной изоцели в направлении возрастания значений вектора С, если определяется максимальное значение целевой функции или в противоположном направлении, если определяется ее минимальное значение, до тех пор, пока изоцель не станет опорной к ОДЗ. Точки пересечения опорной изоцели и ОДЗ будут оптимальными точками задачи.

5.    Для определения координат оптимальной точки необходимо решить систему  соответствующих  линейных уравнений тех условий, на пересечении которых находится оптимальная точка.

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

23. теоремы об области допустимых значений задачи ЛП и о целевой ф-ции


Теорема об ОДЗ. Область допустимых решений задачи ЛП выпуклое множество (замкнутое и ограниченное в n-мерном пространстве)

Теорема 2. О целевой функции задачи линейного программирования.

Целевая функция ЗЛП принимает своё оптимальное значение в одной из угловых точек области допустимых значений переменных. Если целевая функция принимает своё оптимальное значение в нескольких угловых точках, то такое же значение она принимает и в любой точке, являющейся выпуклой комбинацией данных угловых точек.

24. Теорема об угловой точке. Достаточное и необходимое условие

25. Следствия из теоремы о свойствах решений задач ЛП и выводы. Понятие опорного плана.

Следствия из теорем.

Определение. План = (х1,х2,…,хn), положительным координатам которого соответствуют линейно независимые векторы, называется опорным планом ЗЛП.

Следствие1. Опорный план имеет не более m положительных координат.

Если он имеет ровно m положительных координат, то такой опорный план называется невырожденным, в противном случае вырожденным.

Следствие 2. Каждая угловая точка ОДЗ является опорным планом.
27. Алгоритм симплексного метода.

При решении задач ЛП симплексным методом необходимо выполнить следующую последовательность действий.

1.   Проверяется, находится ли задача ЛП в канонической форме. Если нет, то необходимо исходную модель преобразовать в каноническую форму.

2.   Выделяется начальный опорный план и значение целевой функции при этом опорном плане.

3.   Проводится построение исходной симплексной таблицы.

4.   Проверяются значения оценок оптимальности в индексной строке. Если нет положительных оценок, то выписывается оптимальное решение и алгоритм заканчивает свою работу. В противном случае выполняется пункт 5.

5.   В базисе вводится вектор, которому соответствует наибольшая положительная оценка. Данный столбец называется разрешающим.

6.   Из базиса выводится вектор, которому соответствует симплексное отношение, рассчитанное по формуле          0 < Ө ≤  . Данная строка называется разрешающей строкой.

7.   Строится новая симплексная таблица. Соответствующим образом изменяются столбцы Б и С_Б. остальная часть таблицы заполняется из предыдущей с помощью гауссовских преобразований, причем индексная строка считается m+1 строкой и также преобразуется с помощью гауссовских преобразований. Переходим к выполнению пункта 4 данного алгоритма.

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

28. выбор базиса и построение начального опорного плана при решении задач симплекс методом.

29. Симплекс-таблицы, их заполнение. Формулы расчета коэффициентов индексной строки.






30. Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом.

Теорема 1: Если для некоторого вектора Ā_j в системе

Х₁            + а_1m+1X_m+1 + а_1m+2X_m+2 + … + а_1nX_n = a₁

      Х₂      + а_2m+1X_m+1 + а_2m+2X_m+2 + … + а_2nX_n = a₂

…………………………………………………..

          X_m + а_mn+1X_m+1 + а_mn+2X_m+2 + … + а_mnX_n = a_m

Выполняется соотношение Z_j – c_j > 0, то план Х_Б0 не является оптимальным и можно перейти к плану Х_Б1 такому, что Z (Х_Б1) ≤ Z (Х_Б0).

Здесь Z_j = (С, Ā_j) – скалярное произведение векторов.

С – вектор, состоящий из коэффициентов при базисных переменных целевой функции Z

Ā_j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

c_j – коэффициент целевой функции Z при переменной Х_j

Следствие из теоремы: Если для всех векторов Ā₁, Ā₂, …, Ā_n некоторого опорного плана Х выполняется соотношение Z_j – c_j < 0, то опорный план Х является оптимальным. Величины (Z_j – c_j) – называются оценками оптимальности соответствующих векторов.

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

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

31. Выбор вектора, вводящегося в базис и выводящегося из базиса. Симплексное отношение.

Для перехода к новому опорному плану необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Пусть таким вектором будет вектор А m+1 .

Разложению –

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



Координаты  вектора Х1 должны быть неотрицательными, т.е. .

Если  , то эта координата будет неотрицательной.



Пусть минимум в соотношении (5) был получен при i =1, тогда если взять



то первая координата вектора 1 х станет равной нулю.

Соотношение (6) называется симплексным отношением. Таким образом, мы перешли от исходного опорного плана 0 х (базисные векторы А1,А2,…Аm) к опорному плану 1 х (базисные векторы А2,А3,…,Аm,Am+1).
32. разрешающий элемент таблицы, его выбор. Правило полных жордановых исключений для перерасчета симплекс таблицы.










33. Правило  «четырехугольника» для перерасчета симплекс-таблицы

34. Признак единственности оптимального плана, множества оптимальных планов и отсутствия оптимального плана при решении задача ЛП симплекс-методом.

При решении задач симплекс-методом возможны следующие виды оптимальных решений:

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

2. Альтернативный оптимум (множество оптимальных решений).

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

3. ЗЛП не имеет оптимального решения, так как целевая функция не ограничена снизу. Если в симплекс таблице имеется положительная оценка, а все элементы данного столбца отрицательны и нулевые, то данный вектор можно ввести в базис. Однако никакой из базисных векторов нельзя вывести из базиса. Из этого следует, что дальнейшее уменьшение целевой функции возможно при переходе к неопорному плану.

4. ЗЛП не имеет оптимального решения, так как система ограничений противоречива. Поскольку при решении ЗЛП обычным симплекс-методом должен быть исходный опорный план, то система линейных уравнений заведомо не противоречива. Следовательно, такой случай не может встретиться при решении обычным симплекс методом.

5. Если ОДЗ состоит из одной точки, то решение такой задачи является тривиальным, и может быть получено без использования симплекс-метода.

35. В каких случая применяется метод искусственного базиса
Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. е. исходный опорный план отсутствует. В этом случае в те уравнения, в которых нет базисных переменных, необходимо добавить с коэффициентом +1 некоторую неотрицательную переменную. Такая переменная называется искусственной.
36. Построение М-задачи в методе искусственного базиса

Если задача линейного программирования находится в канонической форме, однако, не во всех уравнениях присутствуют базисные переменные, т. е. исходный опорный план отсутствует. В этом случае в те уравнения, в которых нет базисных переменных, необходимо добавить с коэффициентом +1 некоторую неотрицательную переменную. Такая переменная называется искусственной.

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

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

Строится исходная симплекс таблица.

37. построение индексной строки в методе искусственного базиса

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

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

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

39. Алгоритм двойственного симплекс-метода
Алгоритм двойственного симплекс-метода:

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

2.      Выбирают направляющую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов А0

3.      Выбирают направляющий столбец по наименьшему по абсолютной величине отношению элементов индексной строки к отрицательным элементам направляющей строки.

4.      Пересчитывают симплексную таблицу по правилу полных жордановых исключений

5.      проверяют полученный план на допустимость. Признаком получения допустимого опорного плана является отсутствие в столбце А0 отрицательных элементов. Если в столбце А0 имеются отрицательные элементы то переходят ко второму пункту. Если же их нет, то переходят к решению полученной задачи обычным способом.

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

41.  Открытые и закрытые транспортные модели. Переход от открытой транспортной модели к закрытой.

Типы транспортных задач.

Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку.

Если сумма объёмов запасов продукции равна объёму потребностей всех потребителей, то такая задача называется закрытой транспортной задачей

(т. е. если ∑ Ai = ∑ Bj), в противном случае транспортная задача называется открытой. Для решения транспортной задачи необходимо, чтобы она была закрытой.

Открытую транспортную задачу можно преобразовать к закрытой следующим образом.

Пусть ∑Ai > ∑Bj. В этом случае необходимо ввести фиктивного n+1 потребителя с объёмом потребностей ∑Ai – ∑Bj Удельные затраты на перевозку от поставщиков к фиктивному потребителю полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторая часть продукции останется у поставщиков.

Если ∑Bj > ∑Ai . В этом случае необходимо ввести фиктивного m+1 поставщика с объёмом запасов∑Bj – ∑Ai . Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.

42. Способы построения первоначального распределения в транспортной задаче: метод северо-западного угла и метод наименьшего элемента в матрице.

Северо-западный прием построения опорного плана. Согласно этому приему формирование величин перевозок начинается с с.-з. уголка таблицы, т.е. с клетки x11. По этому приему прежде всего распределяется товар первого поставщика. Причем первый поставщик сначала предельно возможно удовлетворяет первого потребителя. Затем, если у поставщика товар еще остался,

Метод наименьшего элемента в матрице.

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

Сначала делаем пометки (например, знаком ▼ ) в тех клетках строк, в которых наблюдается самая меньшая цена по строке. Затем обходим таблицу по столбикам и делаем такие же пометки в клетках, в которых самая маленькая цена по столбикам.

Дальнейшее распределение делается сначала предельно возможно по клеткам с двумя отметками, потом - с одной, а затем делается добалансировка задачи до (m + n – 1) заполнений. Заполнения организуем при прохождении таблицы слева направо и сверху вниз.
43. Свойства транспортных задач

Транспортная задача обладает некоторыми свойствами, которые можно отразить следующими теоремами.

Теорема 1. Закрытая транспортная задача всегда имеет решение.

Теорема 2. Если объёмы запасов продукции и объёмы потребностей является целыми числами, то и решение транспортной задачи также будет целочисленным.

Теорема 3. система ограничений закрытой транспортной задачи всегда линейно-зависима.

Из этой теоремы следует, что распределение закрытой транспортной задачи всегда имеет m + n – 1 базисную переменную и (m – 1) (n – 1) свободные временные.
44. Вырожденное распределение в транспортных задачах, избавление от вырожденности. Вычеркиваемая комбинация.

Распределение называется вырожденным, если количество клеток меньше чем m + n – 1.

45. Теорем оптимальности транспортной задачи.

Теорема. Если для некоторого распределения транспортной задачи вы-

полняются условия:

а). ui+vj = сij для занятых клеток

б) ui+vj ≤ сij,, для свободных клеток,

то данное распределение является оптимальным.

Величины ui называют потенциалами строк, а величины vj называют потенциалами столбцов.
46. Потенциалы и  способы их расчета.

Для нахождения потенциалов строк и столбцов пользуются следующими рассуждениями, исходя из условия а) теоремы оптимальности.

Количество уравнений исходя из этого условия равняется m + n – 1, а количество неизвестных ui и vj равняется m + n. Т.о. количество переменных больше количества уравнений, причем все уравнения линейно независимы.  Решение такой системы линейных уравнений является неопределенным, поэтому одному из потенциалов нужно присвоить любое значение. На практике ui = 0. получается система из m + n – 1 уравнений с m + n – 1 неизвестными переменными. Эту систему можно решить любым методом. На практике для расчета потенциалов рассматриваются занятые клетки, для которых один их потенциалов известен, и исходя из условия а) теоремы вычисляются значения остальных неизвестных потенциалов.
47. расчет оценок оптимальности распределения транспортных задач и критерий оптимальности.

Исходя из соотношения б) теоремы можно записать следующую формулу для вычисления оценок: δ ij = ui +vj – сij. Для того, чтобы оценки не перепутать с объёмами перевозок, они (оценки) заключаются в круги.

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

48. перераспределение поставок в транспортной задаче

Если распределение не является оптимальным, то необходимо осуществить перераспределение поставок.

Для перераспределения осуществляют построение цикла пересчета. В качестве клетки выбирается клетка с наибольшей положительной оценкой. Эта клетка помечается знаком «+», то есть в неё необходимо записать некоторый объём поставки. Но тогда нарушится баланс по данному столбцу, следовательно, одну из занятых клеток данного столбца необходимо пометить знаком «-», то есть уменьшить объём поставки на такую же величину. Но тогда изменится баланс по данной строке, следовательно, какую-то занятую клетку данной строки необходимо пометить знаком «+». Данный процесс продолжается до тех пор, пока не поставлен знак «-» в строке, где находилась исходная клетка.

Для любой свободной клетки существует цикл пересчета и притом единственный.
49. цепочки перераспределения, их виды.

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

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

Для этого Q надо выбрать равным наименьшему уменьшаемому из клеток, в которых Q вычитается. На следующих рис. 7.1 и 7.2 покажем примеры циклов и правило вычисления.



    



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

50. Выбор объема перераспределения.

Определение объёма перемещаемой продукции. При определении объёма продукции, перемещаемого по циклу пересчёта, мы должны исходить из следующих двух соображений:

а) после преобразования в клетках таблицы не должны получиться отрицательные числа;

б) одна из занятых клеток должна стать свободной.

Для того, чтобы эти условия выполнялись, необходимо объём перемещаемой продукции выбрать следующим: θ=min {хij} -, где {хij} – объёмы перевозок из клеток цикла пересчёта, помеченных знаком «-».

θ = min{20;30}=20

К значениям клеток, помеченных знаком «+»прибавляется θ. От значений клеток, помеченных знаком «-», вычитается θ. Значение поставок остальных клеток переписывается без изменений. В результате получим следующую таблицу.
53. Алгоритм метода потенциалов.

Алгоритм:

1. Проверить, выполняется ли для задачи рав-во если нет, то в задачу вводится фиктивный поставщик или потребитель

2. Условие задачи записывается в форме транспорт.таблицы

3. Строится начальный опорный план

4. Определяются потенциалы пост-ков и потреб-лей

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

6. Загруж-т перспективную клетку. Оформл-т нов.опорн.план в виде трансп.таблицы. Переходят к пункту 4.
54. Учет затрат на производство и транспортировку продукции. Транспортная задача с запретами на поставки.

При решении некоторых задач необходимо учитывать затраты не только на перевозку груза, но и на производство перевозимой продукции. Для этого в матрице трансп. задачи
Где Cij ‘ – приведенные затрат на производство одной единицы продукции.

Cij “– затраты на транспортировку одной единицы продукции.

 Дальше задача решается обычным способом.
Задачи с запретами на поставки.

В некоторых ситуациях нельзя перевозить продукцию по какому-либо маршруту.

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

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

учет ограничений по пропускной способности маршрутов.

В некоторых транспортных задачах по некоторым маршрутам устанавливают меньшую пропускную способность чем необходимо для удовлетворения спроса пункта потребления.
учет обязательности некоторых поставок в транспортной задаче.

В некоторых случаях в задаче требуется, что например по маршруту Ak Bs должно обязательно осуществиться поставка в объема А ед. В  этом случае из объема производства пункта А и объем S Bs вчитается обязательная поставка и задача решается относительно необязательности поставок. После получения оптимального решения обязательно поставка добавляется к объему стоящему в клетке Ak Bs.
56. Возможные выводы при экономич. интерпретации оптимального распределения для открытых транспортных задач.

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

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

2.      если же введен фиктивный пункт производства, то это означает, что мощностей реальных пунктов производства не хватает и их необходимо увеличить. Увеличиваются мощности тех пунктов производства, которые ближе всего расположены к пунктам потребления, привязанным к фиктивному пункту производства. Производится увеличение мощности производителя на величину привязки. Для этого рассматривают столбец пункта потребления, который привязан к фиктивному пункту производства, и находят в нем наименьший тариф. Мощность соответствующего этому тарифу пункта производства наиболее эффективно увеличить на величину привязки.
57.Понятие двойственности. Экономическая постановка двойственных задач на примере задачи об оптимизации плана выпуска продукции.

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

Пусть имеется зада об оптимизации плана выпуска продукции. Она имеет следующий вид:

Исходная задача:

а₁₁х₁+а₁₂х₂+…+ а_1пх_п≤в_{1              |}у₁

а₂₁х₁+а₂₂х₂+…+ а_2пх_п≤в_{2              |}у<sub>2

………………..                                                 |..</sub>      (1)

а_т1х₁+а_т2х₂+…+ а_тпх_п≤в_{1           |} у_т
x_j≥0, j = 1,n(2)
z = c₁x₁+c₂x₂+…+c_nx_n ->max(3)

 _

 X = (x_1,x₂,…, x_n)

a_ij – кол-во сырья i- го вида, затраченного для выпуска j-го вида продукции

Двойственная задача

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

у_i- цена i- го вида сырья имеющегося на предприятии.

а₁₁у₁+а₂₁у₂+…+ а_т1у_т≥с₁             

а₁₂х₁+а₂₂у₂+…+ а_т2х_п≥с<sub>2             

………………..</sub>                                                       (1’)

а_1пу₁+а_2пу₂+…+ а_тпу_т≥с_п           

у_i≥0, j = 1,m(2’)
F = b₁y₁+b₂y₂+…+b_my_m ->min(3’)


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

Каждой задаче линейного программирования можно сопоставить

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

1. Во всех ограничениях исходной задачи свободные члены должны

находиться справа, а члены с неизвестными - слева.

2. Ограничения-неравенства исходной задачи должны иметь знаки,

направленные в одну строну.

3. Если целевая функция в исходной задаче минимизируется, ограничения-неравенства следует записать со знаком «≤» , тогда в двойственной задаче целевая функция будет минимизироваться и знаки ограничений-неравенств будут «≥».

4. Каждому ограничению исходной задачи соответствует переменная в

двойственной задаче. Если переменная соответствует неравенству, она неотрицательна, если равенству – то переменная без ограничений на знак («произвольная»).

5. Коэффициенты при переменных в ограничениях двойственной задачи получаются транспонированием матрицы, составленной из

коэффициентов при переменных исходной задачи.

6. Свободные члены исходной задачи являются коэффициентами при

переменных в функции цели двойственной задачи, а свободными

членами в двойственной задаче – коэффициенты при переменных в

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

59. Построение двойственных задач к исходным задачам, записанным в стандартной, канонической и общей форме модели(построение симметричных и несимметричных двойств. задач)


Стандартная форма (исходная)

  _n

Σ a_ijx_j ≤ b_i, i=1,n(1)

 ^j=1

x_j≥0, j=1,n(2)

       _n

z = Σ c_jx_j ->max(3)

      ^j=1

Двойственная стандартная

  _m

Σ a_ijy_i ≤ c_j, j=1,n(1)

 ⁱ⁼¹

y_i≥0, j=1,m(2)

       _m

F = Σ b_iy_i ->min(3)

      ⁱ⁼¹

Исходная задача в канонической форме:

  _n

Σ a_ijx_j = b_i, i=1,m(1)

 ^j=1

x_j≥0, j=1,n(2)

       _n

z = Σ c_jx_j ->min(3)

      ^j=1

Двойственная каноническая
  _m

Σ a_ijy_i ≤ c_j, j=1,n(1)

 ⁱ⁼¹

y_i- любые (2)

       _m

F = Σ b_iy_i ->max(3)

      ⁱ⁼¹
Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й  продукции – aij.Требуется определить объем производства продукции каждого вида xj  (j=1,n), максимизирующий суммарную стоимость

 f= c1x1+…+cnxn    (1)

При этом расход ресурсов не должен превышать их наличия:

a11x1+…+a1nxn<=b1     }

……………………..        } (2)

am1x1+…+amnxn<=bm  }

Все известные по своему экономическому смыслу неотрицательны:

Xj>=0  (j=1,n). (3)

 

Заметим, что это задача образуют симитричную  двойственную задачу.

Несимметричные двойственные задачи.

Возьмем ЗЛП на максимум в канонической форме:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi  (i=1,m)

Xj>=0  (j=1,n).



60.Основная и вторая  теорема двойственности (сформулировать теоремы и разъяснить)

 Первая теорема двойственности.

Теорема: если одна из двойственных задач имеет оптимальный план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi*  если в исходн. задаче целевая функция неограниченна на множестве планов, то в двойственной задаче система ограничений несовместна.

Вторая теорема двойственности и ее эконом.интерпритация.

Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств.задачи обращ-ся оптималь.планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю.Если же какая-то  компонента опт. плана равна нулю, то соответствующее ограничение двойств.задачи обращается опт.планом в строгое равенство   хj*>0 следовательно (i= от 1 до m)Σaij yi*=cj   (затраты на пр-во продукции=цене) – Если продукция вошла в опт.план, то если затраты>цены, объем пр-ва=0 Σaij yi* >cj следовательно xj*=0 

yi*>0 следовательно (j=от 1 до n) Σaij xj*=bi (рас-ды рес-ов =запас рес-ов).

(j=от 1 до n) Σaij xj* <bi следовательно  yi*=0

Смысл теоремы сводится к следующему:

-если стоимост.оценка рес-ов расход-х на пр-во ед.прод-ии=цене, то этот вид прод-ии входит в оптим.план ;

-если затраты превышают цену, то прод-ию производить не следует;

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

-если рес-с израсходован неполностью, то его стоимост.оценка = 0.

1. Реферат Для мини пивоварни
2. Реферат Україна у чорноморському регіоні
3. Реферат Функции налогов и их взаимосвязь
4. Реферат на тему Constitutional Issues
5. Реферат на тему Компьютерное моделирование местной вентиляции
6. Реферат на тему Биосфера планеты
7. Реферат Характеристика, бюрократической организации. Теория бюрократии М. Вебера
8. Сочинение на тему Чехов а. п. - Человек и среда в рассказах а. п. чехова. человек и среда в рассказе а. п. чехова
9. Реферат Свободные экономические зоны в мировом хозяйстве
10. Реферат Бенчмаркетинг и его применение на предприятии