39. В каких случаях примется метод искусственного базиса?

При решении задачи линейного программирования симплекс-методом предполагалось, что среди векторов имеется m – единичных векторов. Это значит, что в каждом уравнении есть базисная переменная. Это переменная, которая является изолированной, т.е., переменная, которая входит лишь в одно уравнение с коэффициентом 1 и отсутствует в остальных уравнениях. Если этого нет, то базисные переменные можно формально дописать. В этом случае используется метод искусственного базиса.

40. Построение м-задачи в методе искусственного базиса.

Рассмотрим исходную задачу, заданную в канонической форме и в системе ограничений которой отсутствуют изолированные переменные:

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

Ясно, что искусственные переменные должны равняться нулю, чтобы выполнялись условия равенства системы ограничений. Если среди них окажутся не равные нулю, то исходная задача несовместна. Или, по-другому – ОДЗ задачи будет представлять собой пустое множество .

41.Построение индексной строки в методе искусственного базиса.

Числа в индексной строке имеют вид a+bM. Для их записи в симплексной таблице индексную строку разбиваем на две подстроки и записываем их в виде , т.е. в двух уровнях. В (m+1)-ю строку вносят а, а в (m+2) -ю b. Знак числа определяется знаком числа b если . Поэтому, сначала направляющий столбец выбираем по нижней строке, а после перевода всех искусственных переменных в свободные оптимизация производится по верхней индексной строке.

Если (m+2)-я индексная строка в результате преобразований превращается в нулевую, то это свидетельствует, что построен начальный опорный план исходной задачи и дальнейшая оптимизация производится по предпоследней индексной строке.

42. Критерий оптимальности в методе искусственного базиса

рассмотрим частный случай задачи ЛП .Напомним, что вектор является допустимым базисным решением (д.б.р.) этой задачи. Вычислим значение целевой функции для этого вектора. Обозначим его через :

. (2.6)

Обозначим через и через

, (2.7)

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

Теорема .Если в приведенных выше обозначениях в задаче ЛП существует оценка _k >0, то соответствующее д.б.р. x⁰ не является оптимальным и существует другое допустимое решение x¹, такое что .

Доказательство

Умножим соотношение 2.7 на ≥ 0 и вычтем из соотношения 2.6. Получаем:

Заметим, что и в левую и в правую часть полученного равенства мы прибавили величину . Рассмотрим вектор

.

Из п. 2.1 следует, что этот вектор является решением задачи ЛП (2.2), при этом если , то он будет допустимым при любом ≥0, если же , то, выбрав по критерию (2.5), получим вектор x¹, являющийся не только допустимым, но и базисным решением задачи ЛП (2.2). Теперь вернемся к полученному нами равенству и перепишем его в виде:

. Так как ≥0 и _k>0, то и теорема доказана.

Замечание. Если в теореме 6 >0, то неравенство будет строгим.

Теорема 7 (критерий оптимальности). Если в приведенных выше обозначениях в задаче для д.б.р. x⁰ все оценки _k ≤0, то x⁰- оптимальное решение.

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

Двойственный симплекс-метод заключается в построении оптимального недопустимого плана с последующим преобразованием его в допустимый, не нарушая оптимальности. Алгоритм двойственного симплекс-метода 1.      Выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов. 2.      Выбирают разрешающий столбец по наибольшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки. 3.      Пересчитывают симплексную таблицу по правилам обычного симплекс-метода. 4.      Решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов. Замечания: 1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима. 2. Если ограничения задачи заданы неравенствами типа «³», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных. 44. Понятие двойственности Теория двойственности представляет собой фундаментальное понятие в математическом программировании, имеющее теоретическое и практическое значение.  Основная идея теории двойственности: для каждой задачи ЛП существует некоторая задача ЛП, решение которой тесно связано с прямой. Между решениями прямой и двойственной задач имеется ряд важных соотношений, полезных при исследовании общих свойств оптимального решения ЗЛП и проверке оптимальности допустимого решения.  Экономический смысл двойственных задач Проанализируем экономический смысл двойственной задачи. Для этого сначала рассмотрим экономический смысл переменных. Экономический смысл переменной, отражающей ограниченность ресурса виден явно: она представляет собой двойственную оценку, или условную цену этого ресурса. Целевая функция данной двойственной задачи экономически интерпретируется как максимальная прибыль фирмы-поставщика ресурсов. 45.Соотношение между структурными элементами прямой и двойственной задачи Прямая Двойственная Целевая функция (min) Правая часть ограничений Правая часть ограничений Целевая функция (max) A – матрица ограничений AT – матрица ограничений i–ое ограничение: ≥ 0, (≤0) Переменная ui ≥ 0, (≤0) i–ое ограничение: = 0 Переменная ui ≠ 0 Переменная x ≥ 0 j–ое ограничение: ≤ 0 Переменная x ≠ 0 j–ое ограничение: = 0

