Лабораторная работа по транспортным средствам

Лабораторная работа №1. Решение задач линейного программирования Графический метод основан на геометрической интерпретации экономических задач, которая дает возможность наглядно представить их структуру. Задачу линейного программирования с двумя переменными всегда можно решить графически. Однако уже в трехмерном пространстве такое решение усложняется, а в пространствах, размерность которых больше трех, графическим методом может быть решена задача линейного программирования, система ограничений которой содержит n-неизвестных и m-линейно независимых уравнений, причем n-m≤2. Задача 1. Решите графическим методом задачу линейного программирования (x_1≥ 0,x_2≥ 0): Исходные данные: Необходимо найти максимальное значение целевой функции Решение: Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Построим уравнение x_1+6x_2= 6 по двум точкам. Для нахождения первой точки приравниваем x_1= 0. Находим x_2= 1. Для нахождения второй точки приравниваем x_2= 0. Находим x_1= 6. Соединяем точку (0;1) с (6;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1·0 + 6·0 — 6 ≤ 0, т.е. x_1+6x_2- 6≥ 0 в полуплоскости выше прямой. Аналогично: Построим уравнение -1/3 x_1+3x_2= -1 по двум точкам: x_1= 0,x_2= -1/3. x_2= 0,x_1= 3. Соединяем точку (0;-1/3) с (3;0) прямой линией. -1/3 x_1+3x_2+1≥ 0 в полуплоскости ниже прямой. Построим уравнение –x_1+2,5x_2= 2,5 x_1= 0,x_2= 1. x_2= 0,x_1= -2,5. -x_1+2,5x_2- 2,5≤ 0 в полуплоскости ниже прямой. Построим уравнение 7x_1+11x_2= 77 x_1= 0,x_2= 7. x_2= 0,x_1= 11. 7x_1+11x_2- 77≤ 0 в полуплоскости ниже прямой. Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений. Рассмотрим целевую функцию задачи F = 3x_1+x_2→ max. Построим прямую, отвечающую значению функции F = 3x_1+x_2= 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (3;1). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией. Прямая F(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (2) и (4), то ее координаты удовлетворяют уравнениям этих прямых: {█(-1/3 x_1+3x_2=-1@7x_1+11x_2=77)┤ Решив систему уравнений, получим: {█(x_1= 9 30/37,@x_2=28/37.)┤ Откуда найдем максимальное значение целевой функции: F(X)= 3∙9 30/37+28/37= 30 7/37. Задача 2. Найти графическим методом оптимальный план задач линейного программирования (х_j≥0). Исходные данные F(X)= 7x_1+x_2+x_3-x_4→max при ограничениях: 5x_1+x_2+x_3+3x_4+x_5=5 -2x_2+4x_3+x_4+x_5=3 x_1-3x_2+5x_3=2 x_1≥ 0,x_2≥ 0,x_3≥ 0,x_4≥ 0,x_5≥ 0 Решение: Расширенная матрица системы ограничений-равенств данной задачи: |■(5&1&1&3&1&5@0&-2&4&1&1&3@1&-3&5&0&0&2)| Приведем систему к единичной матрице методом жордановских преобразований. 1. В качестве базовой переменной можно выбрать x_4. Разрешающий элемент РЭ=1. Строка, соответствующая переменной x_2, получена в результате деления всех элементов строки x_4 на разрешающий элемент РЭ=1. На месте разрешающего элемента получаем 1. В остальных клетках столбца x_2 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы: 2. В качестве базовой переменной можно выбрать x_5. Разрешающий элемент РЭ=-2. Строка, соответствующая переменной x_1, получена в результате деления всех элементов строки x_5 на разрешающий элемент РЭ=-2. На месте разрешающего элемента получаем 1. В остальных клетках столбца x_1 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ -(А∙В)/РЭ СТЭ — элемент старого плана, РЭ — разрешающий элемент (-2), А и В — элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Представим расчет каждого элемента в виде таблицы: 3. В качестве базовой переменной можно выбрать x_3. Разрешающий элемент РЭ=5. Строка, соответствующая переменной x_3, получена в результате деления всех элементов строки x_3 на разрешающий элемент РЭ=5. На месте разрешающего элемента получаем 1. В остальных клетках столбца x_3 записываем нули. Все остальные элементы определяются по правилу прямоугольника. Представим расчет каждого элемента в виде таблицы: Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (5,4,3). Соответствующие уравнения имеют вид: -18/5 x_1-1/5 x_2+x_5= -1/5 14/5 x_1+3/5 x_2+x_4=1 3/5 1/5 x_1-3/5 x_2+x_3=2/5 Выразим базисные переменные через остальные: x_5=18/5 x_1+1/5 x_2-1/5 x_4= -14/5 x_1-3/5 x_2+1 3/5 x_3= -1/5 x_1+3/5 x_2+2/5 Подставим их в целевую функцию: F(X)= 7x_1+x_2+(-1/5 x_1+3/5 x_2+2/5)-(-14/5 x_1-3/5 x_2+1 3/5)= =48/5 x_1+11/5 x_2-1 1/5→ max Система неравенств: 18/5 x_1+1/5 x_2-1/5≥ 0 -14/5 x_1-3/5 x_2+1 3/5≥ 0 -1/5 x_1+3/5 x_2+2/5≥ 0 Приводим систему неравенств к следующему виду: -18/5 x_1-1/5 x_2≤ -1/5 14/5 x_1+3/5 x_2≤1 3/5 1/5 x_1-3/5 x_2≤2/5 F(X)=48/5 x_1+11/5 x_2-1 1/5→ max Упростим систему. -18x_1-x_2≤ -1 14x_1+3x_2≤8 x_1-3x_2≤ 2 F(X)= 48x_1+11x_2-6→ max Поскольку мы упростили систему, домножив на 5, то полученное значение целевой функции необходимо будет разделить на 5. Решаем графически: Построим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами (полуплоскости обозначены штрихом). Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи. Обозначим границы области многоугольника решений. Построим прямую, отвечающую значению функции F = 48x_1+11x_2-6 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (48;11). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией. Прямая F(x) = const пересекает область в точке B. Так как точка B получена в результате пересечения прямых (2) и (4), то ее координаты удовлетворяют уравнениям этих прямых: 14x_1+3x_2=8 x_1=0 Решив систему уравнений, получим: x_1= 0,x_2= 2 2/3 При этом значения базисных переменных будут следующие: x_3= -1/5·0+3/5·2 2/3+2/5=2 x_4= -14/5·0-3/5·2 2/3+1 3/5=0 x_5=18/5·0+1/5·2 2/3-1/5=1/3 Найдем максимальное значение целевой функции: F^* (X)= 48∙0 + 11∙2 2/3- 6 = 23 1/3 Разделив на 5, получим F(X)= 23 1/3:5=4 2/3 Лабораторная работа №2. Технология решения задач линейного программирования с помощью поиска решений в среде EXCEL Решим задачи из лабораторной работы № 1 в среде Excel с помощью надстройки «Поиск решения» Задача 1. Необходимо найти максимальное значение целевой функции F = 3x_1+x_2→ max, при системе ограничений: x_1+6x_2≥6,(1) -1/3 x_1+3x_2≥-1,(2) -x_1+2,5x_2≤2,5,(3) 7x_1+11x_2≤77,(4) x_1≥ 0,(5) x_2≥ 0,(6) Решение: Запишем систему ограничений так, чтобы знак ограничений был одинаковый в каждом неравенстве: x_1+6x_2≥6,(1) -1/3 x_1+3x_2≥-1,(2) x_1-2,5x_2≥-2,5,(3) -7x_1-11x_2≥-77,(4) Создаем на листе Excel такую таблицу (рис. 1): Рисунок 1 В ячейках А5:А8 запишем коэффициенты при х_1, в ячейках В5:В8 – коэффициенты при х_2, в ячейках D5:D8 – значения параметров С (правые части неравенств). В ячейках А2, В2 указаны соответственно значения коэффициентов при х_1 и х_2 в целевой функции. В ячейки А3 и В3 будут помещены оптимальные значения вектора Х =(Х_1,Х_2), в ячейку С3 — оптимальное значение целевой функции, формула в которой записывается так: С3=СУММПРОИЗВ(A2:B2;A3:B3) Колонка С5:С8 используется для записи произведений полученных оптимальных значений вектора Х=(Х_1,Х_2) и коэффициентов в ограничениях. Таким образом будет проверяться соответствие этих значений ограничениям по параметрам С. Для записи формул в ячейках С5:С8 в ячейку С5 записываем: С5=СУММПРОИЗВ($A$3:$B$3;A5:B5) и копируем эту формулу на оставшийся диапазон С6:С8. В ячейках С5:С8 ожидаемо появились нули. Исходные данные записаны, приступаем к решению. Запускаем надстройку MS Excel «Поиск решения» (вкладка «Сервис» — «Поиск решения») (рис. 2): Рисунок 2 В открывшемся окне вводим следующее (рис. 3): Указываем целевую ячейку – С3, указываем, что ищем максимум целевой функции, в качестве изменяемых ячеек записываем $A$3:$B$3, уточняем ограничения: во-первых, неотрицательность значений х_1 и х_2, а во-вторых, то, что значения ячеек С5:С8 должны быть больше значений D5:D8. Нажимаем кнопку выполнить и получаем результат (рис. 4): Рисунок 3 Как видно из рисунка 4, в ячейках А3 и В3 получили оптимальные значения переменных х_1 и х_2, а в ячейке С3 – максимум целевой функции. Результаты, полученные с помощь. надстройки Excel, соответствуют результатам, полученным графическим методом в лабораторной работе № 1. Задача 2. Найти оптимальный план задач линейного программирования (х_j≥0). Исходные данные F(X)= 7x_1+x_2+x_3-x_4→max при ограничениях: 5x_1+x_2+x_3+3x_4+x_5=5 -2x_2+4x_3+x_4+x_5=3 x_1-3x_2+5x_3=2 x_1≥ 0,x_2≥ 0,x_3≥ 0,x_4≥ 0,x_5≥ 0 Решение: Создадим в среде Excel таблицу, аналогичную представленной на рис. 1, и заполним ячейки соответствующими значениями (рис. 5): проставим коэффициенты перед переменными в целевой функции (ячейки А2:Е2), заполним ячейки А5:Е7 коэффициентами перед переменными в ограничениях; внесем в столбец G5:G7 значения свободных членов в ограничениях. Целевая функция теперь будет в ячейке F3. Формулы в рассчитываемых ячейках останутся такими же, как в предыдущей задаче, только охватят больший диапазон ячеек. Рисунок 5 Нажимаем на «Поиск решения», записываем ячейку целевой функции (F3), изменяемые значения (А3:Е3) и вводим ограничения: значения переменных должны быть неотрицательны, значения ячеек F5:F7 должны быть соответственно равны значениям в столбце G5:G7 (рис. 6). Рисунок 6 Нажимаем «Выполнить», подтверждаем сохранение решения и получаем следующее решение (рис. 7): Рисунок 7 Как видно, полученные значения переменных и целевой функции совпадают с теми, которые были получены в предыдущей лабораторной работе с помощью графического метода.