Как найти базис двойственный к данному

Как найти базис двойственный к данному

  1. Пусть (е1, е2, е3) – некоторый базис трёхмерного векторного пространства V, a (є1, є2, є3) – двойственный ему базис пространства V:
    (а) Найдите базис пространства V     (то есть выразите через є1, є2, є3), двойственный
    к базису (3e1 + e2 – 2e3, 2e1 + e3, e1) пространства V.
    (6) Найдите базис пространства V (то есть выразите через е1, е2, е3), для которого двойственным является базис (є3, 2є1 + є3, 3є1 + є2 – 2є3) пространсва V*.

@Kuchizu: используйте определение двойственного базиса. Для того, что надо найти, введите обозначения. Запишите условия, которые при этом возникают. Такие задачи обычно решаются сами, если начать что-то делать.

Источник

Пусть $V$ — векторное пространство над полем $F$.

Определение 1. Двойственным векторным пространством1) к $V$ называется векторное пространство линейных функционалов $textrm{Hom}_F(V,F)$2), то есть множество линейных функционалов $varphicolon Vrightarrow F$, с операциями сложения и умножения на скаляр, определенными формулами:

  1. $(varphi_1+varphi_2)(v)=varphi_1(v)+varphi_2(v)$ для всех $vin V$;

  2. $(alphavarphi)(v)=alpha(varphi(v))$ для всех $vin V$.

Двойственное пространство к пространству $ V $ обозначают через $V^*$. Таким образом, $V^*=textrm{Hom}_F(V,F)$.

Замечание 1. Отображение $V^*times Vrightarrow F$ такое, что $(varphi,v)=varphi(v)$ для всех $varphiin V^*$ и $vin V$ является спариванием между $V^*$ и $V$.

Предложение 1. Пусть $ V $ — векторное пространство размерности $ n $ с базисом ${e_1,ldots,e_n}$. Тогда линейные функционалы $e^1,e^2,ldots,e^n$, определенные соотношением

$e^i(e_j)=delta_{ij}=begin{cases}1,quad i=j\0,quad ineq jend{cases}$,

образуют базис $V^*$.

Определение 2. Базис ${e^1,ldots,e^n}$ пространства $V^*$, указанный в формулировке предложения 1, называется двойственным3) к базису ${e_1,ldots,e_n}$ пространства $ V $.

Источник

РАЗДЕЛ 5

Двойственное пространство. Сопряженный оператор

Пусть X – линейное пространство (вещественное или комплексное). Предположим, что в пространстве X выбран некоторый базис e = fe1; : : : ; eng. Рассмотрим произвольные линейный функционал f 2 L(X; C) и вектор x 2 X, x = x1e+ + xnen. Значение функционала f на векторе x равно

f(x) = f(x1e1 + + xnen) = x1f(e1) + + xnf(en):

При этом набор чисел f’1 := f(e1); : : : ; ‘n := f(en)g однозначно определяет линейный функционал f. Эти числа ‘1; : : : ; ‘n называются коэффициентами линейного функционала (линейной формы) в базисе e.

Выясним, как коэффициенты (‘1; : : : ; ‘n) линейного функционала f меняются при переходе от одного базиса к другому. Пусть переход от базиса e = fe1; : : : ; eng в котором f (‘1; : : : ; ‘n) к базису e0 = fe01; : : : ; e0ng осуществляется при помощи матрицы перехода S = ( jk). Тогда при j = 1; : : : ; n

‘j0 := f(ej0 ) = f

n

rjer

n

n

rj‘r:

r=1

= r=1

rjf(ej) = r=1

X

X

X

Из этого следует, что если обозначить через (f)e строку коэффициентов линейной формы f в базисе e, то

(f)e0 = (f)eS:

5.1. Двойственное пространство и двойственный базис

Рассмотрим линейное пространство X = L(X; C) всех линейных функционалов на линейном пространстве X. Напомним, что если f; g 2 X , а ; 2 C, то отображение ( f + g) : X ! C определяется соотношением ( f + g)(x) = f(x) + g(x), x 2 X.

Определение. Линейное пространство X называется двойственным (сопряженным или дуальным) пространством к пространству X.

Как было показано выше, при заданном базисе e = fe1; : : : ; eng пространства X имеет место взаимно однозначное соответствие : f 7!(‘1; : : : ; ‘n) между линейными функционалами на X и вектор-строками из n элементов. Заметим, что из правил сложения функционалов и умножения функционалов на числа вытекают следующие свойства этого отображения. Пусть f; g 2 X и пусть (f)e = (‘1; : : : ; ‘n), а

(g)e = ( 1; : : : ; n). Тогда

(f + g)e = (‘1 + 1; : : : ; ‘n + n);

а для любого 2 C имеет место

( f)e = ( ‘1; : : : ; ‘n):

Из полученный равенств вытекает, что отображение задает изоморфизм линейных пространств X и Cn (рассматриваемого как пространство вектор-строк) и, следовательно, dim X = dim X = n.

Рассмотрим набор вектор-строк j = ( j;1; : : : ; j;n) при j = 1; : : : ; n такой, что

j;k =

0;

j 6= k

1;

j = k;

56

5.1. ДВОЙСТВЕННОЕ ПРОСТРАНСТВО И ДВОЙСТВЕННЫЙ БАЗИС

57

и введем набор линейных функционалов e1; : : : ; en определенных в базисе fe1; : : : ; eng этими координатными строками. Непосредственное вычисление показывает, что для этих функционалов верны соотношения

ej(ek) = jk;

где jk – символ Кронекера. При этом для любого вектора x = x1e1 + + xnen имеем

nn

XX

ej(x) = xkej(ek) =

xk j;k = xj:

k=1

k=1

Так как вектор-строки j, j = 1; : : : ; n линейно независимы, то и функционалы ej, j = 1; : : : ; n, рассматриваемые как элементы пространства X , будут линейно независимыми. Таким образом нами установлено следующее утверждение.

Теорема 5.1. Пусть X – n-мерное линейное пространство (n 2 N). Тогда двойственное пространство X также имеет размерность n. Если e = fe1; : : : ; eng – ба-

зис в X, а e1; : : : ; en – такие линейные функционалы, что ej(ek) = jk, то fe1; : : : ; eng

– базис в X .

Определение. Базис fe1; : : : ; eng пространства X (см. формулировку теоремы 5.1) называется двойственным (дуальным или сопряженным) базисом для данного базиса fe1; : : : ; eng пространства X.

Выясним смысл “двойственности”, содержащейся в понятии двойственного базиса. Во-первых заметим, что между базисами в X и X установлено взаимно-однозначное соответствие (которое каждому базису ставит с соответствие соответствующий сопряженный базис). Во вторых заметим, что выражение f(x), где f 2 X , а x 2 X, допускает двоякую трактовку. При фиксированном f – это линейный функционал на X, а при фиксированном x – линейный функционал на X . Отталкиваясь от этого, запишем выражение f(x) – значение функционала f на векторе x в виде hfjxi, смысл этой записи будет ясен чуть позднее. Символ “вертикальной черты” применяется для того, чтобы отличить эту запись от скалярного произведения векторов так как в выражении h j i первым аргументом должен быть линейный функционал (т.е. элемент множества X ), а вторым аргументом – элемент x 2 X. Заметим, что выражение h j i определяет отображение X X ! C, линейное по каждому аргументу, т.е.

h f + gjxi = hfjxi + hgjxi; hfj x + yi = hfjxi + hfjyi

(5.1)

при всех f; g 2 X , x; y 2 X, ; 2 C.

Определение. Пусть V и W – линейные пространства. Отображение декартова произведения V W = f(v; w) : v 2 V; w 2 Wg в C (или в R), линейное по каждому из двух своих аргументов называют спариванием (происходит от английского слова paring) между пространствами V и W.

Спаривание между X и X определенное соотношением hfjxi := f(x), f 2 X ,

x 2 X называется каноническим.

Разложим теперь произвольные элементы f

2 X

и x

2 X

по двойственным базисам

fe1; : : : ; eng и fe1; : : : ; eng соответственно:

Тогда

f = ‘1e1 + + ‘nen;

x = x1e1 + + xnen:

n

n

n

n

n

n

X

X X

XXk

