Транспортная задача.

Автобаза обслуживает три магазина, доставляя в них товары из двух торговых баз. Известно, что ежедневно вывозится с первой базы 12т. товара, а со второй базы 15т. При этом в магазины ежедневно завозится в первый – 8т., во второй 9т., в третий 10т. Стоимость перевозки одной тонны определяется таблицей.

Требуется спланировать перевозки так, чтобы их стоимость была минимальной.

Введём переменные величины, соответствующие количеству товара доставляемого в первый, второй и третий магазины соответственно; - количество товара поставляемого со второй базы. Стоимость перевозок запишем в виде:

- это и есть целевая функция.

- проектные параметры. На проектные параметры накладываются ограничения. Во-первых, это ограничение равенства, оно следует из условия задачи и описывает количество товаров, которые вывозят с баз и доставляют в магазины.

К данной системе необходимо добавить систему неравенств

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

А целевая функция принимает вид . Теперь условия неравенства принимают вид.

Система этих неравенств определяет область допустимых значений переменных - область . запишем систему неравенств в виде

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

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

В общем случае при решении произвольной задачи линейного программирования, область допустимых значений образуется при пересечении конечного числа плоскостей. Эта область может быть как ограниченной, так и неограниченной и даже пустой, если система ограничений противоречива, в последнем случае задача решения не имеет. Обычно область решений представляет собой выпуклый многоугольник. Целевой функции соответствует гиперплоскость. Изменение значения целевой функции соответствует параллельной пересечения гиперплоскости (на единицу меньше). Минимальному значению целевой функции будет соответствовать точка касания гиперплоскости с одной точкой области , то есть с одной из вершин многогранника. При минимальном значении целевой функции гиперплоскость может совпадать не с одной точкой, а с одной из граней. В этом случае все точки целевой функции являются решением задачи.