 |
Задачи для самостоятельного решения
|
|
|
|
Компании планирует инвестировать свободные средства. Как варианты для инвестиций выступают четыре проекта. Выбор проекта осуществляется на основании трех критериев (стоимость реализации, уровень риска, прибыль от реализации проекта). Пусть даны некоторые экспертные оценки критериев (К 1,К 2,К 3) и оценки альтернатив (А 1,А 2,А 3,А 4) по каждому из критериев. Рассчитать глобальные приоритеты альтернатив, отношения согласованности для каждой матрицы парных сравнений и определить наиболее предпочтительный для реализации проект.
Вариант 1
Оценки критериев
| К 1 | К 2 | К 3 | |
| К 1 | 1/7 | 1/5 | |
| К 2 | |||
| К 3 | 1/4 |
Оценки альтернатив по критерию К 1
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/2 | 1/5 | ||
| А 2 | 1/3 | 1/2 | ||
| А 3 | 1/4 | |||
| А 4 |
Оценки альтернатив по критерию К 2
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | ||||
| А 2 | 1/7 | 1/2 | ||
| А 3 | 1/4 | |||
| А 4 | 1/5 | 1/2 | 1/3 |
Оценки альтернатив по критерию К 3
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/2 | 1/5 | ||
| А 2 | 1/4 | |||
| А 3 | ||||
| А 4 | 1/8 | 1/6 | 1/5 |
Вариант 2
Оценки критериев
| К 1 | К 2 | К 3 | |
| К 1 | |||
| К 2 | 1/5 | ||
| К 3 | 1/3 | 1/2 |
Оценки альтернатив по критерию К 1
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/2 | |||
| А 2 | ||||
| А 3 | 1/5 | 1/7 | ||
| А 4 | 1/3 | 1/9 | 1/4 |
Оценки альтернатив по критерию К 2
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/6 | |||
| А 2 | ||||
| А 3 | 1/2 | 1/4 | ||
| А 4 | 1/7 | 1/2 |
Оценки альтернатив по критерию К 3
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | ||||
| А 2 | 1/5 | 1/2 | ¼ | |
| А 3 | 1/8 | |||
| А 4 | 1/2 |
|
|
|
Вариант 3
Оценки критериев
| К 1 | К 2 | К 3 | |
| К 1 | 1/2 | 1/4 | |
| К 2 | 1/2 | ||
| К 3 |
Оценки альтернатив по критерию К 1
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/2 | 1/3 | ||
| А 2 | 1/6 | 1/3 | ||
| А 3 | 1/3 | |||
| А 4 |
Оценки альтернатив по критерию К 2
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/3 | |||
| А 2 | ||||
| А 3 | 1/2 | |||
| А 4 | 1/8 | 1/6 | 1/5 |
Оценки альтернатив по критерию К 3
| А 1 | А 2 | А 3 | А 4 | |
| А 1 | 1/5 | 1/2 | ||
| А 2 | ||||
| А 3 | ||||
| А 4 | 1/4 | 1/8 | 1/6 |
Лабораторная работа №4
Симплекс-метод
Цель работы: Познакомиться с симплекс-методом, овладеть навыками нахождения оптимального решения, выполнить необходимые расчеты в программе Mathcad согласно определенному преподавателем варианту. Сделать вывод о полученных результатах.
Теоретические сведения
При постановке задачи оптимизации необходимо:
1. Наличие объекта оптимизации и цели оптимизации. При этом формулировка каждой задачи оптимизации должна требовать экстремального значения лишь одной величины, т.е. одновременно системе не должно приписываться два и более критериев оптимизации, т.к. практически всегда экстремум одного критерия не соответствует экстремуму другого.
2. Наличие ресурсов оптимизации, под которыми понимают возможность выбора значений некоторых параметров оптимизируемого объекта.
3. Возможность количественной оценки оптимизируемой величины, поскольку только в этом случае можно сравнивать эффекты от выбора тех или иных управляющих воздействий.
4. Учет ограничений.
Из практики рассмотрения задач математического программирования следует, что в общем виде решить их практически невозможно. Целесообразно рассматривать отдельные классы (виды) задач. Наиболее разработанными в математическом программировании являются задачи линейного программирования (ЛП).
|
|
|
В задачах линейного программирования целевая функция линейна, а условия-ограничения содержат линейные равенства и линейные неравенства. Переменные могут быть подчинены или не подчинены требованию неотрицательности.
Общая задача линейного программирования:
F = c1x1 + c2x2 + c3x3 + … + cnxn → max (min) (6)
В данной задаче необходимо найти такой вектор X = (x 1,x 2,x 3 … x n), при котором целевая функция(6) принимает экстремальное значение и удовлетворяет ограничениям системы m линейных уравнений с n переменными (7):
a11x1 + a12x2 + … + a1nxn ≤ b1 (7)
a21x1 + a22x2 + … + a2nxn ≤ b2
a31x1 + a32x2 + … + a3nxn ≤ b3
… … …
am1x1 + am2x2 + … + amnxn ≤ bm
X ≥ 0
Где aij – константы системы ограничений (при i = 1 … n, j = 1 … m);
xj – переменные системы ограничений;
bj – ограничения.
Вектор X называется допустимым решением или планом. Множество всех допустимых решений составляет область допустимых значений. План называется оптимальным, если оно доставляет экстремум целевой функции.
Решение задач ЛП осуществляется по следующему алгоритму:
1. приводим целевую функцию к стандартному виду – поиск максимума;
2. приводим систему ограничений к каноническому виду;
3. определяем базис и заполняем таблицу;
4. находим разрешающий элемент и осуществляем пересчёт элементов таблицы;
5. проверяем найденное решение на оптимальность, если экстремум не достигнут, то повторяем пункты 3 – 5 до тех пор пока не будет найден максимум или установлено его отсутствие для данных условий.
Рассмотрим каждый шаг симплекс-метода на конкретном примере. Компании, занимающейся производством офисной мебели необходимо получить максимальную прибыль от реализации произведенных офисных столов, при этом важно в полной мере использовать имеющиеся ресурсы (древесина, пластик, металл), необходимые для производства данных товаров. Общие условия задачи приведены в таблице 22.
Таблица 22 – Условия задачи
| Продукт 1 | Продукт 2 | Продукт 3 | Ограничения | |
| Древесина | ||||
| Пластик | ||||
| Металл | ||||
| Прибыль |
Как видно из таблицы, в распоряжении компании имеются 100 единиц древесины, 130 единиц пластика и 110 единиц металла. На каждую модель офисного стола необходимо то или иное число единиц сырья. Важно отметить, что условия задачи не требуют выпуска всех видов продукции, но важно максимально реализовать имеющееся сырье с извлечением максимальной прибыли.
|
|
|
Математическая модель задачи имеет следующий вид:
F = 5x1+6x2+7x3 →max
x1…3 ≥ 0
1. Если в исходной задаче требуется найти минимум, то умножаем целевую функцию на -1 и имеем стандартную задачу. В данной задаче этого не требуется.
2. В каноническом виде система ограничений представлена как система равенств, при этом остаётся требование неотрицательности переменных:
a11x1 + a12x2 + … + a1nxn = b1 (8)
a21x1 + a22x2 + … + a2nxn = b2
a31x1 + a32x2 + … + a3nxn = b3
… … …
am1x1 + am2x2 + … + amnxn = bm
X ≥ 0
Для преобразования в канонический вид в каждое из m неравенство системы ограничений вводится дополнительная неотрицательная переменная: xn+1, xn+2, …, xn+m. В данном случае система ограничений принимает следующий вид (9):
a11x1 + a12x2 + … + a1nxn + xn+1 = b1 (9)
a21x1 + a22x2 + … + a2nxn + xn+2 = b2
a31x1 + a32x2 + … + a3nxn + xn+3 = b3
… … …
am1x1 + am2x2 + … + amnxn + xn+m = bm
X ≥ 0
Где xn+1, xn+2, xn+3 …, xn+m – выравнивающие балансовые переменные.
При переходе должны выполняться следующие условия:
· неравенство вида a1x1 + a2x2 + … + anxn ≤ b равносильно равенству a1x1 + a2x2 + … + anxn + xn+1 = b1 и простейшему неравенству xn+1 ≥ 0;
· неравенство вида a1x1 + a2x2 + … + anxn ≥ b1 равносильно равенству a1x1 + a2x2 + … + anxn - xn+1 = b и простейшему неравенству xn+1 ≥ 0;
· каждую переменную, на которую не наложено условие неотрицательности, можно представить в виде разности двух
Приведем модель к каноническому виду, добавив ряд переменных. В итоге получим следующее:
F = 5x1+6x2+7x3+x4+x5+x6→max
x1…6 ≥ 0
3. Базисными выбираем те переменные, которые встречаются лишь в одном из уравнений системы ограничений. Заполняем таблицу. Для этого в каждую строку заносим коэффициенты соответствующего уравнения системы ограничений, не забываем заполнить столбец свободных членов. Последняя строка называется индексной. Она составляется из коэффициентов целевой функции. Целевую функцию приводим к виду F-5x1-6x2-7x3-x4-x5-x6=0. Слева заполняем столбец именами базисных переменных, в соответствии с единичным значением.
|
|
|
Приступаем к решению, построив первую опорную таблицу 23.
Таблица 23 – Опорная таблица №1.
| Базис | x1 | x2 | x3 | x4 | x5 | x6 | Св. чл. |
| x4 | |||||||
| x5 | |||||||
| x6 | |||||||
| Индекс.ст. | -5 | -6 | -7 |
4. Определяем разрешающий столбец: разрешающим столбцом является тот, в котором элемент индексной строки максимален по модулю. В нашем случае это столбец с элементом индексной строки -7. определяем разрешающую строку: делим свободные члены на соответствующие строкам элементы разрешающего столбца. Т.е 100/1=100, 130/1=130, 110/5=22. Строка с минимальным значением отношения считается разрешающей, т.е. 22. Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки. Соответственно разрешающий элемент: 5. определение разрешающих строки и столбца определяет переменную вводимую в базис и переменную выводимую из базиса (не забывайте менять имена переменных в строке заголовке и столбце базисных переменных)
В новой таблице разрешающий элемент принимает значение единицы, а элементы индексного столбца 0. Пересчет элементов разрешающей строки производится делением первоначальных значений элементов разрешающей строки на первоначальное значение разрешающего элемента. Элементы разрешающей строки следующие: 0,4; 0,6; 1; 0; 0; 0,2; 22.
Оставшиеся элементы таблицы пересчитываем с помощью формулы (12):
a,ij = aij – a,qj*aip (12)
Где aij – первоначальное значение элемента;
a,qj – новое значение элемента разрешающей строки;
aip – первоначальное значение элемента разрешающего столбца.
Результатом станет таблица 24.
Таблица 24 – Опорная таблица №2
| Базис | x1 | x2 | x3 | x4 | x5 | x6 | Св. чл. |
| x4 | 2,60 | 3,40 | 0,00 | 1,00 | 0,00 | -0,20 | 78,00 |
| x5 | 3,60 | 4,40 | 0,00 | 0,00 | 1,00 | -0,20 | 108,00 |
| x3 | 0,40 | 0,60 | 1,00 | 0,00 | 0,00 | 0,20 | 22,00 |
| Индекс.ст. | -2,20 | -1,80 | 0,00 | 0,00 | 0,00 | 1,40 | 154,00 |
5. Оптимальное решение найдено, если все элементы индексной строки имеют положительное значение. Если в какой либо строке таблицы,, за исключением индексной, нет положительных коэффициентов, то система ограничений несовместна, она не имеет ни одного допустимого решения, а следовательно, и оптимального.
Как видно из таблицы 3, в индексной строке есть отрицательные значения, поэтому продолжаем решать задачу по определенному выше алгоритму.
Таблица 26 – Опорная таблица №3
| Базис | x1 | x2 | x3 | x4 | x5 | x6 | Св. чл. |
| x1 | 1,00 | 1,31 | 0,00 | 0,38 | 0,00 | -0,08 | 30,00 |
| x5 | 0,00 | -7,84 | 0,00 | -1,38 | 1,00 | 0,08 | 0,00 |
| x3 | 0,00 | 0,08 | 1,00 | -0,15 | 0,00 | 0,23 | 10,00 |
| Индекс.ст. | 0,00 | 1,08 | 0,00 | 0,85 | 0,00 | 1,23 | 220,00 |
Проверяем индексную строку – все элементы положительные. Значит решение оптимально. Мы получили, соответственно, следующее результаты: x1=30; x2=0; x3=10; F(x)=220. Следовательно, для получения максимальной прибыли в размере 220 денежных единиц необходимо произвести 30 офисных столов первой модели и 10 третьей.
|
|
|
|
|
|
