Решить оптимизационную задачу с линейной статической моделью графически, симплекс-методом, привести таблицу с решением средствами Excel, графическую модель, показать возможности «улучшения» оптимального решения, чувствительность параметров модели.
F = 7x1+9x2 → max2x1+5x2≤20,4x1+3x2≤48,
x1 ≥ 0,x2 ≥ 0.
Решение
Необходимо найти максимальное значение целевой функции F = 7x1+9x2 при системе ограничений:
2x1+5x2≤20, (1)4x1+3x2≤48, (2)x1 ≥ 0,(3)x2 ≥ 0, (4)
Строим область допустимых решений, т.е. решим графически систему неравенств. Для этого построим каждую прямую и определим полуплоскости, заданные неравенствами.
Строим прямую 2x1+5x2 = 20.
х1 0 10
х2 4 0
Определяем полуплоскость, которая задается неравенством. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости:2 ∙ 0 + 5 ∙ 0 - 20 ≤ 0, т.е. 2x1+5x2 - 20≤ 0 в полуплоскости ниже прямой.
Строим прямую 4x1+3x2 = 48.
х1 0 12
х2 16 0
Определяем полуплоскость, которая задается неравенством. Выбираем точку (0; 0), определяем знак неравенства в полуплоскости:4 ∙ 0 + 3 ∙ 0 - 48 ≤ 0, т.е. 4x1+3x2 - 48≤ 0 в полуплоскости ниже прямой.
Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.Рассмотрим целевую функцию задачи F = 7x1+9x2 → max.
Строим прямую, которая отвечает значению функции F = 7x1+9x2 = 0. Вектор-градиент, который составлен из коэффициентов целевой функции, указывает направление максимизации F(X). Начало вектора – точка (0; 0), конец – точка (7; 9)
. Двигаем эту прямую параллельным образом. Т.к. нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области.
Прямая F(x) = const пересекает область в точке, полученной в результате пересечения прямых (4) и (1), следовательно, ее координаты удовлетворяют уравнениям этих прямых:
x2=02x1+5x2=20
Решив систему уравнений, получаем: x1 = 10, x2 = 0.
Откуда находим максимальное значение целевой функции:
F(x) = 7∙10 + 9∙0 = 70.
Решим задачу симплекс-методом с использованием симплекс-таблицы.
Для построения опорного плана 1 систему неравенств приводим к системе уравнений путем введения дополнительных переменных (переходим к канонической форме).
В 1-м неравенстве смысла (≤) введем неотрицательную базисную переменную x3, во 2-м неравенстве смысла (≤) введем неотрицательную базисную переменную x4.
2x1+5x2+x3 = 204x1+3x2+x4 = 48
Матрица коэффициентов A = a(ij) этой системы уравнений принимает вид:
A = 2 5 1 0
4 3 0 1
Решаем систему уравнений относительно базисных переменных: x3, x4
Полагаем, что свободные переменные равны 0, получим опорный план 1: X0 = (0,0,20,48).
БП B x1 x2 x3 x4
x3 20 2 5 1 0
x4 48 4 3 0 1
∆ 0 -7 -9 0 0
Переходим к симплекс-преобразованиям.
Ключевой столбец выбираем по наименьшему отрицательному элементу индексной строки.
Ключевую строку выбираем по наименьшему отношению частного от деления: bi / aij.
Ключевой элемент находится на пересечении ключевого столбца и ключевой строки.
Все вычисления сводим в симплекс-таблицы.
Переход от одной симплекс-таблицы к другой проводим по правилу прямоугольника.
Для этого выбираем из старого плана четыре числа, расположенные в вершинах прямоугольника и всегда включающие ключевой элемент КЭ.
НЭ = СтЭ - (А∙В)/КЭ
СтЭ – элемент старого плана,
КЭ – ключевой элемент,
А и В – элементы старого плана, образующие прямоугольник с элементами СтЭ и КЭ.
БП B x1 x2↓ x3 x4 min
←x3 20 2 5 1 0 4
x4 48 4 3 0 1 16
∆ 0 -7 -9 0 0
БП B x1↓ x2 x3 x4 min
←x2 4 2/5 1 1/5 0 10
x4 36 14/5 0 -3/5 1 90/7
∆ 36 -17/5 0 9/5 0
БП B x1 x2 x3 x4
x1 10 1 5/2 1/2 0
x4 8 0 -7 -2 1
∆ 70 0 17/2 7/2 0
Т.к
Задать вопрос
на новый заказ в Автор24.