X

f(x) =

‘jej(x) = ‘j

xkej(ek) =

xk‘jej(ek) =

xj‘j:

j=1

j=1

k=1

j=1

=1

j=1

Заметим также, что координаты (‘1; : : : ; ‘n) линейного функционала f 2 X в базисе fe1; : : : ; eng и координаты (x1; : : : ; xn) вектора x 2 X в базисе fe1; : : : ; eng, сопряженном

5.2. СЛУЧАЙ ЭРМИТОВА ПРОСТРАНСТВА

58

к fe1; : : : ; eng, могут быть вычислены по формулам

xk := hekjxi

и

‘k := hfjeki

(5.2)

соответственно. В самом деле,

hekjxi =

ek

n

n

j=1 xjej

= j=1 xjhekjeji = xk;

X

X

n

n

hfjeki =

j

ek

j

j=1 ‘je

= j=1 ‘jhe jeki = ‘k:

X

X

Формулы (5.2) также можно рассматривать как проявление свойства двойственности базисов fe1; : : : ; eng и fe1; : : : ; eng.

Пример 5.2. Пусть n = Spanf1; t; : : : ; tng – пространство многочленов степени, не выше n. Отображение f : P 7!P ( ), ставящее многочлену P 2 n его значение в точке 2 R является, очевидно, линейным функционалом на пространстве n. Можно показать, что совокупность функционалов f при 2 f 0; : : : ; ng, где 0; : : : ; n – различные точки из R, является линейно независимой. Следовательно, она является

базисом в n.

Другой пример базиса в n можно получить рассмотрев семейство линейных функционалов fk : P 7!aP (k)( ), где a 2 R и 2 R – некоторые фиксированные параметры, а k = 0; 1; : : : ; n. Проверка линейной независимости функционалов fk оставляется в качестве несложного упражнения.

Можно проверить, что набор функционалов fk0 : P 7!P (k)(0)=k! образует базис в

n, двойственный к базису f1; t; : : : ; tng в n, а набор функционалов fk : P 7!P (k)( )=k! при k = 0; 1; : : : ; n образует базис в n, двойственный к базису f1; (t ); : : : ; (t )ng в пространстве n.

5.2.Случай эрмитова пространства

Вэтом разделе X – n-мерное эрмитово пространство с (эрмитовым) скалярным произведением h ; i. Рассмотрим сопряженное пространство X . Так как dim X = n и dim X = n, то X и X изоморфны как линейные пространства.

Построим специальный изоморфизм между X и X следующим образом: элементу x 2 X поставим в соответствие линейный функционал f 2 X такой, что f(y) = hy; xi (напомним, что в силу Теоремы 4.17 функционал f определяется таким вектором x единственным образом). Этот изоморфизм естественно назвать каноническим (или естественным) изоморфизмом между X и X .

Пусть fe1; : : : ; eng – ортонормированный базис в X, т.е. скалярные произведения базисных векторов равны hej; eki = jk. В этом случае линейные функционалы ej( ) = h ; eji, j = 1; : : : ; n, определяемые векторами базиса fe1; : : : ; eng, будут образовывать базис, двойственный к базису fe1; : : : ; eng. В самом деле, ej(ek) = hek; eji = kj. Для построенного базиса fe1; : : : ; eng будет использоваться обозначение be, где e = fe1; : : : ; eng

– исходный ортонормированный базис.

Далее, для произвольного вектора x 2 X определим вектор x следующим образом: если (x1; : : : ; xn)> – координатный столбец вектора x в рассматриваемом (ортонормированном базисе), то вектор x = x1e1 + xnen (черта, как обычно, означает комплексное сопряжение). Таким образом, если X – вещественное пространство, то векторы x и x совпадают.

Напомним, что каноническим спариванием между пространствами X и X является спаривание hfjxi = f(x). Из доказательства Теоремы 4.17 вытекает, что оно задается формулой

hfjxi = hx; fi;

5.3. РЕФЛЕКСИВНОСТЬ

59

где

f

2 X

,

x

2 X, а

f

2 X – такой вектор, что его координаты

относительно базиса

1

n

g.

fe1; : : : ; eng совпадают с координатами элемента f относительно базиса fe

