Решить эту задачу двумя методами – графическим и симплекс методом. Эти методы подробно рассмотрены в работе «Бакулева Скворцов Хрюкин Методы оптимизации.pdf»
Проверить полученные результаты путем решения задачи средствами программы Excel. Применение программы Excel для решения указанных задач рассмотрено в методичках (папка «Средства Excel»).
Задание_2.
maxF=x1+2x2
3x1-2x2≤6-x1+2x2≤43x1+2x2≤12; x1,x2≥0.
Решение
Найдем решение задачи, используя ее геометрическую интерпретацию.
Для этого в неравенствах системы ограничений перейдем к равенствам и построим соответствующие прямые:
3x1-2x2=6-x1+2x2=43x1+2x2=12; x1=0, x2=0, x1, x2 -целые
Прямые будем строить по двум точкам:
3x1-2x2=6 : 1) x1=0; x2=6-3x1-2=6-3∙0-2=-3; 0; -32) x2=0; x1=6+2x23=6+2∙03=2; 2; 0
-x1+2x2=4 : 1) x1=0; x2=4+x12=4+02=2; 0; 22) x2=0; x1=2x2-4=-4; -4; 0
3x1+2x2=12 : 1) x1=0; x2=12-3x12=6; 0; 62) x2=0; x1=12-2x23=4; 4; 0
Чтобы определить расположение соответствующей полуплоскости относительно граничной прямой, подставим координаты какой-либо точки в левую часть каждого неравенства. Так, например, подставим координаты точки O0;0 в левую часть первого ограничения: 3∙0-2∙0≤6. Так как координаты этой точки удовлетворяют первому неравенству, следовательно, данная полуплоскость включает начало координат.
Координаты точки O0;0 удовлетворяют второму неравенству -1∙0+2∙0≤4, а также третьему 3∙0+2∙0≤12, это значит, что полуплоскости включат начало координат.
Штриховкой отметим найденные полуплоскости. Так же построим область допустимых решений ограничений x1≥0 и x2≥0.
Областью допустимых решений (ОДР) является закрашенная область, представленная пятиугольником ABCDO.
Найдем в этой области оптимальное решение.
maxF=x1+2x2
Построим вектор c, координаты которого равны частным производным функции F по переменным x1 и x2: c=∂F∂x1;∂F∂x2=1;2. Этот вектор является градиентом функции fx=x1+2x2 и указывает направление возрастания ее значений.
Зафиксируем какое-нибудь значение функции F=const, получим линейное уравнение x1+2x2=const, графиком которого является прямая, называемая линией уровня
. Градиент перпендикулярен линиям уровня. Построим линию уровня целевой функции для значения F=0:
x1+2x2=0
Определим координаты двух точек для построения прямой:
1) x1=0; x2=0
1) x1=4; x2=-2
Перемещаем линию уровня параллельно самой себе в направлении градиента до конца ОДР, то есть до точки B, координаты которой находятся как решение системы уравнений:
3x1+2x2=12-x1+2x2=4
Из второго выразим x1 и подставим в первое уравнение
x1=2x2-4
32x2-4+2x2=12
6x2-12+2x2=12
8x2=24
x2=3
Тогда x1=2x2-4=2∙3-4=6-4=2
Получаем оптимальное решение задачи: x1*=2 и x2*=3. Максимальное значение целевой функции при этом составит Fmax=x1+2x2=2+2∙3=2+6=8.
Решим задачу симплексным методом.
Построим начальный опорный план задачи. Для этого приведем задачу к каноническому виду, добавив к левым частям системы ограничений дополнительные переменные xj≥0 при j=4, 6. В целевую функцию дополнительные переменные вводятся с коэффициентами, равными нулю.
Получаем задачу в канонической форме записи:
Fx=x1+2x2+0∙x3+0∙x4+0∙x5→max
3x1-2x2+x3=6-x1+2x2+x4=43x1+2x2+x5=12; xj≥0 j=1, 5
Анализируя каноническую модель задачи, замечаем, что каждая из переменных x3,x4,x5 входит только в одно из уравнений системы, т. е. эти переменные входят в систему ограничений в предпочтительном виде и их можно взять в качестве базисных. Переменные x1,x2 будут свободными.
Составляем симплекс-таблицу:
БП 1 2 0 0 0 Bi
biaip
x1
x2
x3
x4
x5
x3
3 -2 1 0 0 6 -
x4
-1 2 0 1 0 4 42=2
x5
3 2 0 0 1 12 122=6
F
-1 -2 0 0 0 0
Рабочая часть таблицы, начиная со 2-го столбца и 3-й строки, содержит элементы расширенной матрицы, над которыми будут производиться преобразования с целью получения оптимального плана
Задать вопрос
на новый заказ в Автор24.
