Скачать 29.25 Kb.
|
Вариант 12 Задача 1 стр.3 Задача 2 стр.7 Задача 3 стр.11 Задача 1 Используя графический метод решения линейных программ, найти максимальное и минимальное значение линейной функции на одном и том же множестве планов. L ![]() х1 + 2х2 ≤ 10 3х1 - 5х2 ≤ 8 5х1 + 3х2 ≥ 20 х1 ≥ 2 Решение: Построим область L допустимых решений. Заменим в каждом неравенстве задачи знак неравенства на знак равенства. Получим уравнения прямых: х1 + 2х2 = 10 (I) 3х1 - 5х2 = 8 (II) 5х1 + 3х2 = 20 (III) х1 = 2 (IV) Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат. Для нахождения экстремума функции L=2х1+3х2, строим разрешающую прямую, приравнивая линейную форму нулю: L=0. Отсюда получаем: прямая (I) определена уравнением х1 + 2х2 = 10, следовательно при х1 = 0, х2 = 5; х2 = 0, х1 = 10, таким образом получаем: прямая (I) – точки (0;5) и (10;0) - градиент целевой функции; прямая (II) определена уравнением 3х1 - 5х2 = 8, следовательно при х1 = 0, х2 = -1,6; х2 = 0, х1 = 2,7, таким образом получаем: прямая (II) – точки (0;-1,6) и (2,7;0); прямая (III) определена уравнением 5х1 + 3х2 = 20, следовательно при х1 = 0, х2 = 6,7; х2 = 0, х1 = 4, таким образом получаем: прямая (III) – точки (0;6,7) и (4;0); прямая (IV) определена уравнением х1 = 2, следовательно х2 = 0, прямая (IV) проходит через точку х1 = 2 параллельно оси 0х2. Данные вычисления изобразим на рисунке 1. ![]() + ![]() ![]() ![]() + ![]() + (II) + 1+ ![]() + 1 (III) (I) qrad Х1 + (IV) Рисунок 1. Графическое решение задачи ЛП Определим ОДР. Для этого, подставим точку (0;0) в исходное ограничение (I), получим 0≤10, что является истинным неравенством, поэтому стрелкой обозначим полуплоскость, содержащую точку (0;0), т.е. расположенную левее и ниже прямой (1) (рис. 2). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (рисунок 2). Общей областью, разрешенной всеми ограничениями, т.е. ОДР является четырехугольник ABCD. Целевую прямую можно построить по уравнению L = 2х1 + 3х2 Выберем произвольное значение, например, L=3 целевой функции. Прямая 2х1 +3х2 = 15 пересекает ось x1 в точке x1=6 и ось x2 в точке x2=9. Строим вектор ![]() Точка В – это единственная вершина четырехугольника допустимых решений ABCD, через которую проходит целевая прямая, двигаясь по направлению вектора ![]() ![]() ![]() + ![]() ![]() ![]() ![]() ![]() ![]() + В Lmax ![]() ![]() + А (II) + С 1+ D Lmin ![]() ![]() (IV) Рисунок 2. Графическое решение задачи ЛП Определим координаты точки В из системы уравнений прямых ограничений (I) и (IV) х ![]() х1 = 2 (IV) Получили точку B (2;4). Максимальное значение равно L (В) = 2*2 + 3*4 = 16 Т.к., область L определяется как общая часть полуплоскостей, соответствующих неравенствам ограничений (рисунок 2), минимальное значение функция принимает в точке D. Определим координаты точки D из системы уравнений прямых ограничений (II) и (III) 3 ![]() 5х1 + 3 х2 = 20 (IV) Получили точку D (3,5;0,5). Минимальное значение равно L (D) = 2*3,5 + 3*0,5 = 8,5 В результате решения задачи линейного программирования были получены минимум и максимум рассматриваемой функции, вследствие того, что область ограничений представляет собой замкнутый четырехугольник. Таким образом, получили максимальное значение L (В) = 16 и минимальное значение L (D) = 8,5. ^ Lmax = 16, Lmin = 8,5 Задача 2 Построить математическую модель задачи и решить ее средствами Excel. Записать сопряженную задачу. Провести анализ и сделать выводы по полученным результатам. Условия: Для рытья котлована объемом 1380м3 строители получили три экскаватора. Мощный экскаватор производительностью 22,5 м3/ч расходует 10 л/ч бензина. Аналогичные характеристики среднего экскаватора - 10 м3/ч и 4 л/ч, малого – 5 м3/ч и 3 л/ч. Экскаваторы могут работать все одновременно, не мешая друг другу. Запас бензина у строителей ограничен и равен 580 литров. Если рыть котлован только малым экскаватором, то бензина заведомо хватить, но это будет очень долго. Каким образом следует использовать имеющуюся технику, чтобы выполнить работу как можно быстрее? Решение: Определим, для удобства, варианты работ по рытью котлована через: Х1 – рытье котлована мощным экскаватором производительностью 22,5 м3/ч и расходованием бензина 10 л/ч; Х2 - рытье котлована средним экскаватором производительностью 10 м3/ч и расходованием бензина 4 л/ч; Х3 - рытье котлована малым экскаватором производительностью 5 м3/ч и расходованием бензина 3 л/ч. Рассчитаем и введем показатели необходимого количества времени для каждого экскаватора для рытья котлована данным объемом. Таким образом, мощному экскаватору необходимо 61,3 часа (1380/22,5), среднему – 138 часов (1380/10) и малому 276 часов (1380/5). Для наглядности, данные показатели сведем в таблицу:
По данным таблицы построим математическую модель: L(х) = 61,3х1 + 138х2 + 276х3 → min целевая функция ![]() 22,5х1 + 10х2 + 5х3 ≥ 1380 производительность 10х1 + 4х2 + 3х3 ≤ 580 расход бензина х1 ≥ 0, х2 ≥ 0, х3 ≥ 0 условия неотрицательности Средствами Excel, на основе данных, составим таблицы в режиме чисел и формул (приложение).
Полученные результаты
Найденное решение позволяет сделать вывод о том, что вариант Х1 при заданных ограничениях дает оптимальный результат (28 часов), нулевой результат показал вариант Х3, самым долговременным результатом оказался вариант Х2 (75 часов). В тоже время, использование сразу всех трех, либо мощного и среднего вместе экскаваторов, дает более долговременные работы (103 часа). По результатам расчетов составим отчет (приложение). Вывод: Оптимальным вариантом рытья котлована объемом 1380 м3/ч затрачивая минимум времени, является использование мощного и малого экскаваторов. |