8. Двойственная задача. Первая теорема двойственности и ее следствия.

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

Следствие 1. Если исходная задача является задачей в канонической форме и ее оптимальная симплекс таблица известна, то оптимальное решение двойственной задачи есть ( , ) =

Следствие 2. Если исходная задача является задачей в стандартной форме и ее оптимальная симплекс таблица известна, то оптимальное решение двойственной задачи есть =

Исходная задача ЛП:

Задача, двойственная к исходной задаче ЛП

Из приведенного определения следует, что двойственная ЗЛП строится по сле­дующим правилам:

1) Каждому ограничению прямой задачи соответствует переменная двойственной задачи, т.е. число переменных двойственной задачи (y₁,.,.,y_n) равно числу ограничений прямой задачи.

2) Каждой переменной прямой задачи соответствует ограничение двойственной за­дачи, т.е. число ограничений двойственной задачи равно числу переменных прямой задачи.

3). Матрица функциональных ограничений двойственной задачи получается путем транспонирования матрицы функциональных ограничений прямой задачи.

9. Экономическая интерпретация двойственной задачи.

F =

i = 1,2…m

j = 1,2…n

n- число технологий произведенной продукции

– цена одной ед. продукта, произведенной по j технологии

F = – прибыль

А – технологическая матрица

– кол – во ресурса вида i необходимого для производства продукта j технологии

- кол-во ресурса вида i использующегося в производстве

– запас ресурса вида i.

10. Теневая цена. Экономическая интерпретация дополнительных переменных.

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

Теневая цена – значение изменения целевой функции при изменении дефицитного ресурса на 1 единицу. Теневая цена недефицитного ресурса будет равна 0.

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

11. Анализ решения на чувствительность.

Анализ чувствительности – это анализ ситуации, как изменение параметров модели повлияет на полученное ранее решение.

Для решения задачи анализа чувствительности ограничения делятся следующим образом:

1. связывающие (ограничения, которые проходят через оптимальную точку)

2. несвязывающие (ограничения, которые не проходят через оптимальную точку)

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

Выделяют 3 следующие задачи анализа на чувствительность:

1. Анализ сокращения, либо увеличения ресурса (на сколько можно увеличить, если ограничение имеет вид , либо уменьшить при , запас дефицитного ресурса с целью улучшить доход

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

3. Увеличение/уменьшение запаса какого ресурса наиболее выгодно

4. Задача анализа изменения целевых коэфф. Какой диапозон изменения коэффициента целевой функции при котором не меняется оптимальное решение.

12. Транспортная задача, экономико-математическая модель, свойства транспортной задачи.

Транспортная задача — задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения

Число пунктов производства – m

i= 1,2…m – количество продукта, произведенного на i пункте.

Количество пунктов потребителя – n

j = 1,2…n – потребность j пункта потребления.

- цена перевозки ед. продукции из i пункта в j.

Классическая постановка задачи

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

Математическая модель задачи:

- кол-во ед. продукта, перевозимого с i пункта производства в j пункт.

Кол – во продукта, вывезенного с i пункта произв.:

i = 1,2..m

Кол-во ед. продукта:

j = 1,2..n

Критерий – суммарные затраты:

F =

Свойства транспортной задачи:

Транспортная задача разрешима тогда, когда выполняемы условия баланса:

- закрытая тр. Зад.

Ранг матрицы ограничений тр. Зад. = m+n-1.

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

Транспортные задачи разделены на два вида: открытые и закрытые. Транспортная задача считается закрытой, когда сумма товаров у поставщиков равна сумме потребностей потребителей ( )

Открытые задачи делятся еще на два типа:

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

2. Суммарное количество потребностей превышает количество изготовленных товаров ( ). В этом случае вводится фиктивный поставщик (строка )

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