Создан заказ №1889471
31 марта 2017
Найти графически оптимальное решение линейного программирования Найти опорное и оптимальное решение задачи методом пересчёта элементов симплексной таблицы х1+3х2≤102х1+х2≤6х1+2х2≤3х1+4х2≥4 х1
Как заказчик описал требования к работе:
Выполнить контрольную по программированию за 2 дня в двух вариантах. Пишите сразу сколько будет стоить контрольная.
Фрагмент выполненной работы:
Найти графически оптимальное решение линейного программирования.
Найти опорное и оптимальное решение задачи методом пересчёта элементов симплексной таблицы
х1+3х2≤102х1+х2≤6х1+2х2≤3х1+4х2≥4
х1, х2≥0
L=4х1+2х2→max
Решение.
Строим область допустимых решений задачи.
В прямоугольной декартовой системе координат строим прямую: х1+3х2=10 (L1), соответствующую ограничению (1).
Х1
4 7
Х2
2 1
Находим какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений первого неравенства. (работа была выполнена специалистами Автор 24) Для этого достаточно, координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Т.к. прямая L1 не проходит через начало координат, подставляем координаты точки О(0,0) в первое ограничение 0+3*0=0≤10. Получаем строгое неравенство 10>0. След., точка О лежит в полуплоскости решений.
Аналогично строим оставшиеся прямые и соответствующие им области решений:
2х1+х2=6 (L2),
Х1
0 2
Х2
6 2
х1+2х2=3 (L3),
Х1
1 3
Х2
1 0
х1+4х2=4 (L4),
Х1
0 4
Х2
1 0
Заштрихованная область есть область допустимых решений.
Строим вектор нормали линий уровня n=(4;2) и одну из этих линий, например, 4х1+2х2=0. Т.к. решается задача на отыскание максимума целевой функции, то линию уровня передвигаем в направлении нормали до опорной прямой.
4х1+2х2=0
Х1
0 -1
Х2
0 2
Эта прямая проходит через точку Х* пересечения прямых соответствующих первому и третьему неравенству. Определим координаты Х*=L3∩L4.Решая систему х1+2х2=3х1+4х2=4, х1=3-2х22х2=1, х1=2х2=1/2, ,
Получаем Х*=(2;1/2)
Вычисляем L(X*)=4*2+2*1/2=9
Решение:
max L(X*)=9 при Х*=(2;1/2)
23114003789045n=(4;2)=(1100;900)
00n=(4;2)=(1100;900)
24257014706600016014704043045Х*
00Х*
-196068164220700-584835177546000767714362859412725404126230105346540633457696433947160769643389953546824904804410-422910376618500-3562353395531-46101032232600057150031191203
3
202882545523153
3
-1466854191000118751345612051
01
-175260422910-422910-914400
Х1
Х2
L1
L2
L3
L4
00
Х1
Х2
L1
L2
L3
L4
163855245523152
2
58483517741906
6
43815287083513906528327350058166040373301
01
56578536188652
2
380936545567607
7
250825045567604
4
2. Приведём задачу линейного программирования к каноническому виду.
Неравенства соответствующие функциональным ограничениям, преобразуем в равенства, введя в каждое из них по одной вспомогательной переменной (в первые три неравенствам прибавить вспомогательную переменную, в четвёртом отнять), в целевую функцию эти переменные войдут с нулевыми коэффициентами (вспомогательные переменные могут принимать только неотрицательные значения).
х1+3х2+х3=102х1+х2+х4=6х1+2х2+х5=3х1+4х2-х6=4
х1, х2, х3, х4, х5, х6≥0
L=4х1+2х2+0 х3+0 х4+0 х5+0 х6→max
Найдём базисное опорное решение:
Заполним таблицу
x1 x2 x3 x4 x5 x6 bj
1 3 1 0 0 0 10
2 1 0 1 0 0 6
1 2 0 0 1 0 3
1 4 0 0 0 -1 4
Найдём базисное опорное решение, для этого заполним новую таблицу:
1-я строка: из первой строки вычтем четвертую умноженную на 3/4;
2-я строка: из второй строки вычитаем четвертую умноженную на 1/4;
3-я строка: из третьей строки вычитаем четвертую умноженную на 2/4;
4-я строка: 4-ю строку разделим на 4;
Базис cj Cj
4
A1 2
A2 0
A3 0
A4 0
A5 0
A6 План
B Qi
А3 0 1/4 0 1 0 0 3/4 7 28
А4
0 7/4 0 0 1 0 1/4 5 20/7
←А5 0 1/2 0 0 0 1 1/2 1 2
А2
2 1/4 1 0 0 0 -1/4 1 4
∆j -7/2 ↑ 0 0 0 0 -1/2 2
Векторы А3, А4, А5, А2 образуют базис трехмерного векторного пространства, след., переменные х3, х4, х5, х2 являются базисными.
Полагая, что свободные переменные х1=0, х6=0, получим первоначальное опорное решение Х0=(0; 1; 7; 5; 1; 0).. Соответствующее значение целевой функции L(x)=2
Проверим первоначальное опорное решение на оптимальность.
Вычисли оценки векторов Аi, используя формулы , j=1,6 (перемножим соответствующие элементы столбцов сi/cj и Аj, результаты сложим, а затем из полученного значения вычтем сj), и оценку столбца свободных членов
∆1=0∙1/4+0∙7/4+ 0∙1/2+2∙1/4-4=-7/2
∆6=0∙3/4+0∙1/4+ 0∙2/4+ 2∙(-1/4)-0=-1/2
Оценки базисных векторов равны нулю.
Проверим критерий оптимальности опорного плана задачи линейного программирования: условие ∆j<0 выполняется для векторов А1, А6, а значит, первоначальный опорный план не является оптимальным.
Чтобы улучшить план, следует ввести в базис вектор, имеющий наименьшую отрицательную оценку ∆j . Из значений ∆1, ∆6 минимальной оценкой является ∆1=-7/2, след., столбец, соответствующий оценке, ∆1 является направляющим, т.е...Посмотреть предложения по расчету стоимости
Заказчик
заплатил
заплатил
200 ₽
Заказчик не использовал рассрочку
Гарантия сервиса
Автор24
Автор24
20 дней
Заказчик принял работу без использования гарантии
1 апреля 2017
Заказ завершен, заказчик получил финальный файл с работой
5
Найти графически оптимальное решение линейного программирования
Найти опорное и оптимальное решение задачи методом пересчёта элементов симплексной таблицы
х1+3х2≤102х1+х2≤6х1+2х2≤3х1+4х2≥4
х1.docx
2017-04-04 12:30
Последний отзыв студента о бирже Автор24
Общая оценка
5
Положительно
Толковый Автор. Работу сопровождает , растолковывает то , что не понятно. Спасибо!
Хочешь такую же работу?
300 ₽
