Образец типового расчета
Задача 1. Используя градиентный метод, найти минимум функции при системе ограничений .
Решение Строим область допустимых решений, вектор и одну из линий уровня . Перемещаем линию уровня в направлении, противоположном , так как решается задача на отыскание минимума функции. Опорная прямая проходит в этом случае через точку А, координаты которой найдём из решения системы
Итак, . Вычисляем . Замечание. В действительности от вида области допустимых решений и целевой функции задача ЛП может иметь единственное решение, бесконечное множество решений или не иметь ни одного решения.
Задача 2. Составить математическую модель и решить симплекс-методом следующую задачу. Строительное управление ведет капитальный ремонт жилых домов. Перегородки внутри этих домов могут быть изготовлены гипсобетонными или каркасными. Ресурсы на месяц заданы в табл. 7.7 (потребность на 1 м2 площади перегородок). Таблица 7.7
Рассчитать общее количество м2 как каркасных, так и гипсобетонных перегородок, которые следует возвести в текущем месяце, чтобы общая их площадь была наибольшей, если строительное управление имеет в наличии гипсобетона – 300 м3; пиломатериалов – 200 м3; сухой штукатурки – 8000 м3; трудоресурсов – 2000 чел/дней.
Решение Составим математическую модель задачи. Пусть требуется возвести каркасных и гипсобетонных перегородок. Из условия на это уйдёт: гипсобетона , пиломатериалов , сухой штукатурки , трудоресурсов . Учитывая лимиты материалов и трудоресурсов, составляем систему ограничений – неравенств: Для решения задачи симплекс-методом вводим дополнительные переменные: Полагаем . Принимаем , в качестве свободных переменных, , , , в качестве базисных. Начальный опорный план имеет вид: , . Составляем симплекс-таблицу (в сокращённой форме), соответствующую начальному опорному плану. Обратим внимание, что коэффициенты при свободных переменных пишутся с противоположным знаком.
столбца: , , . Элемент ведущего столбца, для которого отношение минимально ( в нашем случае 0,25) объявляем ведущим. Строка, в которой находится элемент, также называется ведущей и помечается стрелкой слева. Теперь запишем правила перехода к новой симплекс-таблице, соответствующие приведённому выше алгоритму симплекс-метода: 1. Базисная переменная, находящаяся в ведущей строке, и свободная переменная, находящаяся в ведущем столбце, меняются местами. 2. Ведущий элемент заменяется величиной, ему обратной. 3. Все элементы ведущей строки (включая свободный член), кроме ведущего элемента, заменяются их отношениями к ведущему элементу. 4. Все элементы ведущего столбца (кроме ведущего элемента) заменяются взятыми с обратными знаками их отношениями к ведущему элементу. 5. Остальные элементы заменяются по «правилу 4 элементов»: любой такой элемент умножается на ведущий и из произведения вычитается произведение двух других элементов, составляющих с первыми вершины прямоугольника, после чего результат делится на ведущий элемент. Проводя вычисление по этим правилам, получаем следующую симплекс-таблицу:
Аналогично составляем следующую симплекс-таблицу:
, . Задача 3. Максимизировать функцию Z=x1+2x2-2x3 при ограничениях Решение Преобразуем исходную задачу линейного программирования к канонической. Для этого введём в ограничения дополнительные неотрицательные переменные. А именно, в первое неравенство – переменную x4 со знаком «+», во второе – x5 со знаком «-». Система ограничений примет вид: Эту систему запишем в векторной форме: A1x1+A2x2+A3x3+A4x4+A5x5=B, где , , , , , . Очевидно, что в данной системе ограничений отсутствует единичный базис. Это означает, что среди векторов Aj нет трёх необходимых единичных векторов, которые должны образовывать базис в R3. Однако заметим, что вектор A4 является частью базиса. Ему соответствует базисная переменная x4. Необходимо найти ещё два единичных вектора. Для этого применим метод искусственного базиса. Введём искусственные переменные в те уравнения ограничений, в которых не присутствует базисная переменная x4, и построим следующую вспомогательную задачу (ВЗ):
F=-w1-w2®max где w1, w2 – искусственные переменные. Система ограничений ВЗ в векторном виде имеет вид: A1x1+A2x2+A3x3+A4x4+A5x5+A6w1+A7w2=B, где векторы Aj , j=1,2,3,4,5 определяются так же, как и выше, а и . Таким образом, вектора A4, A6, A7 образуют базис в R3 и им соответствуют базисные переменные (БП) – x4, w1, w2. Все остальные переменные, а именно x1, x2, x3, x5 объявляются свободными (СП). Далее к ВЗ применяем обычный симплекс-метод. Как и раньше (см. § 5. 1) начальный опорный план получается, если присвоить свободным переменным значения, равные нулю. При этом базисные переменные принимают значения, равные числам в соответствующей строке столбца свободных коэффициентов В, то есть x1=x2=x3=x5=0¸ а x4=8, w1=4, w2=12. Строим симплекс-таблицу, соответствующую начальному опорному плану:
С этой таблицей проводим необходимые преобразования (см. §5.1) симплекс-метода, пока не получим оптимальную симплекс-таблицу или не получим неразрешимость. В нашем случае, мы уже на втором шаге будем иметь такую симплекс-таблицу:
Эта таблица будет оптимальной для ВЗ. При этом все искусственные переменные стали свободными и max F=0. Вычеркивая столбцы, соответствующие искусственным переменным и последнюю строку, и приписывая новую строку оценок с использованием исходной целевой функции Z(X), получим начальную симплекс-таблицу для исходной задачи ЛП:
Проанализировав последнюю таблицу, делаем вывод, что исходная задача ЛП не имеет решения в силу неограниченности целевой функции. Задача 4. Для данной задачи составить двойственную, решить ее графическим методом и, используя вторую теорему двойственности, найти решение исходной задачи: , . Решение приведено на стр. 6 – 7 данной методички.
Задача 5. Решить транспортную задачу (табл. 7.8). Таблица 7.8
Решение приведено на стр. 13 – 17 данной методички.
Популярное: Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (352)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |