Ирина Эланс

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

Методы оптимальных решений. 20

МОСКОВСКИЙ ФИНАНСОВО-ЮРИДИЧЕСКИЙ УНИВЕРСИТЕТ-МФЮА

Факультет "Экономика, управление и информатика"

Кафедра "Менеджмент и маркетинг"

Специальность 080507 "Менеджмент организации"

КОНТРОЛЬНАЯ РАБОТА

Студента Бинчук Ольги Николаевны

На тему: Методы оптимальных решений

Автор работы:
Бинчук Ольга Николаевна
(ФИО)		(подпись)

Научный руководитель:
Зенина Наталья Васильевна
(ученая степень, звание, ФИО)		(подпись)

Волгоград 2013

Задание

Перечень вопросов по дисциплине "Методы оптимальных решений"

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

2.Транспрортная задача. Общая постановка Открытая и закрытая ТЗ.

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

Алгоритм метода искусственного базиса

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

Шаг 0 Построить начальную симплексную таблицу

Таблица1

Базис	БДР	X₁	X₂	....	Х_n		У₁	У₂	....	у_m
y	b	A E
z	∆₀	∆₁	∆₂	....	∆_n	∆_n+1		∆_n+2	....	∆_n+m

Оценки ∆n+1. . . ;∆n+m будут равны нулю. Остальные оценки вычисляются по формуле2

∆0 = 1 ・ b; ∆j = 1 ・ Aj

Искусственные переменные y1, . . . , ym образуют базис.

Шаг 1 К таблице применить ПСМ. Проверить значение целевой функции z, если оно больше нуля, то исходная задача решения не имеет. Перейти на шаг 3. Если z = 0, то возможны два случая:В столбце .Базис. только исходные переменные xj.Перейти на шаг 2.В столбце .Базис. имеются искусственные переменные. Такие переменныезаменяются на исходные с помощью преобразования Жордана — Гаусса. Для этого выбирается ведущая строка с искусственной переменной, и ведущий столбец — любой столбец, не находящийся в базисе, но такой, чтобы ведущий элемент не был равным нулю. После избавления от искусственных переменных перейти на шаг 2.

Шаг 2 Отбросить столбцы, соответствующие искусственным переменным, стереть оценки и вычислить новые в соответствии с исходной целевой функцией. Применить к получившейся таблице ПСМ. Перейти на шаг 3.

Шаг 3 Конец алгоритма.

Пример

1x1 + 3x2 + 2x3→ min

2x1 + 3x2 + 1x3 = 2

4x1 + 0x2 + 5x3 = 10

x1; x2; x3 > 0

Построили начальную симплексную таблицу. Оценки ∆0;∆1,...,∆n равны сумме элементов в соответствующих столбцах. Оценки искусственных переменных равны нулю (так как они все базисные). Выбрали ведущий столбец s = 3 (максимальная оценка -3 = 6, можно было выбрать и s = 1). Вычислили симплексные отношения (справа) выбрали минимальное для y1 (можно было выбрать и y2).

Таблица2

Базис

БДР

Таблица3

Базис

БДР

y 2

Х3

У2

2 - 6

3 - 15

1 -5

-6

-15

-6

Найдено оптимальное решение искусственной задачи. Оно равно 0, но в базисе осталась искусственная переменная (y2). Чтобы .убрать. её, выберем эту строку в качестве ведущей, а в качестве столбца возьмём, например, x1 (можно было бы взять x2, так -15 ≠ 0).

Таблица4

Базис

БДР

Х3

У2

-2

5/2

-2/3

5/ 6

1/3

-1/6

-1

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

и применить ПСМ.

Таблица5

1 3 2

Базис

БДР

-2

5/2

-3/2

Анализ строки оценок показывает, что решение уже оптимально (случайное совпадение). Оптимальное решение: z = 4, x1 = 0, x2 = 0, x3 = 2.

Транспортная задача. Общая постановка. Открытая и закрытая ТЗ

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

Транспортная задача. Один из экономико-математических методов. Цель: минимизация затрат при перевозке грузов. При ее помощи решаются ресурсные задачи (пр: КР пути. Есть карьеры балласта, с какого лучше везти. Пр: прикрепление поставщиков и потребителей) Транспортная задача может решаться в матричной или сетевой форме.

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.

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

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

Постановка Транспортной задачи (ТЗ) для n переменных

Пусть имеется несколько поставщиков однородной продукции (каждый с определенным запасом) и несколько потребителей этой продукции (с известными потребностями у каждого). Задана также сеть коммуникаций (дорог, рек, воздушных линий и т.д.) связывающая каждого поставщика с каждым потребителем. На каждой коммуникации задана цена перевозки – стоимость перевозки единицы продукции. Если какая – либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+∞). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.

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

Транспортные задачи бывают:

1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)

2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)

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

Открытую ТЗ сводят к закрытой ТЗ путем прибавления к суммарному запасу продукции или суммарной потребности продукции недостающих единиц до равенства суммарного запаса продукции и суммарной потребности продукции.

Закрытая транспортная задача формулируется как Задача Линейного Программирования (ЗЛП) следующего вида:

