Построение последовательных итераций.

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

1) находим потенциалы U_k V_l всех поставщиков А_k и потребителей В_l.

2) выбираем какую-нибудь свободную переменную x_pq , для которой сумма потенциалов U_p + V_q строго больше соответствующей стоимости перевозки (тарифа), это соответствует элементу с отрицательным коэффициентом при этой свободной переменной x_pq в правой части выражения функции F.

3) для выбранной в пункте 2 переменной, находим цикл пересчета и производим сдвиг по этому циклу, этот сдвиг приводит к новому допустимому решению.

4) вышеуказанные операции 1-3 повторяются до тех пор, пока не придем к оптимальному базису, т.е. к неотрицательности коэффициентов при свободных переменных в правой части линейной функции F.

Получив исходное опорное решение, перейдем к построению новых опорных решений, улучшающих друг друга, применив метод потенциалов.

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

х _kl - базисные переменные

х _pq - свободные переменные

Базисными называются переменные соответствующие занятым клеткам в распределительной таблице. Занятыми клетки становятся в результате занесения в них перевозок по методу северо-западного угла, или методу минимального элемента. Занятых клеток, а, следовательно, базисных переменных всегда должно быть ровно m+n – 1 (m-число строк, а n – число столбцов в таблице). Остальные переменные, соответствующие незанятым клеткам в таблице называются свободными. Используя уравнения (12) и (13) базисные переменные x_kl можно выразить через свободные x_pq и подставить из в целевую функцию (14). В результате получим выражение

F = _pq х _pq + ₀ (15)

Для нахождения коэффициентов _pq при свободных переменных сопоставим каждому пункту отправления А_i величину U_i i = 1,2,… m, которую назовем потенциалом пункта А_i , а каждому пункту назначения В_j поставим в соответствие потенциал V_j. Поскольку транспортная задача является задачей линейного программирования, то для нее, как и для любой задачи ЛП, можно составить двойственную ЗЛП. Введенные потенциалы являются двойственными переменными такой двойственной ЗЛП и для них так же как в задачах (14), (15) записывается система ограничений. При этом, согласно второй теореме двойственности, для занятых клеток (там, где переменные прямой ЗЛП отличны от нуля, т.е. x_kl > 0) должно выполняться:

U_k + V_l = c_kl , (16)

где c_kl - стоимость перевозки единицы груза из пункта А_k в пункт назначения В_l.

Доказывается, что совокупность уравнений (16) составленных для всех базисных переменных, образует совместную систему уравнений, причем, значение одной из переменных можно задавать произвольно (обычно задают U₁ = 0), и тогда значения остальных переменных находятся из системы однозначно. Обозначим для свободных переменных сумму соответствующих потенциалов через С^′ _pq , т.е. U_p + V_q = С¢ _pq и назовем косвенной стоимостью (в отличие от данной стоимости, т.е.тарифа с_pq), тогда доказывается, что коэффициенты при свободных переменных в равенстве (15) имеют вид:

_pq = с_pq - С¢ _pq (данная стоимость минус косвенная стоимость).

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

Воспользуемся изложенными общими понятиями и продолжим решение примеров.

Продолжение примера 9.

Мы получили исходное опорное решение, следуя методу минимального элемента в виде

X₁ = F = 1020

Для нахождения потенциалов необходимо использовать систему:

U₁ + V₁ = c₁₁ = 6

U₁ + V₂ = c₁₂ = 10

U₁ + V₃ = c₁₃ = 4

U₂ + V₂ = c₂₂ = 2

Значение одной из неизвестных зададим произвольно, например U₁ = 0, а остальные найдем из системы:

V₁ = 6, V₂ = 10, V₃ = 4, U₂ = -8

Далее вычисляем косвенные стоимости:

С¢₂₁ = U₂ + V₁ = -8 + 6 = -2

С¢₂₃ = U₂ + V₃ = -8 + 4 = -4

Подсчитаем теперь разности

_pq = с_pq - С¢_pq

₂₁ = с₂₁ - С¢₂₁ = 12 – (-2) = 14

₂₃ = с₂₃ - С¢₂₃ = 8 - (-4) = 12

тогда F = 1020 + 14 х₂₁ + 12 х₂₃

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

