2.1 Теоретическая часть

Задачи линейного программирования находят широкое распространение в различных областях:

· Энергетике - рациональная организация электрификации районов с помощью различных видов электростанций;

· Химии - составление сложных смесей с заданным составом компонентов;

· Сельском хозяйстве - рациональное распределение посевных площадей под различные культуры;

· Металлургии- расчёт шихты для получения специальных легированных сталей;

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

Для переменных x1, x2, … , xn найти такие неотрицательные значения

xj?0, j=1..n

которые обращали бы в максимум целевую функцию

F=c0+> max

и удовлетворяли системе равенств

i=1..m

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

Если неизвестных переменных n, а ограничений m, то можно m неизвестных выразить через остальные (n-m) переменных, которые играют роль произвольных постоянных и называются свободными. Те m неизвестных переменных, которые выражаются через свободные, называются базисными.

Решение называется базисом, если в нем m базисных неизвестных выражены через (n-m) свободных неизвестных, и при равенстве свободных неизвестных нулю, что предполагается в базисном решении, базисные неизвестные неотрицательны.

Пронумеруем переменные таким образом, чтобы вначале шли свободные переменные (x1, … , xk), а далее базисные переменные (xk+1 , … , xn)

x1, x2, … , xk, xk+1, xk+2, … , xk+i, … , xn

Выразим базисные переменные и целевую функцию через свободные переменные:

xk+i=bi - i=1..m

F=c0+> max

При решении задач линейного программирования принято находить минимум целевой функции, то есть f(x) > min, где f(x)=-F(x)

Существует несколько методов решения задач линейного программирования:

1. графоаналитический метод;

2. симплекс-метод;

В графоаналитическом методе следует учитывать что переменных должно быть не более двух. Здесь сначала на основе неравенств строится область допустимых значений. Любое неравенство двух переменных делит область на два подмножества: в одном они выполняются, в другом - нет. Подмножества представляют собой полуплоскости, разделяемые прямой, которая получается, если в ограничении заменить знак неравенства на знак равенства.

Затем находится градиент, если функцию необходимо минимизировать, и антиградиент функции, если максимизировать:

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

Далее следует уловить тот момент, в котором эта линия имеет последнюю общую точку с ОДР.

Симплекс-методом получивший также в литературе название метода последовательного улучшения плана, разработанный в 1947г. американским математиком Джорджем Данцигом. Он даёт аналитическое решение задачи для любого количества переменных и удобен в использовании.

Для решения задачи линейного программирования симплекс-методом все ограничения должны иметь вид равенств.

Первый этап решения задач симплекс-методом сводится к приведению задачи к канонической форме.

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

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

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

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

Пусть имеется некоторая начальная симплекс-таблица:

xm, xr, xl - базисные неизвестные;

xs, xk - свободные неизвестные;

?ms, ?rs, ?ls, ?fs -- коэффициенты, стоящие перед свободной неизвестной хs, в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно;

?mk, ?rk, ?lk, ?fk --коэффициенты, стоящие перед свободной неизвестной xk, в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно;

?m0, ?r0, ?l0, ?f0 --свободные члены в выражениях для базисных неизвестных xm,xr, xl и целевой функции, соответственно.

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

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

Если в строке для целевой функции есть хотя бы один отрицательный коэффициент и в этом же столбце есть ещё хотя бы один отрицательный коэффициент, то целевую функцию можно уменьшить за счёт увеличения соответствующей свободной неизвестной. Это увеличение ограничено вследствие отрицательности коэффициента в выражении для базисной неизвестной. Из выражения базисной неизвестной через свободную находится предел свободной неизвестной. Например, в приведённой выше симплекс-таблице в строке для целевой функцииf(x)коэффициент ?fs > 0,акоэффициент ?fk < 0.Приэтом коэффициенты ?rk и ?lk, стоящие в столбце свободной неизвестной хk отрицательные. Для отрицательных коэффициентов найдём отношение

(i=r,l)

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

mini()=

Минимум ищется по всем значениям. xk называется увеличиваемой свободной неизвестной, i принадлежит тому множеству, для которого ?ik отрицательное.

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

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

Исходя из анализа начальной симплекс-таблицы, оптимальное решение не найдено, а целевую функцию можно уменьшить. При переходе к новому базису xl станет свободной неизвестной, а xk -- новой базисной неизвестной.

Получаем следующую симплекс-таблицу:

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

