Главная Учебники - Разные Лекции (разные) - часть 34
|
Министерство образования и науки Российской Федерации Южно-Уральский государственный университет Кафедра систем управления по дисциплине «Исследование операций» Нормоконтроллёр: Плотникова Н. В. «____» ___________ 2005 г. Руководитель: Плотникова Н. В. «____» ___________ 2005 г. Автор: Студент группы ПС-346 Нечаев Л. В. «____» ___________ 2005 г. Работа защищена с оценкой «____» ___________ 2005 г. Оглавление
Список использованной литературы 29 Задача 1 Оператор связи оказывает 2 вида услуг: Предоставление одной линии телефонной сети общего пользования (ТСОП) и трёх линий цифровой связи (ЦС); Предоставление одной линии ЦС и двух линий ТСОП. Стоимость услуг указана в табл. 1: Таблица 1 Сети связи и эксплуатируемое оборудование накладывает следующие ограничения на количество используемых линий связи: ТСОП ≤ 300 ЦС ≤ 120 ТСОП+2*ЦС ≤ 380 Определить оптимальное соотношение услуг 1 и 2, которые оператор должен предоставлять для получения максимальной выручки. Обозначим за x1 количество оказанных услуг с номером `1', а x2 – количество оказанных услуг с номером `2'. Учтём ограничения задачи: Составим целевую функцию, которую нужно максимизировать: Задача сведена к следующей задаче линейного программирования: «Найти значения аргументов x1 и x2, при которых функция Решим выше представленную задачу графическим методом, так как в задаче присутствуют только 2 переменные x1 и x2. Для этого: Изобразим многоугольник решений в плоскости x2Ox1: График представлен на рис. 1. В начале максимизации наибольшее значение целевой функции равно 0, также F проходит через начало координат (пунктирная линия на рис. 1). Вектор Оптимальное решение находится в точке (0; 95), находящейся на пересечении прямых Итак, для получения наибольшей прибыли (57000 ед.) оператор связи должен не предоставлять услуг 1, а услуг 2 предоставить в количестве 95 штук. Не предоставлять yслуг #1 Yслуг #2 предоставить в количестве 95 штук. Решение задачи линейного программирования. С помощью симплекс–таблиц найти решение задачи линейного программирования: определить экстремальное значение целевой функции F=CTx при условии Ax B, где CT = [ c1 c2 . . . c6 ]T , ВT = [ b1 b2 . . . b6 ]T , XT = [ x1 x2 . . . x6]T , А= [aij] (i=1,6; j=1,3). Таблица 2 Составляем систему: Целевая функция имеет вид Приведем систему ограничений к виду основной задачи линейного программирования: Пусть х1, х2 – свободные переменные, х3, х4, х5 – базисные. Приведем систему и целевую функцию к стандартному виду, для построения симплекс-таблицы: Составляем симплекс-таблицу. Это решение является допустимым, но не опорным, т.к. присутствует отрицательный свободный член во второй строке. Ликвидируем его путём замены базисных переменных на основные. В строке x4 находится отрицательный элемент a42=-2, следовательно, столбец x2 – разрешающий. Наименьшее отношение между свободным членом и эл-том разрешающего столбца (см. поле «оценка») будет в первой строке и элемент a32 – разрешающий. Получилась таблица 3 (верхние числа). Таблица 3 2 2 -1 -1 1 1 -7 4 3 -2 -2 2 16 -4 3 2 2 -2 6 18 13 -9 -9 9 Теперь преобразуем таблицу по следующему алгоритму: Выделим разрешающий элемент aij; Найдём обратную ему величину λ=1/aij и запишем её в правом нижнем углу этой же ячейки; Все элементы разрешающей строки, кроме разрешающего элемента, умножим на λ и запишем внизу соответствующей ячейки; Все элементы разрешающего столбца , кроме разрешающего элемента, умножим на -λ и запишем внизу соответствующей ячейки; Выделим все верхние числа в разрешающей строке, и все нижние - в разрешающем столбце; Для каждого из остальных элементов запишем в нижнюю часть ячейки произведение выделенных чисел, стоящих в той же строке и в том же столбце, что и данный элемент; Перепишем таблицу, заменив переменные: элементы разрешающих строки и столбца – значениями, стоящими в нижних частях этих ячеек; оставшиеся элементы – суммой чисел, стоящих в верхних и нижних частях ячеек. Применительно к текущему шагу, разрешающий элемент a32, λ = 1 / a32 = 1. После указанных выше преобразований, получим новую таблицу (табл. 4): Таблица 4 Решение снова не может быть опорным, т.к. присутствует отрицательный свободный член во второй строке. Попытаемся ликвидировать его путём замены базисных переменных на основные. Но в строке x4 больше нет отрицательных элементов, следовательно, невозможно выбрать разрешающий столбец. Заметим, что в строке целевой функции нет отрицательных элементов, значит оптимальное решение, в случае отмены ограничений на переменные, достигнуто. Ограничивающая система уравнений не имеет решений при неотрицательных значениях всех переменных. Система уравнений несовместима в области положительных значений переменных. Этот же результат получен и при решении данной задачи в пакете Mathematica: Задача 3 Решение транспортной задачи: 1. Записать условия задачи в матричной форме. 2. Определить опорный план задачи. 3. Определить оптимальный план задачи. 4. Проверить решение задачи методом потенциалов. Таблица 5 Заметим, что общее количество запасов (700+600+200+200+100=1800) меньше количества заявок (300+700+1000=2000), следовательно имеем открытую транспортную задачу с избытком заявок. Добавим строку с фиктивными запасами для дополнения задачи до задачи закрытого типа. После корректировки получаем транспортную задачу с правильным балансом (табл. 6): Таблица 6 Найдём опорное решение методом наименьших затрат (табл. 7): Таблица 7 10 300 20 400 32 - 12 - 50 - 25 600 21 - 18 200 50 - 25 - 15 100 23 100 21 - 30 - 40 100 0 - 0 - 0 200 Выбранный план перевозок является допустимым, т.к. при нём все заявки удовлетворены и все запасы израсходованы, сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу – заявке соответствующего пункта назначения. Сумма запасов равна сумме заявок, и выражается числом 2000, стоящим в правом нижнем углу таблицы. Данное распределение является базисным (заполнено m+n-1=8 ячеек таблицы), следовательно, задача готова к решению. Первоначально затраты на перевозку составят: Составим матрицу оценок методом потенциалов: Начнём с первого столбца. Пусть потенциал этого столбца равен нулю. Рядом с потенциалом в скобках записываем номер шага. После прибавления потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (1;1) не изменится; чтобы полученный после сложения коэффициент стал равен 0, потенциал первой строки таблицы должен быть равен -10; для обнуления коэффициента затрат клетки (1;2) потенциал второго столбца должен быть -10 и т.д. Изменённые коэффициенты выписываются в виде матрицы оценок: Критерий оптимальности (базисное распределение поставок верно тогда и только тогда, когда оценки всех свободных клеток неотрицательны) на данном шаге не выполнен – присутствуют 2 свободные клетки с отрицательными оценками. Продолжим оптимизацию (табл. 8). Составим цикл пересчёта для клетки (5;2) и дадим поставку неё: Таблица 8 10 300 20 400 32 - 12 - 50 - 25 600 21 - 18 200 50 - 25 - 100 23 + 100 21 - 30 + - 40 - 100 0 - 0 - 0 200 В верхнем правом углу знаком «+» отмечаются те клетки, поставки в которые увеличатся, а знаком «-» - те, в которые уменьшатся. Наибольшая возможная поставка, исходя из текущего цикла пересчёта равна min {100, 100, 100} = 100. Передвигаем её по циклу (табл. 9): Таблица 9 10 300 20 400 32 - 12 - 50 - 25 600 21 - 18 200 50 - 25 - 15 0 23 200 21 - 30 100 40 - 0 - 0 - 0 200 После передвижения освободились сразу 2 клетки, решение перестало быть базисным. Для того, чтобы оно осталось базисным, дадим фиктивную поставку в клетку (4;2). Снова составляем матрицу оценок по вышеприведённому алгоритму: На текущем шаге клеток с отрицательной оценкой нет, следовательно, критерий оптимальности выполнен. Проверим решение с помощью метода потенциалов (табл. 10). Примем a1 = 0, тогда bj = cij – ai (для заполненных клеток). Если найденное решение справедливо, то во всех пустых клетках таблицы Δij = cij – (ai + bj ) ≥ 0, и Δij = 0 в заполненных клетках. Получим следующую таблицу (в скобках показаны оценки клеток): Таблица 9 10 (0) 300 20 (0) 400 32 (4) - 12 (5) - 50 (33) - 25 (0) 600 21 (13) - 18 (0) 200 50 (24) - 25 (20) - 15 (0) 0 23 (0) 200 21 (1) - 30 (0) 100 40 (2) - Условие Δij ≥ 0 выполняется, следовательно, решение верное. Таблица 10 10 300 20 400 32 - 12 - 50 - 25 600 21 - 18 200 50 - 25 - 15 - 23 200 21 - 30 100 40 - Суммарные затраты на перевозку составляют: Решение задачи нелинейного программирования Определить экстремум целевой функции вида F = c11x12+c22x22+c12x1x2+b1x1+b2x2 при условиях a11x1+a12x2<=>p1 a21x1+a22x2<=>p2 . Данные располагаются в табл. 11. Найти стационарную точку целевой функции и исследовать ее (функцию) на выпуклость (вогнутость) в окрестностях стационарной точки. Составить функцию Лагранжа. Получить систему неравенств в соответствии с теоремой Куна-Таккера. Используя метод искусственных переменных составить симплекс-таблицу и найти решение полученной задачи линейного программирования. Дать ответ с учетом условий дополняющей нежёсткости. Таблица 11 Целевая функция имеет вид: Ограничения: Определим относительный максимум функции. Для этого необходимы координаты стационарной точки Получили стационарную точку (1.6;4.4). Исследуем стационарную точку на максимум, для чего и определим вогнутость функции f. Условия выполняются, следовательно целевая функция является строго вогнутой в окрестности стационарной точки. Составим функцию Лагранжа: А) Перепишем систему А: A1) A2) перепишем систему Б: Б2) Решим систему А2 с помощью метода искусственных переменных. Вводим псевдоцелевую функцию базисные переменные: y1, y2, w1, w2 свободные переменные: x1, x2, v1, v2, u1, u2 Решаем эту задачу симплекс-методом с помощью таблиц и небольшой программы на языке Си, текст которой приведён в Приложении 1. Таблица 12 1 0.5 2 0.5 -0.5 -0.25 1 0.5 0 0 -1 -0.5 0 0 8 0.25 -0.5 0.25 2 -0.125 1 0.25 1 0 0 -0.25 -1 0 7 -0.5 1 -0.5 1 0.25 0 -0.5 0 0 0 0.5 0 0 5 0 0 0 1 0 0 0 0 0 0 0 0 0 9M 0.75M -1.5M 0.75M -1.5M -0.375M -2M 0.75M -1M 0M 1M -0.75M 1M 0M Таблица 13 0.5 1.1 0.5 0.03333 -0.25 0.1333 0.5 0.1667 0 0.1333 -0.5 -0.03333 0 -0.1333 8.25 4.4 0.25 0.1333 1.875 0.5333 1.25 0.6667 1 0.5333 -0.25 -0.1333 -1 -0.5333 6.5 -5.5 -0.5 -0.1667 1.25 -0.6667 -0.5 -0.8333 0 -0.6667 0.5 0.1667 0 0.6667 5 -4.4 0 -0.1333 1 -0.5333 0 -0.6667 0 -0.5333 0 0.1333 0 0.5333 9.75M 8.25M 0.75M 0.25M -1.875M 1M -1.25M 1.25M -1M 1M 0.25M -0.25M 1M -1M Таблица 14
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||