Продолжение примера 8.

Первоначальное опорное решение согласно правилу северо-западного угла имеет вид:

X = F = 1860

Для нахождения потенциалов, необходимо решить систему:

U₁ + V₁ = c₁₁ = 6

U₁ + V₂ = c₁₂ = 10

U₂ + V₂ = c₂₂ = 2

U₂ + V₃ = c₂₃ = 8

Значение одной из неизвестных зададим произвольно, например U₁ = 0, а остальные найдем из системы:

V₁ = 6, V₂ = 10, U₂ = -8, V₃ = 16.

Вычисляем косвенные стоимости:

С¢₁₃ = U₁ + V₃ = 0 + 16 = 16

С¢₂₁ = U₂ + V₁ = -8 + 6 = -2

Затем посчитаем разности

_pq = с_pq - С¢_pq

₁₃ = 4 - 16 = -12

₂₁ = 12- (-2) = 14

следовательно

F= 1860 - 12 х₁₃ + 14 х₂₁

Среди коэффициентов при переменных в правой части есть отрицательный (при х₁₃ ), следовательно, можно попытаться уменьшить значение F, увеличив х₁₃ (сохранив нулевое значение х₂₁). Положим х₁₃ = l

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

Таблица 6

	90 - l	l
	20 + l	70 - l

Добавление l к х₂₂ компенсируется вычитанием l из х₁₂ , а это в свою очередь, прибавлением к х₁₃ , вычитанием из х₂₃

Мы получим так называемый цикл пересчета. После несложных рассуждений можно заключить, что l = 70. Получаем следующее опорное решение

X₂ = F = 1860 -12·70 = 1020

Как можно видеть (по предыдущему решению) оно является оптимальным.

Задача №4

Условие задачи представляют в табличной форме, а полученную матрицу называют платежной (матрицей игры).

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

Такими критериями являются:

1. Критерий Лапласа, который основан на вероятностях состояния природы. Если эти вероятности не известны, то можно предположить, что эти вероятности равны для всех состояний природы, т.е.

.

Если при этом представляет получаемый выигрыш (например, прибыль), то получим решение такое, которое обеспечивает .

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

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

, где a – показатель оптимизма, величина которого может принимать значения: .

4. Критерий минимаксного риска Сэвиджа позволяет путем замены платежной матрицы матрицей потерь (риска) определить оптимальную стратегию:

,

где - элементы матрицы риска,

- элементы платежной матрицы

-максимальный элемент в k- ом столбце платежной матрицы.

Пример 9.

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

Таблица 7

Величина прибыли, в тыс. руб.
План продажи	Состояние конъюнктуры рынка
П1		0,1		0,2		0,3		0,4
П2		0,1		0,2		0,3		0,4
П3		0,1		0,2		0,3		0,4
П4		0,1		0,2		0,3		0,4

X=0,6 Таблица 2

	К1	К2	К3	К4
П1
П2
П3
П4

