Лекция 3. Математическое программирование

Лекция 3. Математическое программирование

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

 

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

Математическая формулировка задачи об оптимальном использовании ресурсов

Для изготовления n видов продукции используется m видов ресурсов.

Обозначим через x_j…-число единиц j-го вида продукции (j=1,…,n), запланированной к производству;

b_i- запас i-го ресурса (i=1,…,m)

a_ij…-число единиц ресурса i, затрачиваемого на изготовление единицы продукции j-го вида (a_ij- технологические коэффициенты);

c_j- выручка от реализации единицы продукции j-го вида (или цена продукции j-го вида).

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

Найти такой план X=(x_{1, …,} x_n) выпуска продукции, который удовлетворял бы системе ограничений:

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

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

 

Лекция 7. Содержательные постановки задач линейного программирования. Методы решения задач линейного программирования

 

Лекция 4.

Пример решения задачи линейного программирования.

Рассмотрим следующую задачу. Компания производит краску для внутренних и наружных работ из сырья двух типов: М1 и М2. Существуют ограничения на расход сырья (таблица 2) и ограничения по спросу на готовую продукцию. Первое ограничение указывает, что ежедневный объем производства краски для внутренних работ не должен превышать ежедневный объем производства краски для наружных работ более, чем на одну тонну. Второе ограничение таково: максимальный ежедневный объем производства краски для внутренних работ не должен превышать 2 т.

 

Таблица 2. Исходные данные по расходу сырья.

 

	Расход сырья (в тоннах) на тонну краски	Максимально возможный ежедневный расход сырья
для наружных работ	для наружных работ
Сырье М1
Сырье М2
Доход (в тыс. долл.) на тонну краски

 

Сформулируем задачу линейного программирования в следующем виде: найти максимум линейной формы 5х₁ + 4 х₂ при ограничениях

6x₁ + 4 х₂ ≤ 24;

x₁ + 2 х₂ ≤ 6;

-x₁ + х₂ ≤ 1;

х₂ ≤ 2;

х ₁, х ₂ > 0.

 

 

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

5 x ₁ + 4 x ₂ + 0 x ₃ + 0 x ₄ + 0 x ₅ + 0 x ₆→ max;

6 х ₁ + 4 х ₂ + 1 х ₃ + 0 x ₄ + 0 x ₅ + 0 x ₆= 24;

х ₁ + 2 х ₂ + 0 х ₃ + 1 x ₄ + 0 x ₅ + 0 x ₆= 6;

- х ₁ + х ₂ + 0 х ₃ + 0 x ₄ + 1 x ₅ + 0 x ₆= 1;

х ₂+ 0 х ₃ + 0 x ₄ + 0 x ₅ + 1 x ₆=2;

x_i ≥0, i =1,…,6

 

Составим исходную симплекс-таблицу (табл. 3).

 

Таблица 3

	С
Bx	A0	A1	A2	A3	A4	A5	A6
хз
x4
x5		-1
x6
		-5	-4

 

Небазисные (нулевые) переменные х ₁ и х ₂; базисные переменные х ₃, x ₄, x ₅, x ₆

Поскольку -5 < -4 < 0, то в качестве направляющего выбираем столбец A ₁. Составив отношение вида , определяем направляющую строку. Для этого находим минимальное отношение

min Следовательно, направляющая строка - первая, направляющий элемент — а₁₁=1- Применив первый шаг симплексного преобразования, получим новую таблицу (табл. 4).

Таблица 4

	С
Bx	A0	A1	A2	A3	A4	A5	A6
x1
x4
x5
x6
			-

 

На данном этапе в качестве направляющего столбца выбираем второй, направляющая строка - третья, т.к. из наименьший элемент равен 3/2. Применим следующий шаг симплексного преобразования. В результате получим табл. 5.

 

Табл. 5.

Bx	A0	A1	A2	A3	A4	A5	A6
x1
x2
X2

 

Поскольку в индексной строке все элементы положительны, это означает, что найдено оптимальное решение х₁^*= 3, х₂ = , искомое значение целевой функции равно 5 х₁ + 4х₂= 21.

Пример 11.1.

Составить двойственную задачу по отношению к задаче, состоящей в максимизации функции

(11.4)

при условиях

(6.5)

Решение. Для данной задачи

и

Число переменных в двойственной задаче равно числу уравнений в системе (6.5), т. е. равно трем. Коэффициентами в целевой функции двойственной задачи являются свободные члены системы уравнений (6.5), т.е. числа 12, 24, 18.

Целевая функция исходной задачи (6.4) – (6.6) исследуется на максимум, а система условий (6.5) содержит неравенства. Поэтому в двойственной задаче целевая функция исследуется на минимум. Так как все три переменные исходной задачи (6.4) – (6.5) принимают только лишь неотрицательные значения, то в системе условий двойственной задачи должны быть три неравенства. Следовательно, для задачи (6.4) – (6.5) двойственная задача такова: найти минимум функции при условиях

Значение целевой функции в задачах равно 34.8

 

 

11.2. Решение задач линейного программирования с использованием программного обеспечения MATLAB

 

В состав MATLAB входит Optimization Toolbox, предназначенный для решения линейных и нелинейных оптимизационных задач.

Задача линейного программирования состоит в нахождении вектора x, который минимизирует целевую линейную функцию

f^Tx

при условии A X≤ B; X≥0,

где с =(с₁, c₂,…,c_n) представляет собой n-мерный вектор, составленный из коэффициентов целевой функции, причем c^T – транспонированная вектор- строка; x=(x₁. x_n) – n –мерный вектор переменных решений,

B=[b₁

b₂ m-мерный вектор свободных членов

b_m]

B_eq=[b_eq1

_…

b_eqr] ограничения в виде равенств;

двусторонние покомпонентные ограничения в векторной форме

lb≤x≤ub

A=

Пример: задача составления рациона питания

Имеются 3 продукта П₁, П₂ и П₃ разной цены, каждый из которых содержит определенное количество питательных ингридиентов И₁, И₂, И₃, И_4.

Известно, что в день требуется: И₁не менее 250, И₂ не менее 60, И₃ не менее 100 и И₄ не менее 220. Требуется минимизировать затраты на приобретение продуктов. Очевидно, что количество приобретаемых процессов не может быть отрицательным..

Записываем целевую функцию, матрицу A, векторы b и lb в соответствии с требованиями Toolbox, обозначив искомые количества продуктов через x_1, x₂ и x₃ соответственно. Поскольку линейные ограничения содержат «меньшк или равно», а количество ингредиентов в рационе не может быть менее заданных величин, то следует изменить знаки обеих частей системы.При вызове программы linprog вместо неиспользуемых ограничение (нет ограничений в виде равенств) задайте пустые массивы, обозначаемые в MATLAB пустыми скобками.

Программа ration

% задание матрицы и вектора правой части системы неравенств

A=[4 6 15

2 2 0

5 3 4

7 3 12]

A=-A;

b=[250 60 100 220];

b=-b;

% Определение коэффициентов целевой функции

f=[44; 35; 100];

% Задание ограничений снизу на переменные

lb=[0; 0; 0];

% решение и вывод результата в командное окно

x=linprog(f,A,b,[],[],lb)

Постановка задачи

Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. В качестве критериев в транспортных задачах используют: критерий стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию), критерий времени (план оптимален, если на его реализацию затрачивается минимум времени) и другие.

Наиболее часто встречаются следующие задачи, относящиеся к транспортным:

· прикрепление потребителей ресурса к производителям;

· привязка пунктов отправления к пунктам назначения;

· взаимная привязка грузопотоков прямого и обратного направлений;

· отдельные задачи оптимальной загрузки промышленного оборудования;

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

Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a ₁, a ₂,..., a_m. Известна потребность в грузах b ₁, b ₂,..., b_n по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту c_ij, . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i -го пункта отправления (от поставщика) в каждый j -ый пункт назначения (до потребителя) x_ij с минимальными транспортными издержками.

