Методы оптимизации

Размещено на http://www.allbest.ru/

1. Метод северо-западного пути

При этом методе всегда выбираем первый из оставшихся элементов.

Заполняем клетки начиная с А1В1 и заканчиваем на А3В5.

Так чтобы сумма строк была равна значению текущей строки в столбце «Запасы», а сумма столбцов была равна сумме в строке «Потребитель» текущего столбца.

X = опорный план

Значения в матрице Х умножаем на соответствующий тариф из матрицы С.

F = 150*7+30*12+60*8+80*6+120*5+10*3+100*4=3400

2. Метод наименьшего элемента

В данном случае заполнение начинается с наименьшего тарифа и таких несколько то заполняем тот который ближе к началу.

X = опорный план

Значения в матрице Х умножаем на соответствующий тариф из матрицы С.

F = 80*4+100*6+150+10*5+110*3+90*13+10*7=2690

3. Метод апроксимации Фогеля

В данном методе в столбце находи разность между двумя разными тарифами и первую итерацию записываем в столбец соответствующий максимальному значению из полученных разностей.

X = опорный план

Значения в матрице Х умножаем на соответствующий тариф из матрицы С.

F =120*6+60*5+150+90*8+30*6+50*8+50*4=2670

4. Симплекс метод

16x₁+14x₂= min

Определим минимальное значение целевой функции F(X) = 16x₁ + 14x₂ при следующих условиях-ограничений.

Умножим коэффициенты исходной функции на -1.

К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x3 - преобразуем неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x4 - преобразуем неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x5 - преобразуем неравенство 3 в равенство.

Система ограничений приведена к каноническому виду, т.е. все условия системы представляют собой уравнения.

Наличие единичного базиса в системе ограничений позволяет легко найти начальное опорное решение. Рассмотрим подробнее:

Переменная x3 входит в уравнение 1 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x3 - базисная переменная.

Переменная x4 входит в уравнение 2 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x4 - базисная переменная.

Переменная x5 входит в уравнение 3 с коэффициентом 1, а в остальные уравнения системы с коэффициентом ноль, т.е. x5 - базисная переменная.

Переменные, которые не являются базисными называются свободными переменными. Приравняв свободные переменные нулю в получившийся системе ограничений мы получим начальное опорное решение.

X _нач = (0, 0, 220, 220, 240)

Функция G не должна содержать базисных переменных

Вернемся к рассмотрению функции G.

G = -16 x1-14 x2

Функция G не содержат базисных переменных.

Значение функции G для начального решения: G (X нач) = 0

Для составления начальной симплекс таблицы мы выполнили все условия.

В процессе дальнейших преобразований возможны два случая. Если в симплекс таблице, на каком то шаге, мы получим строку L состоящую из неотрицательных элементов - задача решена, мы нашли оптимальное решение. В противном случае - функция не является ограниченной.

Учитывая, что все x i0, по условию задачи, наибольшее значение функции G равно свободному члену 0, т.е. мы получили оптимальное решение.

Ответ:

X _опт = (0, 0, 220, 220, 240)

Значение функции: L = 0

апроксимация функция наименьший графический

5. Графический метод

Найдем наименьшее значение линейной функции графическим методом.

L = 16 x₁ + 14 x₂

при следующих ограничениях

Решение

В первую очередь, найдем область допустимых значений, т.е. точки x₁ и x₂, которые удовлетворяют системе ограничений. По условию задачи x₁  0, x₂  0, т.е. мы рассматриваем только те точки, которые принадлежат первой четверти.

Шаг 1

Рассмотрим неравенство 1 системы ограничений

10 x₁+ 7 x₂<=220

Построим прямую.

Заменим знак неравенства на знак равенства.

10 x₁+ 7 x₂=220

Преобразуем уравнение следующим образом.

Каждый член уравнения разделим на 220.

Данное представление прямой называется уравнением прямой в отрезках и позволяет, очень легко, нарисовать данную прямую. На оси X₁ рисуем точку с координатой 22. На оси X₂ рисуем точку с координатой 31,42857. Соединяем полученные точки и получаем необходимую прямую.

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой. X

Объединим полученную полуплоскость с ранее найденными ограничениями. Область допустимых значений выделена штриховкой. Точки принадлежащие области допустимых значений:

A (0; 0)

B (22; 0)

C (0; 31,42857)

Шаг 2

Рассмотрим неравенство 2 системы ограничений.

Заменим знак неравенства на знак равенства.

Преобразуем уравнение следующим образом.

Каждый член уравнения разделим на 220.

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, область допустимых значений выделена штриховкой.

Точки принадлежащие области допустимых значений:

A (0; 0)

B (22; 0)

D (0; 27,5)

E (3,33; 26,667)

Шаг 3

Рассмотрим неравенство 3 системы ограничений.

4 x₁+ 9 x₂<=240

Заменим знак неравенства на знак равенства.

Преобразуем уравнение следующим образом

Каждый член уравнения разделим на 240.

Соединяем полученные точки и получаем необходимую прямую.

Знак неравенства меньше или равно нуля, следовательно, нас интересуют точки лежащие ниже построенной нами прямой.

Объединим полученную полуплоскость с ранее найденными ограничениями, получим рисунок, приведенный справа.

Область допустимых значений выделена штриховкой.

Точки принадлежащие области допустимых значений:

A (0, 0)

B (22, 0)

F (0, 26,667)

Шаг 4

Вернемся к нашей исходной функции L.

Допустим значение функции L равно 1 (абсолютно произвольно выбранное число), тогда

Данное уравнение является уравнением прямой на плоскости. Из курса аналитической геометрии известно, что данная прямая перпендикулярна вектору, координатами которого являются коэффициенты функции, а именно вектору

Следовательно, с геометрической точки зрения, наша исходная функция L изображается как множество прямых перпендикулярных вектору

Построим вектор

Диапазон перемещения прямой НЕ от точки O до точки N, а именно, в направлении от точки O к точке N.

Диапазон перемещения в направлении от точки O к точке N.

Ответ:

Наименьшее значение функция достигает при

x₁ =0

x₂ = 0

Значение функции: L = 0

Размещено на Allbest.ru