46. Построение двойственных задач к исходным задачам, записанным в стандартной, канонической и общей форме модели(построение симметричных и несимметричных двойств. задач)

Стандартная форма (исходная)

_n

Σ a_ijx_j ≤ b_i, i=1,n(1)

^j=1

x_j≥0, j=1,n(2)

_n

z = Σ c_jx_j ->max(3)

^j=1

Двойственная стандартная

_m

Σ a_ijy_i ≤ c_j, j=1,n(1)

ⁱ⁼¹

y_i≥0, j=1,m(2)

_m

F = Σ b_iy_i ->min(3)

ⁱ⁼¹

Исходная задача в канонической форме:

_n

Σ a_ijx_j = b_i, i=1,m(1)

^j=1

x_j≥0, j=1,n(2)

_n

z = Σ c_jx_j ->min(3)

^j=1

Двойственная каноническая

_m

Σ a_ijy_i ≤ c_j, j=1,n(1)

ⁱ⁼¹

y_i- любые (2)

_m

F = Σ b_iy_i ->max(3)

ⁱ⁼¹

Дадим экономическую интерпретацию пары двойственных задач. Рассмотрим задачу рационального использования ресурсов. Пусть предприятие располагает ресурсами b1,b2,…bm, которые могут использ-ся для выпуска n-видов продукции. Пусть также известны стоимость единицы j-вида продукции cj (j=1,n) и норма потребления i-го ресурса (i=1,m) на производство единицы j-й продукции – aij.Требуется определить объем производства продукции каждого вида xj (j=1,n), максимизирующий суммарную стоимость

f= c1x1+…+cnxn (1)

При этом расход ресурсов не должен превышать их наличия:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Все известные по своему экономическому смыслу неотрицательны:

Xj>=0 (j=1,n). (3)

Заметим, что это задача образуют симитричную двойственную задачу.

Несимметричные двойственные задачи.

Возьмем ЗЛП на максимум в канонической форме:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

47.(второй вариант ответа)

Основная и вторая теорема двойственности (сформулировать теоремы и разъяснить)

Первая теорема двойственности.

Теорема: если одна из двойственных задач имеет оптимальный план, то и другая решима, т.е. имеет опт.план. При этом экстремальные значен.целевых функций совпадают (j=от 1 до n) Σcjxj*= (i=от 1 до m)Σbiyi* если в исходн. задаче целевая функция неограниченна на множестве планов, то в двойственной задаче система ограничений несовместна.

Вторая теорема двойственности и ее эконом.интерпритация.

Для того, чтобы допустимые решения пары двойственных задач были оптимальными, необходимо и достаточно выполнение условия: xj*(∑aij yi*-cj)=0, j от 1 до n, yi*(∑aij xj*-bi)=0, I от 1 до m. Это условия дополняющей нежесткости. Из них следует: если какое-либо ограничение двойств.задачи обращ-ся оптималь.планом в строгое равенство, то соответствующая компонента опт. плана двойственной задачи должно равняться нулю.Если же какая-то компонента опт. плана равна нулю, то соответствующее ограничение двойств.задачи обращается опт.планом в строгое равенство хj*>0 следовательно (i= от 1 до m)Σaij yi*=cj (затраты на пр-во продукции=цене) – Если продукция вошла в опт.план, то если затраты>цены, объем пр-ва=0 Σaij yi* >cj следовательно xj*=0

yi*>0 следовательно (j=от 1 до n) Σaij xj*=bi (рас-ды рес-ов =запас рес-ов).

(j=от 1 до n) Σaij xj* <bi следовательно yi*=0

Смысл теоремы сводится к следующему:

-если стоимост.оценка рес-ов расход-х на пр-во ед.прод-ии=цене, то этот вид прод-ии входит в оптим.план ;

-если затраты превышают цену, то прод-ию производить не следует;

- еслирасход рес-ов=запасу, то стоимост.оценка этого рес-са положительна. Такой рес-с наз-ся дефицитным. Наибелее дефицит.рес-с обладает наибольшей оценкой;

-если рес-с израсходован неполностью, то его стоимост.оценка = 0.

48. Правила построения двойственных задач

1.Число переменных двойственной задачи равно числу основных ограничений исходной задачи , число основных ограничений двойственной задачи равно числу переменных прямой задачи . Коэффициенты целевой функции

исходной задачи служат свободными членами основных ограничений двойственной задачи, а свободные члены основных ограничений

исходной задачи являются коэффициентами целевой функции двойственной задачи.

2. Матрица коэффициентов основных ограничений двойственной задачи является транспонированной по отношению к матрице A основных ограничений исходной задачи.

3. Каждому основному ограничению-неравенству исходной

задачи отвечает несвободная двойственная переменная (с ограничением на знак) .

