Методы оптимальных решений

Подробное решение задач по теме "Методы оптимальных решений". Три задачи ...

нет

строка u2, столбец ХБ: 32∙3-5∙-3232=92+15232=242∙23 =8 ,строка u2, столбец х1: 32∙0-0∙-3232=0,строка u2, столбец u1: 32∙0-1∙-3232=32÷32 =1 ,строка u2, столбец u2: 32∙1-1∙-3232 =32÷32 =1 ,строка u2, столбец u3: 32∙12--12∙-3232 =34-34÷32=0÷32 =0 ,строка u2, столбец w1: 32∙(-1)-0∙-3232 =-32÷32 =-1 .последняя строка, столбец ХБ: 32∙(4-М2-5∙-1232=6-3М4+5232=-3М432+17232 =-М2+173 ,последняя строка, столбец х1: 32∙0-0∙-1232=0,последняя строка, столбец u1: 32∙0-1∙-1232 =12∙23 =13 ,последняя строка, столбец u2: 32∙0-0∙-1232=0,последняя строка, столбец u3: 32∙12--12∙-1232=34-14÷32=24∙23 =13 ,последняя строка, столбец w1: 32∙М-0∙-1232=3М2∙23 =М.В последней строке (столбец ХБ не рассматривается) отрицательные значения отсутствуют, значит найдено оптимальное решение. Выпишем оптимальные значения переменных. В последней таблице в столбце БП были переменные х1, х2 и u2, поэтому им присваиваем соответствующие значения из столбца ХБ. Остальные переменные будут равны 0:х1=103х2=103u1=0u2=8u3=0w1=0.Искусственная переменные w1=0, поэтому ее можно вычеркнуть:х1=103х2=103u1=0u2=8u3=0.Все ui (даже если они не равны 0) тоже вычеркиваем. Итак, оптимальное решение следующее:х1=103х2=103zmax=х1+х2=103+103=203=6,667.Ответ: при х1=103 и х2=103 целевая функция zmax=х1+х2 достигает своего максимального значения, равного 6,667. Результаты решения поставленной задачи графическим и симплексным методом совпали.Решить графическим и симплексным методом задачу линейного программирования: min Решение1. Графический метод1.1 На плоскости координат (оси х1 и х2) построим прямые ограничений (рис. 3):прямая -2х1+х2=2,при х1=0 х2=2,при х2=0 х1=2-2=-1,проводим прямую через точки (0;2) и (-1;0);прямая 3х1-4х2=11,при х1=0 х2=11-4=-234,при х2=0 х1=113=323,проводим прямую через точки (0;-234,) и (323,;0);прямая 3х1+4х2=19,при х1=0 х2=194=434при х2=0 х1=193=613,проводим прямую через точки (0; 434) и (613,;0);прямые х1=0 и х2=0 - это оси координат.Строим прямые на плоскости координат и заштриховываем области согласно знакам неравенств из данной системы ограничений. Таким образом, область допустимых решений можно обозначить многоугольником, который выше точек А и В (рис. 3).Рис. 3 - Построение области допустимых решений1.2 На построенном графике строим произвольную линию уровня целевой функции , например, равной 12 (рис. 4).прямая 3х1+4х2=12,при х1=0 х2=3,при х2=0 х1=4,проводим прямую через точки (0;3) и (4;0);Проводим прямую, параллельную прямой 3х1+4х2=12 таким образом, чтобы она проходила в минимальной точке закрашенной области. Такая прямая проходит через точки А и В (совпадает с прямой, построенной по третьему уравнению). Из построения определяем координаты точек А и В (рис. 4).Рис. 4 - Поиск оптимального решенияКак видно из графика, точка А имеет координаты (1; 4). Таком образом: х1=1,х2=4,zmax=3х1+4х2=3+16=19.Как видно из графика, точка В имеет координаты (5; 1). Таком образом: х1=5,х2=1,zmin=3х1+4х2=15+4=19.2. Симплексный метод2.1 Проверим систему ограничений на каноничность:все хi 0 - условие неотрицательности выполнено;все ограничения должны быть уравнениями. Чтобы выполнить требования данного условия добавим в систему ограничений дополнительные переменные ui со знаком «+» в неравенства, где присутствует знак «≤», и ui со знаком «-» в неравенства со знаком «». Знаки неравенств заменяем на знак равенства:-2х1+х2+u1=2 3х1-4х2+u2=11 3х1+4х2-u3=19 х1≥0, х2≥0, u1≥0, u2≥0, u3≥0 условие о поиске задачи на максимум - не выполняется. Поэтому умножаем целевую функцию на -1 и меняем min на max:zmax=-3х1-4х2→max 2.2 Проверим на предпочтительность уравнения-ограничения: все правые части уравнений должны быть больше ноля - условие выполняется. Так же в левых частях уравнений все ui должны быть со знаком «+»:-2х1+х2+u1=2 - уравнение предпочтительно, преобразования не требуются;3х1-4х2+u2=11 - уравнение предпочтительно, преобразования не требуются;3х1+4х2-u3=19 - не предпочтительно. Добавим искусственную переменную w1 со знаком «+» и добавим ее в целевую функцию с коэффициентов -М (где М - бесконечно большое число):3х1+4х2-u3+w1=19,z=-3х1-4х2-Mw1→max.Таким образом, мы получили следующую целевую функцию и систему ограничений:z=-3х1-4х2-Mw1→max-2х1+х2+u1=2 3х1-4х2+u2=11 3х1+4х2-u3+w1=19 х1≥0, х2≥0, u1≥0, u2≥0, u3≥0, w1≥0 2.3 Построим первую симплекс-таблицу (таблица 6). Количество строк равно количеству уравнений, увеличенному на 3, а количество столбцов равняется количеству переменных, включая дополнительные переменные