22. Виды двойственных задач. Правила составления несимметричных двойственных задач линейного программирования.
Можно рассмотреть 2 вида двойственных задач:
- симметричный
- несимметричный
+ смешанный
В несимметричном случае одна из задач представлена в канонической форме. (в матрице после вертикальной границы вертикально стоят y1,y2,…,ym)
a11x1+a12x2+…+a1nxn=b1
a21x1+a22x2+…+a2nxn=b2
……………………………
am1x1+am2x2+…+amnxn=bm
xj≥0 j=1,n
!!! Основные правила составления двойственной задачи те же, что и в симметричном случае. Отличаются пункты 5 и 7.
5. Если в целевой функции двойственной задачи требуется найти max, то в системе ограничений будут содержаться неравенства вида ≤. А если двойственная задача на min, то ≥.
7. т.к. в прямой задаче в системе ограничений содержатся только уравнения, то в двойственной задаче условия неотрицательности отсутствуют. Т.е. yi – произвольно изменяющаяся переменная.
Таким образом для указанной прямой задачи двойственная задача примет вид:
Z(Y)= b1y1+b2y2+…+bmym→min
a11y1+a21y2+…+am1ym≥c1
a12y2+a22y2+…+am2ym≥c2
………………………………
a1ny1+a2ny2+…+amnym≥cn
yi≥0, i=1,m
- 9. Алгебраический симплексный метод. Основные положения данного метода.
- 10. Алгоритм решение задачи симплексным методом(первый опорный план)
- 11. Алгоритм решения задачи симплексным методом ( проверка на оптимальность, определения ведущего столбца и строки, построение нового опорного плана).
- 13. Анализ оптимального плана симплексного метода на примере задачи планирования товарооборота.
- Метод искусственного базиса на примере системы ограничений, содержащей уравнения.
- Основные теоремы линейного программирования. Фундаментальная теорема и теорема об альтернативном оптимуме.
- Геометрическая интерпретация симплекс-метода.
- Двойственная задача линейного программирования и ее математическая модель.(не до конца!!!!)
- 21. Виды двойственных задач. Правила составления симметричных двойственных задач линейного программирования.
- 22. Виды двойственных задач. Правила составления несимметричных двойственных задач линейного программирования.
- Основное неравенство теории двойственности. Достаточный признак оптимальности. Первая теорема двойственности.
- 24. Экономический смысл первой теоремы двойственности.
- 25. Вторая теорема двойственности. Определение двойственных оценок с помощью второй теоремы двойственности.
- 26. Определение двойственных оценок однородной задачи линейного программирования симплекс-методом.
- 31) Транспортная задача линейного программирования, ее математическая модель.
- 33. Построение начального опорного решения тз методом наименьших тарифов.
- 34. Построение начального опорного решения тз методом северо-западного угла.
- 35. Построение начального опорного решения тз методом двойного предпочтения.
- 37. Метод потенциалов тз. Проверка плана на вырожденность. Проверка решения транспортной задачи на оптимальность.
- 38. Построение нового опорного решения тз. Понятие цикла.
- 39. Анализ оптимального решения тз. Рекуррентная формула расчета целевой функции.
- Поток Пальма. Поток Эрланга.
- Графы состояний смо.
- Цепи Маркова.
- Случайные процессы. Марковские случайные процессы.
- Уравнения Колмогорова.