; : : : ; e

5.3. Рефлексивность

Напомним, что если dim X = n, то dim X = n. Следовательно, на основании теоремы об изоморфизме конечномерных линейных пространств одинаковой размерности, пространства X и X изоморфны. В силу аналогичных соображений изоморфными будут также пространства X и X = (X ) . На первый взгляд кажется, что пространство X – это пространство весьма экзотической природы. В самом деле, оно состоит из линейных функционалов на пространстве линейных функционалов на X. Но, как оказывается, между пространствами X и X существует весьма простая и естественная связь. Эта связь устанавливается следующей теоремой.

Теорема 5.3. Отображение ” : X ! X , определяемое следующим образом

“(x) = “x; “x(f) = f(x);

x 2 X; f 2 X ; “x 2 X ;

является изоморфизмом. Оно называется каноническим (или естественным) изоморфизмом между пространствами X и X .

Доказательство. Линейность ” проверяется непосредственно исходя из его определения. В самом деле, если x; y 2 X, а ; 2 C, то для любого линейного функционала f 2 X имеет место цепочка равенств

” x+ y(f) = f( x + y) = f(x) + f(y) = “x(f) + “y(f) = ( “x + “y)(f):

Проверим теперь биективность отображения “. Выберем в пространствах X и X двойственные базисы fe1; : : : ; eng и fe1; : : : ; eng соответственно. Тогда

“ej (ek) = ek(ej) = kj:

Используя рассуждения, аналогичные приведенным при доказательстве теоремы 5.1 получим, что X = Spanf”e1 ; : : : ; “en g, т.е. набор элементов f”e1 ; : : : ; “en g образует ба-

зис в X , двойственный к базису fe1; : : : ; eng в пространстве X . Из этого вытекает как сюръективность, так и инъективность отображения “.

Замечание. Построенный в Теореме 5.3 изоморфизм ” назван естественным (каноническим) в силу того, что он не зависит от выбора конкретного базиса.

Определение. Свойство линейный пространств, состоящее в том, что между пространствами X и X существует естественный изоморфизм носит название

рефлексивность.

Замечание. Как было установлено в этом разделе, конечномерные линейные пространства рефлексивны. Однако это, в общем случае, не так для бесконечномерных пространств. Соответствующие примеры будут изучены в курсе функционального анализа.

Рефлексивность позволяет отождествить пространства X и X . При этом уже пространство X можно понимать как пространство линейных функционалов на X . При таком понимании формулы спаривания приобретают симметричный вид x(f) = hfjxi = f(x), где в первом равенстве элемент x рассматривается как элемент X , а в последнем – как элемент X.

Из теоремы 5.1 вытекает следующее утверждение.

Следствие 5.4. Если пространство X рефлексивно, то для любого базиса в X существует однозначно определенный двойственный ему базис в X.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
Источник

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

Время на прочтение
9 мин

Количество просмотров 27K

Прочие статьи цикла

Обычно с задачей линейного программирования (ЗЛП) связана другая линейная задача, называемая двойственной. Обе эти задачи можно считать двойственными одну по отношению к другой, считать равносильными. Первая задача называется обычно исходной, или прямой, другая – обратной. Переменные, используемые в двойственной задаче называются двойственными или множителями Лагранжа. На них не накладывается ограничений по знаку. Рассматриваются двойственные критерии оптимальности. Специальные случаи называют симметричными двойственными задачами линейного программирования. Связь между оптимальными решениями двойственных задач устанавливается теоремой двойственности.

Теорема двойственности

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

Теорема двойственности

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

Теорема существования решения

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

Теорема (принцип) дополняющей нежесткости

  1. Если (xQ , xL) – оптимальное решение прямой задачи, а (yQ, yL) – решение двойственной задачи, то (xQ , xL, yQ , yL) – решение задачи Лагранжа. В частности, в этом случае удовлетворяются соотношения между переменными прямой и двойственной задач и условия дополняющей нежесткости.

  2. Оптимальное решение прямой задачи программирования получается только при одном значении xQ. Это справедливо и для переменной yQ в двойственной задаче.

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