Как только в строке для целевой функции не будет отрицательных коэффициентов, то делается вывод о нахождении оптимального решения.

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

2.2 Задание

Фирме требуется уголь с содержанием примеси фосфора не больше 0,05% и с примесью пепла не более 4,00%. Доступны 3 сорта угля A,B,C по следующим ценам (за тонну):

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

2.3 Построение математической модели задачи

экономический математический модель градиент

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

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

Обозначим за x1, x2, x3 количество изделий А, В, С соответственно, с учетом того, что требуется уголь с содержанием примеси фосфора не более 0,05% и примеси пепла не более 4,00%. Связь между сортами угля каждого вида и количеством примесей выразится в системе следующим образом:

(1.1)

По смыслу задачи переменные

x1?0, x2?0, x3?0 (1.2)

Прибыль от реализации трех сортов угля будет выражена функцией:

F=35x1+30x2+48x3 (1.3)

Экономико-математическая модель задачи: найти такое количество каждого сорта угля, x=(x1, x2, x3), удовлетворяющее системе (1.1) и условию (1.2), при котором функция (1.3) принимает максимальное значение:

F=35x1+30x2+48x3 > max

f = -35x1-30x2-48x3 > min

2.4 Решение задачи

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

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

F=35x1+30x2 > max

f = -35x1-30x2 > min

ограничения:

x1?0, x2?0

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

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

Найдем градиент и антиградиент функции:

Значение функции будет уменьшатся при движении по направлению антиградиента и увеличиваться по направлению градиента.

Далее следует уловить тот момент, в котором эта линия имеет последнюю общую точку с ОДР.

Чтобы найти решение необходимо решить систему:

Оптимальное решение:

т. А(0,28;0,78)

F(0,28;0,78)=35*0,28+30*0,78=33,2

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

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

x4?0, x5?0

После приведения задачи к канонической форме необходимо выбрать первоначальный базис. В качестве базисных переменных возьмем x4, x5, а оставшиеся три переменные x1, x2, x3 будут свободными неизвестными. При этом необходимо, чтобы базисные неизвестные обладали следующим свойством: если все остальные неизвестные (x1, x2, x3) принять равными нулю, то переменные, выбранные в качестве базисных, должны быть неотрицательными.

Базисные переменные нужно выразить через свободные неизвестные:

Запишем опорный план:

Целевую функцию нужно выразить через свободные неизвестные:

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

Отрицательные коэффициенты стоят перед x1, x2 и х3.

Из первого уравнения следует, что х1=0,79.

Из второго уравнения следует, что x2=0,95.

Из второго уравнения следует, что x3=1,08.

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

fx1=-27,65, fx2=-28,57, fx3=-51,84

То есть целесообразно ввести в базис x3, тогда x5 выводим из базиса.

Рассчитаем новый базис:

Получаем базис:

Целевую функцию нужно выразить через свободные неизвестные:

Так как x1, x2 и x5 имеют отрицательные коэффициент, значит базисное решение не является оптимальным.

Выясним, до какого предела можно увеличивать x1 , x2 и x5:

из второго уравнения следует ограничение: x1 =0,64;

из первого уравнения следует ограничение: x2 =0,95;

из второго уравнения следует ограничение: x5 =4;

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

fx1=-20,77; fx2=-27,41; fx5=-0,77;

То есть целесообразно ввести в базис x2, тогда x3 выводим из базиса.

Рассчитаем новый базис:

Получаем базис:

Целевую функцию выражаем через свободные переменные:

Так как x1 имеет отрицательный коэффициент, значит базисное решение не является оптимальным.

Выясним, до какого предела можно увеличивать x1:

из второго уравнения следует ограничение: x1 =0,38;

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

fx1=-12,53;

То есть целесообразно ввести в базис x1, тогда x4 выводим из базиса.

Рассчитаем новый базис:

Получаем базис:

Видно, что в полученной функции не содержится отрицательных коэффициентов при x, следовательно найденное решение является оптимальным и Fmax=33,605.

Следовательно, наиболее выгодная смесь сортов углей это 0,295 единиц сорта A и 0,776 единиц сорта B, сорт C покупать не выгодно.

Рассмотрим решение данной задачи табличным симплекс-методом.

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

x4?0, x5?0

