Симплекс-метод решения злп

35. Как должна выглядеть с/таблица перед применением с/метода.

В последней строке среди Δj, j=1…..n, д. б. Δj<0, а в соотв. min Δj столбце должно быть a_ik>0; в столбце А₀ все числа a_i0 должны быть >0.

36. Как должна выглядеть с/таблица перед применением двойственного с/метода.

В столбце А₀ д. б. хотя бы одно отриц. число a_i0<0, в i-ой строке д.б. хотя бы одно отрицательное число и в последн. строке Δj>0.

37. Что означает факт невозможности преобразования с/таблицы с помощью алгоритма с/метода.

Найден оптимальный план, или D – неограниченный многогранник, т.е. С(х) неограниченна на D.

38. Что означает факт невозможности преобразования с/таблицы с помощью алгоритма двойственного с/метода.

Найден оптимальный план, или D=.

39. В каком случае преобразование с/таблицы с помощью с/метода оказывается невозможным.

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

40. В каком случае преобразование с/таблицы с помощью двойственного с/метода оказывается невозможным.

Если в строке, где находится минимальное отрицательное число столбца , нет отрицательных чисел, то преобразование с/таблицы невозможно.

41. Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется с/метод.

, , - ведущий элемент

42. Как находится ведущий элемент симплексной таблицы, если для ее преобразования используется двойственный с/метод.

, , - ведущий элемент

43. Как решается ЗЛП с доп. активным ограничением?

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

Пусть - опт план, и . Последней итерации с/таблицы соответствует система уравнений: . Координаты оптимального плана . Добавим к исходной ЗЛП доп активное ограничение: . Введём доп. переменную : , (1). выражается из и подставляется в (1), получается: . Выделим и сгруппируем свободные переменные, а постоянные – в правую часть: . Тогда доп. переменная . Последнее полученное выражение записывается в (m+1)-ю строку с/табл. Появляется новый единичный базисный вектор A_n+1. За счёт доп. ограничения получается новая ЗЛП, в которой имеется псевдоплан . n новых двойственных оценок не изменились, а оценка _n+1=0, как оценка базисного вектора A_n+1. Кроме того, x_m+1,0<0, т.к. , т.к. доп. ограничение активное. Имея псевдоплан, продолжаем решение ЗЛП двойственным с/методом.

Элементы теории двойственности

44. Верно ли, что двойственная задача к стандартной имеет канонический вид, а двойственная задача к канонической имеет стандартный вид.

Нет.

45. Напишите двойственную задачу к следующей задаче ЛП: AX=B, X>=0, C(X) MIN

B(Y)  Max

А^тYC

46. Напишите двойственную задачу к следующей задаче ЛП:AX>=B, C(X)  MAX

B(y) Max

-А^тY=C

Y0

47. Сколько ограничений и неизвестных в двойственной задаче.

Ограничений столько, сколько переменных в прямой (исходной) задаче (n).

Неизвестных столько, сколько ограничений в прямой (исходной) задаче (m).

48. Сколько ограничений-равенств в прямой задаче ЛП, если все переменные двойственной задачи неотрицательны.

Ограничений – равенств в прямой задаче нет.

49. Известен план прямой задачи и план двойственной задачи. Что можно сказать о разрешимости этих задач; аргументируйте ответ.

По первой теореме двойственности если одна из пары двойственных задач разрешима, то разрешима и другая (имеет оптимальный план). Причем если Х* - оптимальный план , Y* - оптимальный план => C(X*)=B(Y*)

50. Пусть Х – план прямой задачи, а У – план двойственной задачи. Что следует из равенства С(Х) = В(Y)?

Эти планы – оптимальны по лемме 2 о признаке оптимальности планов прямой и двойственной задачи.

51. Пусть выполняется равенство С(Х) = В(Y), причем известно, что Х – неоптимальный план прямо задачи; что можно сказать о векторе Y?

Такая ситуация невозможна по теореме об оптимальных планах.

52. Сформулируйте первую теорему двойственности (теорему разрешимости).

Если одна из задач дв. пары разрешима, то др. задача разрешима, причем значение целевых функций на оптимальных планах прямой и двойственной задач совпадают, если Х* - оптимальный план (1), Y* - оптимальный план (2), то С(Х*)=b(Y*).

Если С(х) одной из пары двойственных задач неограниченна на Д, то Д другой задачи – пусто.

Док-во: Пусть D₂. Тогда существует по крайней мере один план yD₂. Возьмём любой план xD₁. На основании Леммы 1: , следовательно ц.ф. C(x) – ограничена, а по условию теоремы , ч.т.д.

53. Сформулируйте теорему о планах двойственных задач.

D₁ – допустимое мн-во (1), D₂ - допустимое мн-во (2)

Если X D₁, Y D₂ => C(X)<В(Y).

Док-во: _, ч.т.д.

54. Сформулируйте признак оптимальности планов прямой и двойственной ЗЛП.

Пусть x^* - БДП ЗЛП (1), а y^* - БДП ЗЛП (2). . Если , то x^* - оптимальный план ЗЛП (1), y^* - оптимальный план ЗЛП (2).

Док-во: Возьмём любой . По Лемме 1: . Значит, для любого выполняется условие , следовательно, по определению x^* - оптимальный план ЗЛП (1), ч.т.д.

55. Приведите формулировку теоремы равновесия.

Чтобы допустимые планы задач (1) и (2) были оптимальны необходимо и достаточно, чтобы выполнялись следующие соотношения:

Док-во:

1) Пусть x^* - оптимальный план ЗЛП (1), y^* - оптимальный план ЗЛП (2)

Воспользуемся . Т.к. x* - оптимальный план ЗЛП (1), то он допустимый и ; т.к. y^* - оптимальный план ЗЛП (2), то выполняется неравенство . Отсюда:

Значит:

Рассмотрим (3): распишем скалярное произведение

Сумма произведений неотр чисел равна 0 только тогда, когда каждое слагаемое равно 0. Для (3) имеем: . Аналогично для (4).

2) Пусть

Просуммируем (1) по j: , а (2) по i: . В векторной форме: . Приравняем и воспользуемся свойствами векторов:

Т.к. , то , т.е. . На основании Леммы 2 x^* - оптимальный план ЗЛП (1), а y^* - оптимальный план ЗЛП (2), ч.т.д.

56. Дайте экономическую интерпретацию равенства Х(А^т Y– С) = 0

Если X_j>0, то А^т Y= С_j, если j-ый тех-ий способ исп-ся в произ-ве, то «цены» на ресурсы ( ) д.б. такими, чтобы суммарная стоим-ть ресурсов, идущих на изгот-ние 1 шт продукции, производимой j-ым тех-им способом, была равна С_j-ой стоим 1 шт созданного этим способом продукта. Для остальных способов, не вошедших в опт-ый план, никаких требований к «ценам» не предъявляется.

Если А^т Y> С_j, то X_j=0. В этом случае стоимостные оценки ресурсов таковы, что суммарные затраты на произ-во 1 шт продукции j-ым тех-им способом строго больше стоимости продукта, созданного этим способом. Естественно, что этот способ не используется в производстве, он неэффективен и не входит в опт-ый план.

57. Дайте экономическую интерпретацию равенства У (b – AX) = 0, входящего в формулировку теоремы равновесия.

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

Если , то , следовательно. Если в опт-ом плане i-ый ресурс исп-ся не полностью, то стоим оценка («цена») такого ресурса равна 0.