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

13.02.17 в 11:29

Задание 1.10

Решить задачи с использованием графического метода:

L(¯x)=x_1+x_2→min при ограничениях

x_1≥0,x_2≥0

Решение

Построим область определения этой задачи. Ограничения x_1,x_2≥0 задают первую координатную четверть плоскости х1Ох2.

Для получения решения графическим методом строим прямые:

I 2x_1+4x_2≤16. Прямая проходит через точки (8; 0) и (0; 4). Для нахождения полуплоскости, соответствующей данному неравенству, берем любую точку, не лежащую на граничной прямой, и подставляем ее координаты в неравенство. Возьмем точку О(0;0): 2*0 + 4*0 ≤ 16, 0≤16 Неравенство выполняется, значит, исходному неравенству соответствует та полуплоскость, которая содержит точку О (0;0).

II -4x_1+2x_2≤8. Прямая проходит через точки (-2; 0) и (0; 4). Возьмем точку О(0;0): -4*0 + 2*0 ≤ 8, 0≤8 Неравенство выполняется, значит, исходному неравенству соответствует та полуплоскость, которая содержит точку О (0;0).

III x_1+3x_2≥9. Прямая проходит через точки (9; 0) и (0; 3). Возьмем точку О(0;0): 0 + 3*0 ≥9, 0≥9. Неравенство не выполняется, значит, исходному неравенству соответствует та полуплоскость, которая не содержит точку О (0;0).

Рис. 1. Графический метод решения задачи

Решением является замкнутый многоугольник ABC. Любая точка этого многоугольника внутри и на границе является решением или рекомендацией допустимой задачи.

Строим вектор C ⃗=(c_1;c_2)=(1; 1). Перпендикулярно к вектору C ⃗ проводим линию уровня F=0.

Параллельным перемещением прямой F=0 вдоль вектора C ⃗ находим крайнюю точку A, в которой целевая функция принимает минимальное значение.

Координаты точки A определяются системой

Откуда Z_min (0;3)=1∙0+1∙3=3

Ответ: Z_min (0;3)=3

Задание 2.8

Решить задачи симплексным методом:

L(¯x)=3x_1+x_2+2x_3→min при ограничениях

x_j≥0,j=1,2,3.

Решение

Введем искусственные переменные. В 1 равенстве вводим переменную x_4. Во 2 равенстве вводим переменную x_5.

Z=-3x_1-3x_2-3x_3+50

Сформируем начальную симплекс-таблицу.

Итерация 1Разрешающий столбец – x_3, разрешающая строка – x_5

Итерация 2Так как в столбце свободных членов нет отрицательных элементов, то найдено допустимое решение. Так как в строке L есть положительные элементы, то полученное решение не оптимально.
Разрешающий столбец – x_1, разрешающая строка – x_3

Ответ: н

Задание 2.9

Решить симплекс-методом

L(¯x)=x_1+x_2+x_3+x_4→min при ограничениях

x_j≥0,j=1,2,3,4.

Решение

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).

В 1 неравенстве вводим базисную переменную x_5. Во 2 неравенстве вводим базисную переменную x_6. Так как в преобразуемом неравенстве стоит знак ≥, то при переходе к равенству знаки всех его коэффициентов и свободных членов меняются на противоположные.

Сформируем начальную симплекс-таблицу.

Итерация 1Разрешающий столбец – x_1, разрешающая строка – x_5

Разрешающий столбец – x_4, разрешающая строка – x_6Так как среди свободных членов есть отрицательные значения, то решение недопустимое и сначала нужно перейти к допустимому решению.

Итерация 2

Разрешающий столбец – x_2, разрешающая строка – x_4Данное решение не оптимально.

Итерация 3

Оптимальный план: x_1=5/2,x_2=1/4,x_3=0,x_4=0Последняя строка не содержит отрицательные элементы. Поэтому эта таблица определяет оптимальный план задачи.

Задание 3.2

Решить транспортную задачу

Решение

Данная задача является закрытой, так как запасы поставщиков 90+30+40=160 и потребности 70+30+20+40=160 совпадают.

Теперь исходные данные задачи запишем в виде таблицы, а опорный план получим методом северо-западного угла.

Получим следующую таблицу.

Стоимость этого плана равна:Число заполненных клеток равно 6 и m+n-1=3+4-1=6 – план невырожденный. Оптимальный план найдём методом потенциалов.

L=1*70+3*20+3*10+1*20+5*0+2*40 = 260.

Расставим потенциалы:

(Обычно равным нулю принимают потенциал строки или столбца с наибольшим числом заполненных клеток.)

Теперь проверим пустые клетки на выполнение неравенства

Для клетки (2,4) неравенство не выполняется, значит опорный план не является оптимальным. В эту клетку нужно «ввезти» груз. Строим цикл.

Цикл перерасчёта таблицы – это последовательность ячеек, начинающаяся и заканчивающаяся в одной и той же клетке, с вершинами, лежащими в занятых клетках, кроме одной.

Вершина цикла – клетка, в которой происходит поворот под прямым углом.

«Перемещаем» груз по следующим правилам:

каждой из клеток, связанных циклом присваивается знак: пустой ячейке «+», остальным — поочерёдно знаки «-» и «+» .

среди минусовых клеток находим число 

и прибавляем его к числам, стоящим в плюсовых клетках, и вычитаем из чисел, стоящих в минусовых клетках; остальные клетки вне цикла остаются без изменения.

В нашем примере цикл образуют четыре ячейки: (2,4) – пустая, для которой не выполняется неравенство, и (2,2), (1,2), (1,4) – заполненные.

х = min(10, 0)= 0. Значит в плюсовые клетки «завозим» 0 ед. груза, из минусовых «вывозим». Получим новый опорный план:

Расставим потенциалы и проверим пустые клетки на выполнение неравенства  . Для клетки (3,2) неравенство не выполняется. Строим новый цикл.

х = min(10,40)=10. Значит в плюсовые клетки «завозим» 10 ед. груза, из минусовых «вывозим». Получим новый опорный план:

Расставим потенциалы и проверим пустые клетки на выполнение неравенства .