После приведения задачи к канонической форме необходимо выбрать первоначальный базис. В качестве базисных переменных возьмем x4, x5, а оставшиеся три переменные x1, x2, x3 будут свободными неизвестными. При этом необходимо, чтобы базисные неизвестные обладали следующим свойством: если все остальные неизвестные (x1, x2, x3) принять равными нулю, то переменные, выбранные в качестве базисных, должны быть неотрицательными.

Базисные переменные нужно выразить через свободные неизвестные:

Запишем опорный план:

Целевую функцию нужно выразить через свободные неизвестные:

Составляем начальную симплекс-таблицу:

Теперь необходимо исследовать полученную симплекс-таблицу. Анализ начнем с нижней строки симплекс-таблицы, которая соответствует целевой функции. Так как она содержит отрицательные коэффициенты перед свободными переменными, то минимум функции не может быть достигнут, поскольку можно до некоторого предела увеличивать переменные, перед которыми стоит этот коэффициент. Значит, необходима замена базиса. Определим переменную, которую необходимо вывести из базиса и ввести в него.

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

Отрицательные коэффициенты стоят перед x1, x2 и х3.

Из первого уравнения следует, что х1=0,79.

Из второго уравнения следует, что x2=0,95.

Из третьего уравнения следует, что x3=1,08.

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

fx1=-27,65, fx2=-28,57, fx3=-51,84

То есть целесообразно ввести в базис x3, тогда x5 выводим из базиса.

Следующий шаг - составление новой симплекс-таблицы. В ней x3, x4 будут базисными переменными, а x1, x2, x5 - свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.

Проанализируем полученную симплекс-таблицу. Нижняя строка таблицы, соответствующая целевой функции, содержит отрицательные коэффициенты перед x1, x2 и x5, значит минимум функции не может быть достигнут, поскольку можно до некоторого предела увеличивать эти переменные. Значит, необходима замена базиса.

Выясним, до какого предела можно увеличивать x1 , x2 и x5:

из второго уравнения следует ограничение: x1 =0,64;

из первого уравнения следует ограничение: x2 =0,95;

из второго уравнения следует ограничение: x5 =4;

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

fx1=-20,77; fx2=-27,41; fx5=-0,77;

То есть целесообразно ввести в базис x2, тогда x3 выводим из базиса.

Следующий шаг - составление новой симплекс-таблицы. В ней x2, x4 будут базисными переменными, а x1, x3, x5 - свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.

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

Выясним, до какого предела можно увеличивать x1:

из второго уравнения следует ограничение: x1 =0,38;

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

fx1=-12,53;

То есть целесообразно ввести в базис x1, тогда x4 выводим из базиса.

Следующий шаг - составление новой симплекс-таблицы. В ней x1, x2 будут базисными переменными, а x3, x4, x5 - свободными. Пересчитаем коэффициенты таблицы, для чего воспользуемся правилами перехода от одной симплекс-таблицы к другой, которые были описаны в предыдущем разделе.

Проанализируем полученную симплекс-таблицу. Нижняя строка таблицы, соответствующая целевой функции, не содержит отрицательных коэффициентов, значит, максимум функции достигнут. Найденное решение является оптимальным и Fmax=33,605

Следовательно, наиболее выгодная смесь сортов углей это 0,295 единиц сорта A и 0,776 единиц сорта B, сорт C покупать не выгодно.

3. Задача оптимального распределения перевозок

3.1 Теоретическая часть

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

В типичной транспортной задаче предполагается наличие некоторого количества пунктов отправления А1, А2, … , Аm (это могут быть склады, базы, хранилища и др.) и некоторого количества пунктов назначения В1, В2, … , Вn (это могут быть фабрики, магазины и др.).

Задаётся количество груза, которое должно быть вывезено из каждого пункта отправления, а также количество груза, которое должно быть доставлено в каждый пункт назначения. Ещё задаётся некоторая величина, определяющая стоимость перевозки (или эквивалентная ей характеристика перевозки) из пункта Оi, в пункт Нj. Если в качестве критерия оптимальности взять минимальную стоимость перевозок всего груза, то

cij -- стоимость перевозки единицы груза из i-го пункта отправления в j-ый пункт назначения;

ai -- запасы груза в i-ом пункте отправления;

bj -- потребности в грузе в j-ом пункте назначения;

xij -- количество единиц груза, перевозимого из i-ого пункта отправления в j-ый пункт назначения.

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

Иногда данное равенство не выполняется, тогда модель транспортной задачи открытая.