1. По критерию Вальда (Таблица №8) мы должны найти в столбце min ( , т.е. (1,2,1,1)=2 и по критерию Вальда оптимальной является стратегия П₂.

2. Применим критерий Лапласа.

Итак, имеем: .

Подставив значения из таблицы №7, имеем, что оптимальной стратегией является П₂.

3. Применим критерий Гурвица. Вычислим при :

_.

Подставляя значения из Таблицы №8 получаем для четырех стратегий.

Выберем _.

По критерию Гурвица оптимальной является стратегия П₂.

4. Построим матрицу риска Сэвиджа по формуле: .

Таблица 9

	К1	К2	К3	К4	Выбираем
П1
П2
П3
П4

Риск необходимо свести к минимуму, т.е. в последнем столбце Таблицы №9 выбираем наименьшее значение

Т.к. по 2-м предыдущим критериям выбрали П₂, то и здесь П₂.

Первая буква	Фамилия	Имя
А																	0,1	0,2	0,3	0,4
Б																	0,5	0,2	0,1	0,2
В																	0,4	0,2	0,2	0,2
Г																	0,2	0,4	0,2	0,2
Д																	0,4	0,1	0,4	0,1
Е																	0,2	0,3	0,1	0,4
Ж																	0,7	0,1	0,1	0,1
З																	0,1	0,7	0,1	0,1
И																	0,1	0,1	0,7	0,1
К																	0,1	0,1	0,1	0,7
Л																	0,6	0,2	0,1	0,1
М																	0,2	0,6	0,1	0,1
Н																	0,1	0,2	0,1	0,1
О																	0,1	0,2	0,6	0,1
П																	0,1	0,1	0,2	0,6
Р																	0,5	0,2	0,2	0,1
С																	0,2	0,5	0,1	0,2
Т																	0,2	0,1	0,5	0,2
У																	0,2	0,2	0,1	0,5
Ф																	0,4	0,1	0,2	0,3
Х																	0,1	0,4	0,3	0,2
Ц																	0,1	0,2	0,3	0,4
Ч																	0,3	0,2	0,2	0,3
ШЭ																	0,2	0,3	0,3	0,2
ЮЯ																	0,3	0,2	0,3	0,2

ВОПРОСЫ К ЭКЗАМЕНУ

По дисциплине «Методы оптимальных решений» за 1 семестр

для заочного отделения по направлению подготовки «Экономика», профилям «Бухгалтерский учет, анализ и аудит», «Финансы и кредит».

1. Системы линейных неравенств. Множество решений системы линейных

неравенств.

2. Основная задача линейного программирования. Целевая функция. Макси-

мизация и минимизация целевой функции. Ограничения.

3. Общий вид математической постановки задачи линейного программиро-

вания.

4. Основная и каноническая формы записи ЗЛП, их взаимосвязь.

5. Графический метод решения ЗЛП. Область допустимых решений.

6. Симплекс-метод. Базисные и свободные переменные. Симплекс-таблица.

Построение симплекс-таблицы.

7. Геометрическая интерпретация симплексного метода. Теорема об опорном решении и угловой точке.

8. Достаточные условия существования оптимального решения ЗЛП, признак оптимальности опорного решения.

9. Алгоритм симплекс-метода.

10. Двойственность в линейном программировании, Построение симметрич-

ной двойственной задачи.

11. Связь оптимальных решений пары двойственных задач.

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

13. Определение двойственных переменных симметричной ЗЛП симплекс-

ным методом.

14. Определение двойственных оценок ЗЛП. Экономическая интерпретация

двойственных оценок.

15. Транспортная задача. Открытая и закрытая модели.

16. Определение исходного опорного решения по правилу «северо-западного

угла».

17. Определение исходного опорного решения по правилу «минимальной

стоимости».

18. Построение нового опорного решения с помощью метода потенциалов.

19. Оптимальное решение ТЗ методом потенциалов. Признак оптимальности.

20. Расчет потенциалов и оценок свободных клеток.

21. Понятие цикла. Правило пересчета решения по циклу.

22. Критерий Лапласа.

23. Критерий Гурвица.

24. Критерий Сэвиджа.

25. Критерий Вальда.

26. Роль и место моделирования в исследовании систем.

27. Предмет теории моделирования.

28. Классификация моделей.

Оформление контрольной работы

Результатом допуска к зачету по дисциплине «Методы оптимальных решений» является решенная контрольная работа со всеми заданиями с отметкой преподавателя «Зачтено». Если решенная работа не зачтена, студенту необходимо устранить замечания и сдать контрольную на повторное рецензирование.

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

Перед решением каждой задачи полностью записать ее условие. Решение задач сопровождается развернутыми расчетами и краткими пояснениями. Записать ответ. В конце контрольной работы привести список цитируемой литературы, дату и подпись.

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

Контрольная работа, выполненная не в соответствии с данными условиями задач, или оформленная на ПК не рецензируется и не зачитывается.

Список использованных источников

1. Интрилигатор М. Математические методы оптимизации и экономическая теория. М.: Изд. Айрис-Пресс, 2002. (гл. 5)

2. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. М.: Высшая школа, 2001. (гл. 3)

3. Фомин Г.П.Математические методы и модели в коммерческой деятельности. М.: «Финансы и статистика», 2010.

4. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. СПб.: Лань, 2000. (гл. 8, 9).

Не нашли, что искали? Воспользуйтесь поиском по сайту: