ПОЗНАВАТЕЛЬНОЕ

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

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

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

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

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

Основное нер-во двойственности.Пусть Х – какое-нибудь допустимое решение задачи I, а У – какое-нибудь допустимое решение задачи II. Тогда справедливо неравенство f(x)<φ(Y)

Доказательство:Имеем AX<B, откуда следует (АХ)^T<B^T или X^TA^T<B^T. Умножим обе части этого неравенства справа на матрицу У>0=0, получим (X^TA^T)Y<B^TY или, в ввиду ассоциативности умножения матриц,

X^T(A^TY)<B^TY=φ(Y) (I)

Аналогично имеем ATY>С; умножив обе части слева на матрицу XT>0, будем иметь

X^T(A^TY)>X^TC=f(X) (II)

Соединяя два полученных неравенства I и II, можем записать

F(X)<X^TA^TY< φ(Y),

откуда и следует основное неравенство f(X)< φ(Y).

Достаточный призрак опт-ти: Если для некоторых допустимых решений выполняется равенство значений целевых функций то х*, у* - оптимальные решения задачи I и II соответственно.

№ 25. Сформулируйте первую и вторую теоремы двойственности. Докажите вторую теорему двойственности.

Первая теорема двойственности. Если исходная задача имеет оптимальное решение, то и двойственная ей также имеет оптимальное решение. При этом оптимальные значения целевых функций обеих задач равны: f_max=g_min. Оптимальное решение исходной задачи можно найти по фор-ле: X=C^*D^-1

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

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

Доказательство:Пусть и – оптимальные решения пары двойственных задач. Тогда для ,

Они удовлетворяют следующим ограничениям:

. (3)

Умножим (3), соответственно, на и , и просуммируем полученные выражения:

. (4)

Из основной теоремы двойственности следует

. (5)

И с учетом (4) получаем:

, .

Первое из этих выражений можем переписать в виде ,

и так как все и выражения в скобках неотрицательны, то опуская å, получим: .

Аналогично получим: . Ч.Т.Д.

Вопрос №26. Приведите пример постановки транспортной задачи. Что такое оптимальный план перевозок? Что такое транспортная задача с правильным балансом? Сформулируйте критерий разрешимости транспортной задачи.

1) Классическая постановка транспортной задачи общего вида.
Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:
a_i – объемы производства i -го поставщика, i = 1, …, m;
в_j – спрос j-го потребителя, j= 1,…,n;
с_ij – стоимость перевозки одной единицы продукции из пункта A_i– i-го поставщика, в пункт В_j – j-го потребителя.

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

2) Оптимальный план перевозок - такой план перевозок, который определяет минимальную суммарную стоимость транспортировки, не превышая объем производства каждого из поставщиков и полностью покрывая потребности каждого из потребителей.

3) Транспортная задача с правильным балансом.

Теорема: если допустимое решение Х=(х_ij)*(i= , j= ) транспортной задачи является оптимальным, то существует потенциалы поставщиков u_i (i= ) и потребителей v_j(j= ). Удовлетворяющее условиям: 1) u_i+v_j=c_ij, если x_ij>0; 2) u_i+v_j ≤c_ij, если x_ij=0.

Общее кол-во товара у поставщиков:

Общая потребность в товаре в пунктах назначения:

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

4) Критерий разрешимости транспортной задачи:

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

№27. Опишите методы построения начального опорного плана транспортной задачи.

1) Метод северо-западного угла

2)Метод минимального тарифа

Начальный опорный план находят, заполняя не более чем m+n-1 клеток (по числу базисных переменных). Любое допустимое решение транспортной задачи можно записать в транспортную таблицу. Клетки транспортной таблицы, в которых находятся отличные от нуля (или базисные нулевые) перевозки, называются занятыми, остальные свободными. Клетки таблицы нумеруются так, что клетка, содержащая перевозку x_ij, т.е. стоящая в i-строке и j- столбце, имеет номер (i,j). Каждой клетке с номером (i,j) соответствует переменная x_ij. Выбор заполняемых клеток производят, ориентируясь на тарифы перевозок, а именно: на каждом шаге выбирают какую-нибудь клетку (i,j), отвечающую минимальному тарифу и помещают в нее максимально возможную перевозку x_ij. После чего удаляют либо столбец, либо строку в зависимости от соотношения x_ij=b_j или x_ij=a_i.

№28. Опишите метод потенциалов. Сформулируйте определения следующих понятий: свободная клетка, занятая клетка, оценка свободной клетки, цикл, перестановка по циклу. В чем состоит условие оптимальности опорного плана?

1) Метод потенциалов.

Метод потенциалов основан на следующей теореме.

Если допустимое решение Х=( x_ij) (i= , j= ) транспортной задачи является оптимальным, то существуют потенциалы поставщиков u_i(i= ) и потребителей v_j (j= ), удовлетворяющие условиям: u_i+ v_j=с_ij, если x_ij>0,

u_i+ vj<либо =с_ij, если x_ij=0. Равенства u_i+ v_j=с_ij при x_ij>0 используются для нахождения потенциалов. Данная система уравнений имеет m+n неизвестных u_i,i= и v_j, j= . Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m+n-1. Так как число неизвестных системы на единицу больше числа уравнений, то одно из них можно задать произвольно ( как правило, его берут нулевым), а остальные найти из системы.

Неравенства u_i+ vj<либо =с_ij при x_ij=0 используются для проверки оптимального опорного решения. Эти неравенства удобно записать в виде _ij=u_i+v_j-c_ij при x_ij=0.

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

2) Клетки транспортной таблицы, в которых находятся отличные от нуля(или базисные нулевые) перевозки, называются занятыми, остальные – свободными.

Оценка свободной клетки – (см. метод потенциалов)

Цикл –такая последовательность клеток транспортной таблицы (i₁,j₁), (i₁,j₂), (i₂,j₂),…(i_k,j₁), в которой две и только две соседние клетки расположены в одной строке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце.

(?)Перестановка по циклу - (сдвиг по циклу на величину t)-увеличение объемов во всех нечетных клетках цикла, отмеченных знаком «+», на t и уменьшение объемов перевозок во всех четных клетках, отмеченных знаком «-», на t.

3) Условие оптимальности опорного плана.

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

Оптимальный план перевозки соответствует минимуму линейной целевой функции f(X)= min при ограничениях на потребление и поставку