4. Основным ограничениям -равенствам исходной задачи

отвечает свободная переменная (без

ограничений на знак).

5. Каждой несвободной переменной исходной задачи отвечает

основное ограничение -неравенство того же знака в двойственной задаче

6. Каждой свободной переменной ой задачи соответствует основное

ограничение-равенство

7. Целевая функция исходной задачи на max, двойственной на min .

49. Двойственная оценка (д.о.) ограничения i показывает, на сколько изменится целевая функция при единичном изменении объёма ограничения, т.е величины bi.

Изменение целевой функции будет соответствовать д.о. по крайней мере при достаточно малом изменении величины bi (изменение на единицу может оказаться слишком большим).

Изменение целевой функции может соответствовать д.о. при изменении bi только в одну сторону.

Единица измерения двойственной оценки –

[единица измерения целевой функции]

[единица измерения ограничения i]

Цель анализа – определить возможные изменения модели, при которых не меняется набор ненулевых (базисных) переменных и эффективных ограничений.

Значение целевой функции, а в ряде случаев – базисных переменных или ненулевых двойственных оценок при таких изменениях может меняться.

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

Анализ устойчивости

оптимального плана может также проводиться по отношению к:

Пределу введения в базис небазисной переменной при неизменных оценках и соответствующему изменению значений базисных переменных

Границам изменения технико-экономического коэффициента при небазисной переменной, не влияющего на значения переменных и двойственных оценок

Введению в оптимальный план новых переменных и ограничений (для этой цели достаточно исходной симплексной таблицы)

50. Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (||x_i,j||_mxn), который минимизирует целевую функцию

   (1)

на множестве допустимых планов

   (2)

при соблюдении условия баланса

      (3)      

Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n)mn. Матрицы систем уравне­ний в ограничениях (1) и (2) имеют ранги, равные соответ­ственно mи n. Однако, если, с одной стороны, просуммировать уравнения (1) по m, а с другой — уравнения (2) по n, то получим одно и то же значение. Из этого следует, что ур-е (3) является линейной комбинацией других. Таким образом, ранг матрицы транспорт­ной задачи равен m+n -1, и ее невырожденный базисный план должен содержать m+n -1 ненулевых компонент.

Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта a_i), а столбцы — пунктам потребления (послед­няя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о пе­ревозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значе­ние объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (x_i,j=0), называют свободными, а ненулевые — занятыми (x_i,j>0).

51. Типы транспортных задач. Имеются m поставщиков однородной продукции с известными запасами продукции и n потребителей этой продукции с заданными объёмами потребностей. Известны так же удельные затраты на перевозку.

Если сумма объемов запасов продукции равна объему потребностей всех потребителей, то такая задача назыв. закрытой транспортной задачей (т.е. если ), в противном случае трансп. задача назыв. открытой. Для решения транспортной задачи необходимо, чтобы она была закрытой.

Открытую тран. задачу можно преобр. к закрытой след. образом:

Пусть . В этом случае необходимо ввести фиктивного n+1 потребителя с объемом потребностей Удельные затраты на перевозку от поставщиков к фиктивному потребителю полагаются равными 0, так как на самом деле перевозки осуществляться не будут и некоторая часть продукции останется у поставщиков.

Если . В этом случ. необходимо ввести m+1 поставщика с объемом запасов . Удельные затраты на перевозку от фиктивного поставщика к потребителям полагаются равными 0, так как на самом деле такие перевозки осуществляться не будут и некоторую часть продукции потребители недополучат.

52. Северо-западный прием построения опорного плана. Согласно этому приему формирование величин перевозок начинается с с-з уголка таблицы, т.е. с клетки х11. По этому приему прежде всего распределяется товар первого поставщика. Причем первый поставщик сначала предельно возможно удовлетвор. первого потребителя. Затем, если у поставщика товар еще остался, метод наименьшего элемента в матрице.

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

Сначала делаем пометки в тех клетках строк, в которых наблюдается самая меньшая цена по строке. Затем обходим таблицу по столбикам и делаем такие же пометки в клетках, в которых самая маленькая цена по столбикам.

Дальнейшее распределение делается сначала предельно возможно по клеткам с двумя отметками, потом - с одной, а затем делается добалансировка задачи до ( m + n – 1) заполнений. Заполнения организуем при прохождении таблицы слева направо и сверху вниз.

53. Св-ва трансп. Задач

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

Теор. 1. Закрытая трансп. Задача всегда имеет решение.

Теор. 2. Если объемы запасов продукции и объемы потребностей явлется целыми числами, то и решение трансп. задачи также будет целочисленным.

Теор. 3. Система ограничений закрытой трансп. задачи всегда линейно-зависима.

Из этой теоремы следует, что распределение закрытой трансп. задачи всегда имеет m+n-1 базисную переменную и (m-1) (n-1) свободные переменные.