В общем виде исходные данные представлены в табл. 7.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта a_i ), а столбцы - пунктам назначения (последняя клетка каждого столбца содержит значение потребности b_j). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i -го пункта в j -й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем - значение объема перевозимого груза для данных пунктов.

Таблица 7.1. Исходные данные

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

 

(2.1)

Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:

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

Все грузы из i-х пунктов должны быть отправлены, т.е.:

(2.3)

Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

(2.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных:

(2.5)

Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(2.6)

 

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

- потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления с объемом запасов. равным;

(2.7)

- запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления, равным:

(2.8)

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

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

- распределению подлежат однородные ресурсы;

- условия задачи описываются только уравнениями;

- все переменные выражаются в одинаковых единицах измерения;

- во всех уравнениях коэффициенты при неизвестных равны единице;

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

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

Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.

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

7.2. Методы составления начального опорного плана

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

 

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

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

Начиная с первоначально данной таблицы и повторив (m + n - 2) раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив (m + n - 1) шагов, мы и получим искомый опорный план.

Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется "остаток" равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная "потребность" в количестве нуля единиц груза, которая и удовле­творяется на одном из следующих шагов. Этот нуль ("запас" или "потребностью" – безразлично) надо записать в очередную заполняе­мую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем.

1. Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x ₁₁ и заканчивается в клетке неизвестного x_mn, т. е. идет как бы по диагонали таблицы перевозок.

 

Пример

Заполнение таблицы начинается с ее северо-западного угла, т.е. клетки с неизвестным x ₁₁. Первая база A ₁ может полностью удовлетворить потребность первого заказчика B ₁ (a ₁=300, b ₁=170, a ₁ > b ₁). Полагая x ₁₁= 170, вписываем это значение в клетку x ₁₁ и исключаем из рассмотрения первый столбец. На базе A ₁ остается измененный запас . В оставшейся новой таблице с тремя строками A ₁, A ₂, A ₃ и четырьмя столбцами B ₁, B ₂, B ₃, B ₄; северо-западным углом будет клетка для неизвестного x ₁₂. Первая база с запасом может полностью удовлетворить потребность второго заказчика B ₂ . Полагаем x ₁₂ = 110, вписываем это значение в клетку x ₁₂ и исключаем из рассмотрения второй столбец. На базе A ₁ остается новый остаток (запас) . В оставшейся новой таблице с тремя строками A ₁, A ₂, A ₃ и тремя столбцами B ₃, B ₄, B ₅ северо-западным углом будет клетка для неизвестного x ₁₃. Теперь третий заказчик B ₃ может принять весь запас с базы A ₁ . Полагаем x ₁₃ = 20, вписываем это значение в клетку x ₁₃ и исключаем из рассмотрения первую строку. У заказ­чика из B ₃ осталась еще не удовлетворенной потребность .

Теперь переходим к заполнению клетки для неизвестного x ₂₃ и т.д.

Через шесть шагов у нас останется одна база A ₃ с запасом груза (остатком от предыдущего шага) и один пункт B ₅ с потреб­ностью b ₅=200. Соответственно этому имеется одна свободная клетка, которую и заполняем, положив x ₃₅=200. План составлен. Базис образован неизвестными x ₁₁, x ₁₂, x ₁₃, x ₂₃, x ₂₄, x ₃₄, x ₃₅. Правиль­ность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.

Общий объем перевозок в тонно-километрах для этого плана составит

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

Пример

В данном случае заполнение таблицы начинается с клетки для неизвест­ного x ₃₂, для которого мы имеем значение c ₃₂ = 10, наименьше из всех значений c_ij. Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A ₃ и вто­рому заказчику B ₂. Третья база A ₃ может полностью удовлетворить потребность второго заказчика B ₂ (a ₃=250, b ₂=110, a ₃ > b ₂). Пола­гая x ₃₂ = 110, вписываем это значение в клетку x ₃₂ и исключаем из рассмотрения второй столбец. На базе A ₃ остается изменённый запас . В оставшейся новой таблице с тремя строками A ₁, A ₂, A ₃ и четырьмя столбцами B ₁, B ₃, B ₄, B ₅ клеткой с наименьшим значе­нием c_ij клетка, где c ₃₄=11. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В резуль­тате оказываются заполненными (в приведенной последовательности) следующие клетки:

На пятом шаге клеток с наименьшими значениями c_ij оказалось две (c ₁₁= c ₁₅=70). Мы заполнили клетку для x ₁₅ , положив x ₁₅ = 180. Можно было выбрать для заполнения другую клетку, положив x ₁₁ = 170, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит

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

Кроме рассмотренных выше способов иногда используется, так называемый, метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.

 

Понятие потенциала и цикла

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

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

1. Одно из неизвестных последовательности свободное, а все остальные – базисные.

2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

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

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

Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

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

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

старые значения: x ₂₁= 0, x ₂₃= 80, x ₁₃= 20, x ₁₁= 170, x ₂₁= 0;

новые значения:

Очевидно, если снабдить вершины цикла поочередно знаками "+" и "–", приписав вершине в свободной клетке знак "+", то можно сказать, что в вершинах со знаком "+" число x прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком "–" это число x вычитается из прежнего значения неизвестного, находящегося в этой вершине.

Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак "+", т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.

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

Так, например, в рассмотренном выше цикле имеем отрицательные вершины x ₂₁ и x ₁₁ ; следовательно, выбрав х = min {80; 170} = 80, мы получаем:

старые значения: x ₂₁= 0, x ₂₃= 80, x ₁₃= 20, x ₁₁= 170, x ₂₁= 0;

новые значения:

т. е. вместо прежнего базисного решения получаем новое базисное решение:

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

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

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

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

Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свобод­ных неизвестных, как и до пересчета.

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

Пусть x_pq – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом x. Если вершине цикла, находящейся в i -й строке и j -м столбце таблицы перевозок, приписан знак "+", то значение неизвестного x_ij, находящегося в этой вершине, увеличивается на x, что в свою очередь вызывает увеличение затрат на c_ij x, где c_ij – тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного x_ij уменьшается на x, что вызывает уменьшение затрат на c_ij x.

Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность S_pq назовем алгебраической суммой тарифов для данного свободного неизвестного x_pq. Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).

Теперь, очевидно, мы можем, заключить, что в целом при пере­счете но циклу, соответствующему свободному неизвестному x_pq общий объем затрат на перевозки изменится на произведение алгеб­раической суммы тарифов на x, т. е. на величину S_pqx. Следовательно, если алгебраическая сумма тарифов для некоторого свобод­ного неизвестного x_pq отрицательна (S_pq < 0), то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна (S_pq > 0), то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю (S_pq = 0), то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).

Так, например, для цикла x ₂₁, x ₂₃, x ₁₃, x ₁₁, x ₂₁ в рассмотренной задаче алгебраическая сумма тарифов

.

Значит, пересчет по этому циклу снижает расходы. И действитель­но, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет

тогда как по исходному плану он составил S ₁= 30650. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна –15, а пересчет по циклу осуществляется с помощью числа х = 80 (изменение затрат равно -15*80 = - 1200).

Шаг 2.

Ячейки, образующие цикл для свободной ячейки A₃B₂: A₃B₂, A₃B₄, A₂B₄, A₂B₁, A₁B₁, A₁B₂

 

Пункты отправления	Пункты назначения	Запасы
B1	B2	B3	B4	B5
A1	90 + 50 70	110 – 50 50	10015
A2	80 - 50 80			70 + 50 90
A3		+50 10		50 - 50 11	200 25
Потребности

F=29400 ден. ед.

 

Вычисление алгебраической суммы тарифов для каждого из свободных неизвестных можно производить без построения соответствующего цикла, пользуясь так называемыми потенциалами. Припишем каждой базе A_i,, некоторое число u_i, и каждому потребителю B_j некоторое число v_j:

,

так что

u_i, + v_j = c_ij, (7.6)

где c_ij – тарифы, соответствующие клеткам, заполненным базис­ными неизвестными. Эти числа u_i, и v_j называются потенциалами соответствующих баз и потребителе