Основное неравенство двойственности. Для любых допустимых решений Х<n> и Y<n>пары двойственных ЗЛП имеет место неравенство

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

Теорема существования (малая тероема двойственности)

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

Теорема 1 двойственности.

Если одна из пары двойственных задач имеет opt решение, то и другая его имеет. Причем экспериментальные решения их целевых ф. равны; если же ЦФ одной из задач не ограничена, то система ограничений другой противоречива. Интерпретация: оптимальное использование ресурсов – opt план. Суммарная оценка ресурсов = оценке продукта полученного при opt плане. Любой другой план не рентабелен. Cj – стоимость единицы продукции (внешняя оценка) yi – стоимость единицы ресурса (внутренняя оценка). Эти двойственные оценки выступают как инструменты балансирования затрат и результатов. Имеет место xj ​<->​ ym +j ; xn+i <-> yi.

Теорема 2 двойственности (о дополняющей нежесткости)

Для того, чтобы допустимые решения X и Y пары двойственных задач были оптимальными, необходимо и достаточно выполнить условия:

То есть, если какое-либо ограничение одной ЗЛП обращается ее opt планом в строгое равенство, то соответствующая переменная двойственной задачи в ее opt плане равна нулю; если же какая-либо переменная opt-го решения одной ЗЛП положительна, то соответствующее ограничение в двойственной ЗЛП ее opt планом обращается в точное равенство.

Теорема Кёнига хорошо иллюстрирует использование принципа двойственности ЗЛП.

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

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

Минимальное число линий, покрывающих все единицы матрицы [Cij], найдем, решив линейную задачу:

Оптимальному решению (u*i, v*j)  последней задачи отвечает минимальное покрытие, состоящее из множества строк I,  для которых u*i = 1  и столбцов J, для которых u*j =1.

Матрицы  А и АТ коэффициентов (*), (**), (***) являются абсолютно унимодулярными, как матрицы двудольного графа. Поэтому условия целочисленности переменных заменяем  на условие их неотрицательности, и тогда получаем пару двойственных задач линейного программирования и согласно теореме двойственности имеем:

Линией матрицы называется ее строка или столбец. Два элемента матрицы называются неколлинеарными, если они не лежат на одной линии.

Матрица называется абсолютно унимодулярной, если все ее ненулевые миноры равны 1, либо -1.

Следствие. Матрица инциденций неориентированного графа G абсолютно унимодулярна тогда и только тогда, когда G – двудольный граф. В двудольном графе все простые циклы имеют четкую длину                                  

Принцип двойственности в задачах линейного программирования.

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

С этой целью руководство должно назначить стоимости yi за единицу сырья вида Si, стремясь при этом минимизировать общую стоимость сырья (чтобы быстрее продать сырье): Ф = Σ4i=1 biyi

Выручка предприятия от продажи сырья, расходуемого на единицу продукции Пi, составит: Σ4i=1 aij yi

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

Сформулируем исходную и двойственную задачи:

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

  1. Если первая задача сформулирована на поиск максимума, то вторая формулируется на поиск минимума линейной функции.

  2. Коэффициенты ЦФ первой задачи являются свободными членами системы ограничений второй.

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

  4. Матрица коэффициентов второй задачи является транспонированной к матрице коэффициентов ограничений первой задачи.

  5. Знаки неравенств в ограничениях второй задачи противоположны знакам неравенств в ограничениях первой задачи.

Оптимальный план Xopt<n> одной из задач тесно связан с оптимальным планом Yopt<n> другой. Если одна из задач имеет решение, то другая также разрешена, причем для оптимальных клонов Xopt<n> =<x1, x2,…xn> и Yopt<m> =<y1, y2,…ym> справедливо равенство Q( Xopt ) =Q’( Yopt ). Если линейная форма одной из задач неограниченна, то условия другой задачи несовместны. Если A-1 обратная матрица к матрице В, состоящей из векторов базиса оптимального плана исходной задачи, то оптимальный план двойственной задачи равен Yopt<m> =СВ -1, здесь С – вектор базисных переменных. Решение двойственной задачи получается в последней симплексной таблице исходной задачи, в (m+1) строке, в столбцах, соответствующих дополнительным параметрам.

