12. Проблема нахождения начального опорного решения

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

Например:

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

Метод искусственного базиса (м-метод)

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

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

Исходная задача приводится к кананической форме с помощью ввода или добавления искусственных пеерменных: у₁,у₂,y_n, позволяющих получить единичную матрицу.

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

Вид М-задач:

Этот вид задачи обобщенный.

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

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

Каждой задаче лин-го программирования соотв-т задача, называемая двойственной по отн-ю к исходной

Экон.интерпритациядвойств-й задачи об использ-и русурсов:

Предположим, что некоторая орган-я решила закупить ресурсы S₁,S₂…Sm предприятия и необходимой установить оптим-е цены на эти ресурсы y₁,y₂,…y_m

Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы в кол-х b₁,b₂,…b_m по ценам соотв-но y₁,y₂,…y_m были минимальны т.е

Z(y)=b₁y₁+b₂y₂+…+b_my_m→min

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

На изготовление единицы продукции p1 расходуется a11 единиц ресурса S1, a21 единиц ресурса S2, am1 единиц ресурса Sm по цене соотв-но y1,y2…ym

Поэтому для удовлетворения требований продавца затраты на ресурсы, потребление при изговл. Единицы продукции p1, должны быть не менее ее цены с1 т.е

Аналогично составл. огранич. в виде неравенств по каждому виду продукции p₁,p₂…p_m

Исходная задача	Двойственная задача
При ограничениях Составить такой план выпуска продукции Х=(Х1,Х2…Хn), при кот-м прибыль от реализации продукции будет максим-й при условии, что потребление рес-в по каждому виду продукции не превзойдет имеющих запасов	При ограничениях Найти такой набор цен(оценок)ресурсов Y=(y1,y2…yn) , при кот. общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при произв-ве каждого вида продукции будут не менее прибыли от реализации этой продукции

Цены рес-в y1,y2,…yn в лит-ре- учетные, теневые. В отличие от внешних цен с1,с2,…сn на продукцию известных, как правило, до начала произв-ва, цены рес-в у1,у2,…уnявл-сявнутрен-ми т.к задаются не извне. А опред-ся ,непосредственно, в рез-те реш-я задачи, поэтому их чаще назыв-т оценкамирес-в.