Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 12
Текст из файла (страница 12)
Обозначим сзВ ' = л = (лы ..., л ) = с*. Можно считать, что л; является ценой, которую мы платим за единицу г-го продукта на первом производстве. Пусть аз — любой небазисный вектор, представляющий )-й технологический процесс на первом производстве. При единичной интенсивности использования у-м процессом производится ам единиц гхго продукта (г = 1,..., т). Поскольку в рассматриваемой системе каждая единица г-го вещества стоит л; денежных единиц, стоимость продукта, производящегося технологическим процессом агэ составит лар Обозначим лаз через згь Реальные эксплуатационные расходы иго процесса составляют ср Таким образом, если сг — зг = сг — лаз.-. О, то данный процесс использовать не следует.
Если с~ — зг г" О, то использование процесса аз принесет некоторую зкономию. После того как вместо некоторого базисного вектора в базис вводится аг с максимально большой возможной интенсивностью, появляются новые цены л, отличные от старых л. Отсюда л, называется теневой ценой г-й строки относительно данного базиса. Вычисление сг — лаз в литературе называется операцией оценивании. Операция оценивания служит для выяснения, должен ли быть введен вектор аз в базис.
Заметим, что базис В является оптимальным, если В гЬ ) О и сг — свВ 'аг ) О для всех 1. Пусть Ь получит небольшое приращение АЬ, так чтобы В '(Ь + АЬ) ~ )О. Тогда сз = сг— — сзВ 'аг не изменится. Отсюда следует, что базис В останется оптимальным базисом н для новой правой части Ь + АЬ.
Поскольку л = сзВ ', л также не изменится. Но в з 2.4 было показано, что з = '~ л;Ь;, т. е. новое оптимальное значение целевой функции г= 1 имеет вид з'= ~~ л; (Ь; — АЬ|)= в+ ~ л; АЬн ~=1 1=1 Гл. г. скмплвкс-метод откуда Таким образом, кзпоказывает, как изменяется х в зависимости от изменения Ьо В задаче 1 з 1.1, если ограничение по й-му нита- тельному веществу Ьз увеличится на единицу, а все остальные ограничения останутся без изменений, то минимальная общая стоимость рациона увеличится на л„.
Подобным же образом, если Ьз уменшпится на единицу, а все остальные ограничения останутся без изменений, то минимальная общая стоимость рациона уменьшится на нд. Упражнения 1. Дана линейная программа: минимизировать х = бхг + Зх, + х, + 7х, + Зхз прн условиях х,+2х,+7х, =9, Ьхг -',- Зхз + хз — х, = 9, х )~0 () =1, ...,5).
Найдите четыре вектора, являющихся соответственно: а) допусти- мым решением; б) базисным недопустимым решением; в) базисным допустимым решением; г) базисным оптимальным решением. Для получения использовать симплекс-метод. 3. Рассмотрим задачу: минимизировать з = 10 — 2х, — Зхз при условиях хг — хз1-хз Зхз= 3 хг+хз '. з хзт2хз= 2 х, ~0 (у' = 1, ..., 5). Используйте х, и х, в качестве начальных базисных переменных, а для введения в базис всегда выбирайте лексикографически минимальный столбец.
Проверяйте ваши вычисления на каждом шаге 2. Какой вид должны иметь относительные оценки при небазисных переменных, чтобы оптимальное решение было единственным? Какой вид они будут иметь в случае существования других оптимальных решений? дополнвнив значением величины г = лЬ. (Указание. При вычислении г = яЬ константа 10 не учитывается.) 4. Приведите пример линейной программы, для которой в оптимальном решении слабые переменные принимают ненулевое значение. 5.
Дайте математическое обоснование двух следующих утверждений. а) Если некоторый процесс «абсолютно невыгоден» в терминах теневых цен, то интенсивность использования данного процесса должна быть нулевой. б) Если некоторый ресурс использован не полностью, то теневая цена, соответствующая данному ресурсу, должна быть нулевой.
6. Рассмотрим задачу: найти минимум г =11 — х» — х, — х» при условиях х, + х» — х, + 2х» =. 2, хг — х»+ 2х«+ х» = 1 х~ ) 0 (/ = 1„..., 5). Пусть х~ и х» — исходные базисные неременпые. Выберите среди всех возможных векторов — кандидатов для ввода в базис, такой, с введением в базис которого целевая функция больше всего уменьшится. Объясните правило выбора таких векторов, используя см ам и ~,. Дополнение Использование критерия ввода в базис столбца с минимальной отрицательной относительной оценкой аналогично методу наискорейшего спуска. При таком критерии процесс обычно сходится быстрее, чем при использовании других возможпых критериев.
Однако можно построить такой пример, что использование минимальной отрицательной оценки с; привело бы к перебору всех вершин многогранника. ГЛАВА 3 ДВОЙСТВЕННОСТЬ 3,1. Теорема двойственности (Гейл, Кун, Таккер (71!) Двойственная задача: максимизировать ю=~ уЬ; 1=1 при условиях Прямая задача: минимизировать и з= ~~ с~хт э=1 при условиях 4 а;;хт)Ьь э=1 п 2. 1 , а;;х;=Ьп э=1 16 М~ у,)О, 16 М1 у; О, У у;а;;(с;, г=1 / ЕА~~ хз) О, 1 у;ам= с,.
16% х -'О, т( Б предыдущих главах были изучены вопросы существования неотрицательных решений системы линейных уравнений и неравенств и геометрический смысл базисных решений. В этой главе будет рассмотрен еще один аспект задач линейного программирования. Оказывается, с каждой задачей линейного программирования можно сопоставить другую задачу линейного программирования, связанную с исходной рядом интересных соотношений. Будем называть первую задачу прямой задачей линейного программирования, а вторую — двойственной. Для того чтобы сделать взаимосвязь задач более попятной, вводятся следующие множества индексов: М=(1, ...,то ...,т1, М,=(1, ...,тД, М,=(т,+1, ..., т); Ф=(1, ...,и,, ...,п1, Ф,=:(1, ...,п~, У~=(п,+1, ...„п1.
Например, запись 1 ~ Ф, означает, что 1 =- 1,..., и,. Запишем обе задачи рядом, а между ними поместим множества индексов, относящихся к соответствующей строке как первой, так и второй задачи: 3.1. Теогемл дВОйстВеннОсти 72 Симметричность двух задач очевидна. Неравенству в одной задаче соответствует неотрицательная неремеппая в другой. Равенству одной задачи соответствует свободная переменная другой.
Далее, задача, двойственная к двойственной задаче, есть исходная (прямая) задача. Таким образом, моцкно считать любую из такой пары задач прямой, а другую — двойственной. Если записать задачу линейного программирования в стандартном виде, то симметричность становится более очевидной. Выпишем для задач в стандартном и каноническом виде им двойственные.
Стандарп1ный вид Прямая задача минимизировать з=сх (с) Двойственная задача максимизировать ну =ЯЬ (з) при условиях при условиях Ах= Ь, НА(с, х)0. Здесь мы используем у в качестве неотрицательных переменных двойственной задачи, а перемепныо я могут быть любого знака. Стандартпу1о форму пары двойственных задач можно свести в компактную таблицу. Табаица 8.1 2 Х1 Х2 Х12 Уи+1 = хи+1 хии2 Уи ни = хи.ни при условиях Ах) Ь, х)0. Канонический вид: Прямая задача минимизировать з=сх Двойственная задача максимизировать п2=уЬ при условиях уА<с, у)0.
Гл. а. ЛВОйстВеннОсть При чтении таблицы 3.1 каждая строка таблицы умножается на вектор-столбец И, х„..., х„) и приравнивается переменной, выписанной справа от таблицы. Например, ( — Ь„а„, ..., а1„) ° [1, х„..., х„) = х„+,. Вектор-строка (1, у„+„..., у„ьы) умножается на каждый столбец таблицы и приравнивается переменной, записанной под этим столбцом. Нанример, (1, у„+ы... ум- )'[ — еа аы~ аап ., а;) = — уп Все переменные х и у подчиняются требованию неотрицательности, т.
е. хт>0 (1 =1,..., и,..., и+т), ут>0 (у =1,..., п,..., и+т). В дальнейшем для облегчения изложения будут рассмотрены задачи, заданные в стандартном виде. Лемма 3.1. Если х и у — соответствующие допустимые решения пары двойственных задач, то ох>уЬ. Доказательство. Поскольку х — допустимое решение, то Ах>~Ь.
Умножая обе части неравенства на у>0, получаемуАх) ) уЬ. Поскольку у — допустимое решение, то уА(с. Умножая обе части этого неравенства на х> О, получаем уАх сх. Танин образом, сх>~уАх>уЬ. ° Лемма 3.2. Система однородных линейных неравенств Ах — 1Ь> О, — уА+ее > О, уЬ вЂ” сх О, у>0, х>0, т>0, (1) (2) (3) имеет по крайней мере одно решение уо, ха, йи такое, что Аха — гаЬ+ Ут > О, ут — уаА+1ас+ хат > О, и хо >О. уоЪ вЂ” сха+ та О, ео (4) (5) (6) 0 А — Ь -у*- —,тАт 0 ст . х ~~~0, х [>О, Ьт — с 0 т! Доказательство.
Систему (1), (2), (3) мон но представить в матричной Форме следующим образом: гл. теОРемА дВОйстВеннОсти 73 где матрица 0 А — Ь- — Ат 0 ст является кососимметрической. По теореме 1.4 эта система обладает по крайней мере одним неотрицательным решением (ут, х, г), таким, что 0 А — Ь- — А 0 ст о х, > О, Случай 1. го>0. Полагая хв= хо у*= Уо гв= а имеем х*лО, у*>0, 1'>О. Тогда х*, у* и 1" такгке являются решением системы однородных линейных неравенств (1), (2), (3) из леммы 3.2. После подстановки решений х*, у*, с*=1 в систему имеем Ах*> Ь; у"А (с; ох*.~ у'Ь Ах' — Ь = О, — у*А+с >О, у*Ь вЂ” сх' > О, или или или а это и есть не что иное, как условия (4), (5) и (6).
Лемма доказана. Докал|ем теперь теорему двойственности (сы. (71) и (201)). Твогемл двойственности. Пусть дана пара двойственных задач линейного программирования, заданных в виде (с). Тогда справедливо одно и только одно из следующих утверждений: 1. Обе задачи имеют оптимальные решения и оптим льные значения целевых функций равны, т. е. ш1п сх = шах уЬ. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