Для того чтобы векторы Xopt<n> =<x1, x2,…xn> и Yopt<m> =<y1, y2,…ym> были решениями пары задач, необходимо и достаточно, чтобы их компоненты удовлетворяли следующим условиям:

Эти условия называют принципом дополняющей нежесткости. Если исходная (прямая) задача задана в канонической форме, то двойственная к ней называется несимметричной. Для несимметричной двойственной задачи соблюдается условие yi  ≥ 0.

Теория ЗЛП доказывает, что компоненты оптимальных планов взаимно двойственных задач, приведенных к каноническому виду, соответствуют одни другим. То есть базисные переменные основной задачи соответствуют свободным переменным двойственной задачи и наоборот, j = 1(1)n, x*j ​ y*m +j ; x*n+i ​ y*i ; i = 1(1)m.

Размерности в табличке m и n берутся в задаче для y-ков записанной в канонической форме.

Пример. Двойственный симплекс метод.  

Исходная задача. Имеется три вида продуктов Пj, причем единица веса каждого из видов продуктов содержит aij  единиц (питательных веществ). Для нормальной жизнедеятельности человек должен потреблять не менее bi единиц вещества Bi в сутки. Стоимость единицы продукта Пj равняется Cj. Требуется составить оптимальный суточный рацион питания, т.е. найти количество xj продукта, которое должен потреблять человек, чтобы стоимость питания была бы минимальной, если известно, что

такие значения его компонентов xj,  j = 1(1)3, которые минимизируют целевую функцию (Ц) Q = 3x1 + 2x2 + x3 и удовлетворяют ограничениям неравенствам

0,3x1 + 0,2x2 + 0, 4x3  ≥ 0,2;

0,4x1 + 0,3x2 + 0,45x3  ≥ 0,5;

0,2x1 + 0,3x2  + 0, 1 x3  ≥ 0,6;

0,1x1 + 0,2x2 + 0,05x3  ≥ 0,1;

xj ≥ 0; j = 1(1)3 = n

Для приведения задачи к каноническому виду введем дополнительные переменные x4, x5, x6, x7, переменных стало больше чем уравнений n – m = 7 – 4 = 3, следовательно, части из них (трем любым,) для получения решения можно задать произвольные значения (задают, как правило, нулевые значения), возникает число сочетаний из n по m вариантов. Система ограничений примет вид равенств

0,3x1 + 0,2x2 + 0,4x3 – x4 = 0,2;

0,4x1 + 0,3x2 + 0,45x3     – x5 = 0,5;

0,2x1 + 0,3x2 + 0,1x3                     – x6 = 0, 6;                   

0,1x1 + 0,2x2 + 0,05x3                             – x7 = 0, 1;

xj ≥ 0; j = 1(1)3 = n, i = 1(1)4 = m.

Назначаем опорный план. Выбор в качестве базисных переменных x4, x5, x6, x7 приводит к недопустимому опорному плану. Так как знаки левой и правой частей различны. (Свободные переменные x1 = x2 = x3 = 0) Метод искусственного базиса приводит к увеличению числа неизвестных задач, что нежелательно. Анализ задачи показывает, что число уравнений в системе ограничений больше числа переменных. Поэтому попытаемся применить принцип двойственности, т.е. вначале решим двойственную ЗЛП, а затем найдем решение исходной.

Двойственная задача. Коэффициентами линейной формы в двойственной задаче выступают правые части bi , i = 1(1)4 = m, исходной основной задачи. Переменные получают другие имена y1, y2, y3, y4, и формулируется двойственная задача иначе. Найти максимум линейной формы Q’:

Q’=0,2y1 + 0,5y2 + 0,6y3  + 0,1y4;

при ограничениях

0,3y1 + 0, 4y2 + 0,2y3 + 0,1y4  ≤ 3;

0,2y1 + 0, 3y2  + 0,3y3 + 0,2y4  ≤ 2;   

0,4y1 + 0,45y2 + 0,1y3 + 0,05y4 ≤ 1;

yi ≥ 0; i = 1(1)4.

Приведем задачу к каноническому виду, вводим дополнительные неотрицательные переменные y5 , y6 , y7 : 