В случае, если запасы груза превышают потребность в них, то есть , то вводится фиктивный(n+1)-ый пункт назначения с потребностью bn+1=и стоимостью перевозки единицы груза (или эквивалентной характеристики) принимается равной нулю, то есть сi n+1=0 при i=1..m

В случае, если потребности больше, чем запасы груза, то есть , то вводится фиктивный (m+1)-ый пункт отправления с запасом груза am+1= и стоимость перевозки единицы груза (или эквивалентной характеристики) считаются равными нулю, то есть сm+1 j при j=1..n

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

> min

Ограничения:

1) наличие в каждом пункте отправления определённого количества товаров:

(i=1..m)

2) потребность у каждого пункта назначения в определённом количестве товаров:

(j=1..n)

3) xij?0 (i=1..m, j=1..n)

Количество переменных хij в задаче с m пунктами отправления и n пунктами назначения равно (m * n), а число уравнений равно (m + n). Для того, чтобы соблюдалось равенство , число линейно независимых уравнений должно быть равно (m + n - 1). Таким образом, базис будет содержать (m + n - 1) неизвестных.

Базис является невырожденным, если в нём число отличных от нуля компонент точно совпадает с (m + n - 1). Если же это число меньше нуля, то базис -- вырожденный.

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

Метод северо-западного угла является одним из наиболее простых и распространенных методов, но он дает самый далекий от оптимального план. В этом случае начинаем заполнять таблицу с крайней левой верхней клетки (C11) наибольшим возможным объемом груза. Затем вычеркиваем соответствующую строку или столбец и заполняем ставшую крайней левой верхней свободную клетку (т.е. C12 или C21). Продолжаем до тех пор, пока полностью не определим начальный базис.

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

Метод, который дает наиболее близкий к оптимальному план - метод Фогеля. Согласно этому методу для каждой строки и столбца находим "штраф", равный модулю разности между двумя наименьшими стоимостями. Затем начинаем заполнять клетки с той строки или столбца, где имеется наибольший штраф. Заполняем клетку с наименьшей стоимостью перевозки наибольшим объемом груза. Затем столбец вычеркивается и "штрафы" пересчитываются. Процесс продолжается дальше до полного определения начального базиса.

После выработки начального базиса начинается решение. Наиболее простым для нахождения решения является метод потенциалов.

Потенциалы находятся при рассмотрении занятых клеток. Поскольку количество таких клеток (m+n-1), а общее количество клеток (m*n), то количество потенциалов на единицу больше, чем базисных клеток, поэтому один из потенциалов можно задать произвольно (обычно задают нулевой потенциал).

Обозначим потенциалы строк через ui, а потенциалы столбцов через vj. Потенциал столбца находится так, чтобы для базисных клеток сумма потенциалов была равна стоимости перевозок, то есть

ui+vj = cij

После того, как все потенциалы найдены, вычисляются косвенные стоимости (косвенные стоимости находятся для клеток, не вошедших в базис):

cij= ui+vj

Затем, для каждой свободной клетки определяется разность:

fkl=ckl - ckl ,

где к и l -- индексы свободных клеток.

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

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

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

При правильном построении начального базиса для любой свободной клетки можно построить лишь один цикл пересчёта. После того как для выбранной свободной клетки он построен, следует перейти к новому базисному решению. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой. Это перемещение производят по следующим правилам:

1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают знак («+» или «--»), причём свободной клетке -- знак плюс, а всем остальным клеткам -- поочерёдно знаки минус и плюс;

2) в данную свободную клетку переносят меньшее из чисел xij, стоящих в клетках со знаком «--», одновременно это число прибавляют к соответствующим числам, стоящим в клетках со знаком «+», и вычитают из чисел, стоящих в клетках со знаком «--».

Клетка, которая ранее была свободной, будет занятой, а клетка с наименьшей загрузкой и со знаком «--»станет свободной.

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

3.2 Задание

Имеется четыре завода А1, А2, А3, А4, из которых нужно вывести некоторое количество грузов. И пять пунктов назначения В1, В2, В3, В4, В5, в которые должны быть привезены товары с заводов. Количество товаров в каждом пункте отправления, потребности каждого пункта назначения и тарифы на доставку приведены в таблице.

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

3.3 Построение математической модели задачи

Транспортная задача сводится к определению такого плана перевозок некоторого продукта с заводов в пункты потребления (реализации) - , который минимизирует целевую функцию

(2.1)

на множестве допустимых планов:

(2.2)

При соблюдении баланса

.(2.3)

