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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

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

 

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

 

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

 

 

 

 

 

 

 

 

Волгоград 2013

 

 

Задание

 

 

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

 

 

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

 

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

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

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

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

 

 

                                                                                                 Таблица1

 

Базис	БДР	X1	X2	....	Хn		У1	У2	....	уm
y	b	A                                              E
z	∆0	∆1	∆2	....	∆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

Базис	БДР	x1	x2	x3	y1	y2
y1   y2	2   10	2   4	3   0	1   5	1   0	2   2
z	12	6	3	6	0	0

 

 

                                                                               Таблица3

Базис	БДР	x1	x2	x3	y1	y 2
Х3   У2	2   0	2       - 6	3       - 15	1    0	1       -5	0    1
z	0	-6	-15	0	-6	0

 

 

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

 

 

                                                                                  Таблица4

 

Базис	БДР	x1	x2	x3	y1	y2
Х3   У2	2   0	0   1	-2      5/2	1 0	-2/3              5/ 6	1/3  -1/6
z	0	0	0	0	-1	-1

 

 

 

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

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

 

 

                                                                                    Таблица5

                                                              1               3             2

Базис	БДР	x1	x2	x3
x3 x1	2 0	0 1	-2 5/2	1 0
z	4	0	-3/2	0

 

 

 

Анализ строки оценок показывает, что решение уже оптимально (случайное  совпадение). Оптимальное решение: 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 - потенциалы потребителей. Используя схему для построения двойственной задачи к ЗЛП в стандартной форме, имеем: