Нахождение базисного решения методом наименьшей стоимости

1. Находится клетка с наименьшей стоимостью перевозки. Туда ставится максимально возможный груз ().
2. Затем находится следующая клетка с наименьшей стоимостью – заполняется аналогично.

Так же как и методе северо-западного угла, если на каком-то этапе одновременно вычеркивается и ПО, и ПН, то ставится 0 – вырожденное решение.

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

5. Графический метод решения ЗЛП. Градиент функции и его свойства.

Графический метод решения применим тогда, когда в задаче имеются две переменные (.

Линия уровня – множество всех тех точек плоскости, которые удовлетворяют равенству f(x,y)=c.

Градиент – вектор, координатами которого являются частные производные.

Свойства:

1. Он перпендикулярен линии уровня;

2. Он показывает направление наибольшего возрастания функции (если дана линейная функция и l1,l2,l3 – ее линии уровня, которым соответствуют значения функцииf1,f2,f3, то если при перемещении линииl1 параллельно самой себе по направлению градиента, получаем линииl2, а потомl3, то можно составить соотношение между значениями функций:f1<f2<f3).

Справедливо и обратное: зная соотношение между функциями можно узнать расположение линий уровня.

Графический метод решения ЗЛП построен на этом свойстве. Для того, чтобы решить задачу данным методом, необходимо:

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

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

2. Нарисовать вектор градиента целевой функции и перпендикулярно ему линию уровня целевой функции. Если она проходит через начало координат, то она соответствует f=0.

Так как функции, которые мы рассматриваем, линейные, то вектором градиента будут коэффициенты перед x.

3. Перемещать линию уровня параллельно самой себе до крайней точки области, исходя из условия задачи (максимум или минимум нужно найти?)

4. Найти координаты данной крайней точки области, решив соответствующую систему уравнений (уравнения отвечают линиям, которые пересекаются в данной точке).

5. Найти значение функции в указанной точке.

Замечания:

1. Если целевая функция имеет постоянное значение, то линия уровня при проходит через с.

; .

2. При параллельном перемещении линии уровня можно прийти не к крайней точке области, а к отрезку (см. билет 5).

3. Если ограничение задано в виде равенства, то область допустимых решений – отрезок этой прямой (множество точек, координаты которого удовлетворяют равенству: , где λ принимает значения от 0 до 1).