Объемы запасов и заказов равны. Значит, задача сбалансированна и фиктивных пунктов доставки и отправления вводить не нужно.

Обозначим через xij количество продукции, перевозимой из i-го склада в j-ый магазин. Тогда условия перевозки грузов обеспечиваются за счет выполнения следующих равенств:

(2.4)

При данном плане перевозок общая стоимость перевозок составит:

F=5*x11+3*x12+24*x13+10* x14+25* x15+30*x21+2*x22+22*x23+16*x24+7* *x25+30*x31+24*x32+27*x33+29*x34+10*x35+15*x41+17*x42+21*x43+2*x44+3*x45 (2.5)

Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений «2.4», при котором целевая функция «2.5» принимает минимальное значение.

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

3.4 Решение транспортной задачи

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

Заполняется клетка С11 максимальным грузом, затем вычеркивается соответствующая строка или столбец. Затем заполняется клетка С12 или С21 максимальным грузом равным А1-В1, затем вычеркивается соответствующая строка или столбец и процесс повторяется.

Опорный план приведен в таблице.

Так как число отличных от нуля компонент точно не совпадает с (m + n -1), n-число складов, m- количество магазинов, то базис является вырожденным. Следовательно для устранения этого вводим нулевую загрузку в клетку с наибольшим тарифом.

F=5*12+3*12+30*0+2*1+22*14+29*16+2*15+3*9=927

Планы перевозок будут следующие:

1) С завода А1 будет отправлено 12 шт. товара потребителю B1 и 12 шт. товара потребителю B2

2) С завода А2 будет отправлена 1 шт. товара потребителю B2 и 14 шт. товара потребителю B3

3) С завода А3 будет отправлено 15 шт. товара потребителю B4

4) С завода А4 будет отправлено 15 шт. товара потребителю B4 и 9 шт. товара потребителю B5.

2. Метод Фогеля

Для каждой строки и столбца находим штраф - это модуль разности двух наименьших стоимостей перевозок. Заполнение выполняется с наибольшего штрафа. Опорный план приведен в таблице.

Так как число отличных от нуля компонент точно совпадает с (m + n -1), n-число складов, m- количество магазинов, то базис является невырожденным.

Минимальная стоимость перевозок составляет:

fmin = 5*12+24*5+7*10+2*13+22*2+27*7+10*9+2*24= 647

Планы перевозок будут следующие:

1) С завода А1 будут отправлены 12 шт. товара потребителю B1, 5 шт. товара потребителю B3 и 7 шт. товара потребителю B4.

2) С завода А2 будут отправлены 13 шт. товара потребителю B2и 2 шт. товара потребителю B3.

3) С завода А3 будет отправлено 7 шт. товара потребителю B3 B2и 9 шт. товара потребителю B5.

4) С завода А4 будут отправлены 24 шт. товара потребителю B4.

3. Метод двойного предпочтения

В каждой строке отмечаем галочкой клетку с наименьшим тарифом, затем то же сделать для каждого столбца. Далее выбираем клетку, в которой находятся две галочки, если таких клеток оказалось несколько, то выбираем ту, у которой наименьший тариф. В эту клетку записывается максимально возможное значение. Максимально возможное значение будет равно минимальному из чисел ai и bj. Опорный план приведен в таблице.

Так как число отличных от нуля компонент точно совпадает с (m + n -1), n-число складов, m- количество магазинов, то базис является невырожденным.

F=5*12+24*12+2*13+4*2+27*2+29*7+10*7+2*24=757

Планы перевозок будут следующие:

1) С завода А1 будет отправлено 12 шт. товара потребителю B1 и 12 шт. товара потребителю B3

2) С завода А2 будут отправлены 13 шт. товара потребителю B2 и 2 шт. товара потребителю B5

3) С завода А3 будет отправлено 2 шт. товара потребителю B3, 7 шт. товара потребителю B4 и 7 шт. товара потребителю B5

4) С завода А4 будет отправлено 24 шт. товара потребителю B4.

Найденный опорный план проверяем на оптимальность с помощью метода потенциалов.

4. Метод потенциалов

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

Далее для клеток, не вошедших в базис, вычисляются косвенные стоимости , которые принято указывать в верхнем правом углу. Затем, для каждой свободной (пустой) клетки определяется разность , где k и l - индексы клеток, не вошедших в базис. Эти значения пишутся в нижнем правом углу клеток.

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

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

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

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

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

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