Найти минимум ЦФ (знаки у коэффициентов ЦФ поменяли на противоположные): Q’= – 0,2y1 – 0,5y2 – 0, 6y3  – 0,1y4;

при ограничениях (в ограничения добавили новые переменные):

 0,3y1 + 0, 4y2 + 0,2y3 + 0, 1y4 + y5 = 3;

0,2y1 + 0, 3y2 + 0,3y3 + 0, 2y4 + y6 = 2;

0,4y1 + 0,45y2 + 0,1y3 + 0,05y4           + y7 = 1,

yi ≥ 0; i = 1(1)7.

Задача решается симплекс методом. Исходный опорный план в качестве переменных может иметь y5, y6, y7 и свободные переменные y1 = y2 = y3 = y4 = 0, т.е. Y<7> = [0, 0, 0, 0, 3, 2, 1] .

Базисные переменные y5, y6, y7 и ЦФ выражаем через свободные переменные, т.е. из свободных членов (правых частей, обозначенных γi )  вычитаем левые части ограничений

y5 = 3 – (0,3y1 + 0,4y2 + 0,2y3 + 0,1y4);

y6 = 2 – (0,2y1 + 0,3y2 + 0,3y3 + 0,2y4);

y7 = 1 – (0,4y1 + 0,45y2 + 0,1y3 + 0,05y6);

Q’1=γ0 – Σ4i=1 γi yi = 0 -(0,2y1 + 0,5y2 + 0, 6y3  + 0,1y4);

γ0 =0, так как ЦФ не содержит свободного члена.

и строим симплекс таблицу с двумя полуклетками. Направляющий столбец y3, направляющая строка y6.

Анализ таблицы показывает, что все коэффициенты ЦФ при свободных переменных положительны. Следовательно, план Y<7> не является оптимальным, ЦФ можно уменьшить, увеличивая значения соответствующих свободных переменных.

Находим γ = max{γi} =max {0,2; 0,5; 0,6; 0,1} = 0,6. Переменную y3 надо ввести в базис. После этого устанавливаем, существует ли оптимальный план. В направляющем столбце все коэффициенты положительны, следовательно, оптимальный план существует. В базисе есть переменные, которые можно уменьшать до нуля увеличивая значения y3, тем самым минимизируя ЦФ. Раньше других в нуль обратиться переменная y6 и ее исключаем из базиса.

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

Анализ этой таблицы показывает, что все коэффициенты в выражении ЦФ свободных переменных отрицательны. Следовательно, опорный план Y<7>= [0, 0, 20/3, 0, 5/3, 0, 1/3] является оптимальным. ЦФ при этом Q’1 = – 4  достигла наименьшего значения. Возвращаемся к двойственной задаче. Используя соответствие между оптимальными планами двойственных задач ЛП, определяем: базисными переменными в оптимальном плане будут x2 x4 x5 x7; их значения с противоположным знаком записаны в последней строке таблицы. Таким образом, Xopt<n> =<0; 2; 0; 0; 2; 0; 1; 0; 1/30>, т.е. оптимальный рацион из двух единиц продукта П2. Стоимость такого рациона минимальна и составляет 4 единицы. Это значение с противоположным знаком записано в той же таблице.

Литература

  1. Ваулин А. Е. Методы цифровой обработки данных.– СПб.: ВИККИ им. А. Ф. Можайского, 1993.– 106 с.

  2. Гэри М., Джонсон Д. Вычислительные машины и трудно решаемые задачи. М.: Мир, 1982.

  3. Квейд Э. Методы системного анализа // Новое в теории и практике управления производством в США.–М.: Прогресс, 1971.– с.78-99. .

  4. Корбут А.А., Финкельштейн Ю. Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.

  5. Макаров И. М. и др. Теория выбора и принятия решений.– М.: Наука, 1982.– 328 с.

  6. Пфанцагль  И. Теория измерений. – М.: Наука, 1988.–384 с.

  7. Таха Х. А. Введение в исследование операций. 7-е изд. М.: Изд. дом «Вильямс», 2005.

  8.  Фишберн П. С. Теория полезности для принятия решений. – М.: Наука,1978. –352 с.

Источник

Добавить комментарий