, где

а_i- запас i – го поставщика

b_j - потребность j – го потребителя

c_ij - цена перевозки единицы продукции по коммуникациям (i,j)

(от i – го поставщика к j – му потребителю)

x_ij - объем перевозки продукции (неизвестный) по коммуникациям (i,j).

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

Структура матрицы ограничений транспортной задачи такова, что столбец, соответствующей переменной x_ij содержит ровно два ненулевых элемента: единицу в строке с номером i и единицу в строке m + i.

Вектор двойственных переменных Y=(u_1,...,u_m,v_i,...,v_n) имеет m + n компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные u₁,u_2,…,u_m - потенциалы поставщиков; переменные v₁,v_2,…,v_n - потенциалы потребителей. Используя схему для построения двойственной задачи к ЗЛП в стандартной форме, имеем:

В полученной двойственной задаче n·m ограничений, соответствующих каждой переменной x_ij ТЗ. Вспоминая, что невязка между левой и правой частью в ограничений двойственной задачи есть оценка для соответствующей переменной исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:

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

для заполненных клеток (i,j) таблицы ТЗ.

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

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

ШАГ 1. Построение начального плана перевозок.

ШАГ 2. Проверка текущего плана на оптимальность.

Если план оптимален, то алгоритм завершен.

ШАГ 3. Улучшение плана перевозок. Переход к шагу 1.

Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.Построение начального решения (как и последующие расчеты) проводят в таблице, имеющей следующий вид:

цены перевозок
			n-столбцов
запасы	1	120	5	10	12	m-строк
	2	70	8	6	4
	3	50	0	0	0
			60	100	80
			1	2	3
			потребности

Метод штрафных функций

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

Легко увидеть, что можно построить различные функции, удовлетворяющие этому определению. Например, самой простой штрафной функцией может служить следующая функция, где – некоторая положительная константа. Эта функция имеет недостатки, затрудняющие использование ее на практике: она не является непрерывной, и величина штрафа не зависит от величины нарушения ограничений, задающих множество . Учитывая информацию о системе ограничений, определяющих , можно построить штрафные функции, лишенные этих недостатков.

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

Линейная комбинация нескольких штрафных функций с положительными коэффициентами также является штрафной функцией.

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

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

Доказательство. Тогда по теореме Куна-Таккера найдётся вектор такой, что – седловая точка функции Лагранжа.

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

Применение методов штрафных функций

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

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

Параметрические методы распадаются на три категории:

1) методы внутренней точки;

2) методы внешней точки;

3) комбинированные методы.

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

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

J(u)->inf; uU (1)к последовательности задач минимизации k(u)->inf; u U0, k=0,1,…, (2)

где k(u) - некоторая вспомогательная функция, а множество U0 содержит U.

При этом функция k(u) подбирается так, чтобы она с ростом номера k мало отличалась от исходной функции J(u) на множестве U и быстро возрастала на множестве

U0\U.

Можно ожидать, что быстрый рост функции k(u) вне U приведет к тому, что при больших k нижняя грань этой функции на U0 будет достигаться в точках, близких ко множеству U, и решение задачи (2)будет приближаться к решению задачи (1). Кроме того, как увидим ниже, и меняться достаточно широкий произвол в выборе функций k(u) и множества U0 для задач (2), и можно надеяться на то , что задачи (2) удастся составить более простыми по сравнению с задачей (1) и допускающими применение несложных методов минимизации.

Определение 1: Последовательность функций

{Рk(u), k=0,1,..},

определенных и не отрицательных на множестве U0, содержащем множество U, называют штрафом или штрафной функцией множества U на множестве U0, если

Из этого определения видно, что при больших номерах k за нарушение условия uU приходится "платить" большой штраф, в то время как приu

U штрафная функция представляет собой бесконечно малую величину при k->. Для любого множества UЕn можно указать сколько угодно различных штрафных функций.

Например, если {Аk} - какая-либо положительная последовательность, Аk, то можно взять

Рk(u)= Аk(u,U), uEnU0, k=0,1,…

(здесь U предполагается замкнутым) или

здесь (u,U)=|u-v| - расстояние от точки до множества U, а - какая либо точка из U.

Другие примеры штрафных функций будут приведены ниже. Допустим, что некоторое множество U, содержащее U,а также штрафная функция {Р(u)} множества U на U0 уже выбраны . Предполагая, что функция J(u) определена на U0, введем функции

(u)=J(u)+P(u), uU0, k=0,1,... (3)

и рассмотрим последовательность задач (2) с функциями (3). Будем считать,

что =(u)>-, k=0,1,…

может и не достигаться. Поэтому будем считать, что при каждом k=0,1,… с помощью какого-либо метода минимизации найдена точка uk, определяемая условиями:

ukU0, (uk) (6),

где - некоторая заданная последовательность, , k=0,1,…, (если uk удовлетворяет условиям (5), то в (6) допускается возможность =0). Отметим, что, вообще говоря, ukU. Метод штрафных функций описан. Дальнейшее изложение не зависит от того, каким конкретным методом будет найдена точка

uk из (6).

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