Решение отимезированых задачь ленейных моделей с помощбю excel

В данной работе применены различные способы решения задач линейного программирования: графический, симплексный. Также решены транспортные задачи с помощью метода потенциалов. Все эти методы достаточно трудоемки и могут привести к вычмслительным ошибкам и неверным результатам
Облегчить решение можно, применяя пакет анализа Excel. В результате применения инструмента «Поиск решения» результат каждой задачи был проверен.

...

Введение 2
Теоретические сведения 3
1. Геометрическое решение ЗЛП 3
2. Симплексный метод решения 4
3. Транспортная задача. Метод потенциалов 6
4. Математическая модель задачи 7
5. Двойственность в линейном программировании 8
6. Линейное программирование в Excel 10
Решение задач 12
Список использованной литературы 57

Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности.
К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов.
Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Например:
задача об оптимальном использовании ресурсов при производственном планировании;
задача о смесях (планирование состава продукции);
задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами ил и "задача о рюкзаке");
транспортные задачи (анализ размещения предприятия, перемещение грузов).
Экономико-математическая модель любой задачи линейного программирования включает: целевую функцию, оптимальное значение которой (максимум или минимум) требуется отыскать; ограничения в виде системы линейных уравнений или неравенств; требование неотрицательности переменных.
Целью данной работы является освоение графического, симплексного методов решения задач линейного программирования, а также решения таких задач с помощью Ехcel.

Рассмотрим целевую функцию задачи Z = -5x1+14x2+8 → max.Построим прямую, отвечающую значению функции Z = 0:Z = -5x1+14x2+8 = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление максимизации Z(X). Начало вектора – точка (0; 0), конец – точка (-5; 14). Будем двигать эту прямую параллельным образом. Поскольку нас интересует максимальное решение, поэтому двигаем прямую до последнего касания обозначенной области. На графике эта прямая обозначена пунктирной линией.Прямая Z(x) = const пересекает область в точке D. Так как точка D получена в результате пересечения прямых (5) и(7), то ее координаты удовлетворяют уравнениям этих прямых:x2=5x1=0Решив систему уравнений, получим: x1 = 0, x2 = 5Откуда найдем максимальное значение целевой функции:Z(X) = -5∙0 + 14∙5 +8 = 78Построим двойственную задачу по следующим правилам. 1. Количество переменных в двойственной задаче равно количеству неравенств в исходной. 2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной. 3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется. Расширенная матрица A. 51585735-2-5-141-10015-5140Транспонированная матрица AT. 55-210-517-5-11145835-14050Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной. Неравенства, соединенные стрелочками (↔), называются сопряженными. 5y1 + 5y2 - 2y3 + y4≥-5y1 + 7y2 - 5y3 - y4 + y5≥1458y1 + 35y2 - 14y3 + 5y5 + 8 → miny1 ≥ 0, y2 ≥ 0, y3 ≥ 0, y4 ≥ 0, y5 ≥ 0 Исходная задача I Двойственная задача IIx1 ≥ 0↔5y1 + 5y2 - 2y3 + y4≥-5x2 ≥ 0↔y1 + 7y2 - 5y3 - y4 + y5≥14- 5x1 + 14x2 +8→ max↔58y1 + 35y2 - 14y3 + 5y5 + 8 → min5x1 + x2≤58↔y1 ≥ 05x1 + 7x2≤35↔y2 ≥ 0- 2x1 - 5x2≤-14↔y3 ≥ 0x1 - x2≤0↔y4 ≥ 0 x2≤5↔y5 ≥ 0Решим двойственную задачу средствами ExcelОптимальный план двойственной задачи равен: y1 = 0 , y2 = 2 , y3 = 0, y4 = 0, y5 = 0 Z(Y) = 58∙0+35∙2+14∙0+0∙0+5∙0+8 = 78Решить задачу линейного программирования симплекс- методом, сформулировать и решить двойственную задачу к исходной. Решить задачу средствами ExcelРешим прямую задачу линейного программирования симплексным методом, с использованием симплексной таблицы. Определим минимальное значение целевой функции Z(X) = 15x1 - x2 + 10x3+8 при следующих условиях-ограничений. При вычислениях значение Zc = 8 временно не учитываем. - 3x1 + x2 + 5x3≤3 3x1 + 3x2 - 2x3≥6 Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме). В 1-м неравенстве смысла (≤) вводим базисную переменную x4. В 2-м неравенстве смысла (≥) вводим базисную переменную x5 со знаком минус. -3x1 + 1x2 + 5x3 + 1x4 + 0x5 = 3 3x1 + 3x2-2x3 + 0x4-1x5 = 6 Введем искусственные переменные x: в 2-м равенстве вводим переменную x6; -3x1 + 1x2 + 5x3 + 1x4 + 0x5 + 0x6 = 3 3x1 + 3x2-2x3 + 0x4-1x5 + 1x6 = 6 Для постановки задачи на минимум целевую функцию запишем так: Z(X) = 15x1-1x2+10x3+Mx4+Mx5+Mx6 → minЗа использование искусственных переменных, вводимых в целевую функцию, накладывается так называемый штраф величиной М, очень большое положительное число, которое обычно не задается. Полученный базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Из уравнений выражаем искусственные переменные: x6 = 6-3x1-3x2+2x3+x5 которые подставим в целевую функцию: Z(X) = 15x1-x2 + 10x3 + M(6-3x1-3x2+2x3+x5) → min или Z(X) = (15-3M)x1+(-1-3M)x2+(10+2M)x3+(M)x5+(6M) → min Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид: EQ A = \b\bc\| (\a \al \co6 \hs2 (-3;1;5;1;0;0;3;3;-2;0;-1;1))Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом. Полагая, что свободные переменные равны 0, получим первый опорный план: X1 = (0,0,0,3,0,6) Базисное решение называется допустимым, если оно неотрицательно. БазисBx1x2x3x4x5x6x43-315100x6633-20-11Z(X0)6M-15+3M1+3M-10-2M0-M0Переходим к основному алгоритму симплекс-метода. Итерация №0. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x2, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai2 и из них выберем наименьшее: min (3 : 1 , 6 : 3 ) = 2 Следовательно, 2-ая строка является ведущей. Разрешающий элемент равен (3) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6minx43-3151003x6633-20-112Z(X1)6M-15+3M1+3M-10-2M0-M004. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x6 в план 1 войдет переменная x2. Строка, соответствующая переменной x2 в плане 1, получена в результате деления всех элементов строки x6 плана 0 на разрешающий элемент РЭ=3 На месте разрешающего элемента в плане 1 получаем 1. В остальных клетках столбца x2 плана 1 записываем нули. Таким образом, в новом плане 1 заполнены строка x2 и столбец x2. Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. НЭ = СЭ - (А*В)/РЭ СТЭ - элемент старого плана, РЭ - разрешающий элемент (3), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. Получаем новую симплекс-таблицу: БазисBx1x2x3x4x5x6x41-4017/311/3-1/3x2211-2/30-1/31/3Z(X1)-2-160-91/301/3-1/3-MИтерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся положительные коэффициенты. 2. Определение новой базисной переменной. В качестве ведущего выберем столбец, соответствующий переменной x5, так как это наибольший коэффициент . 3. Определение новой свободной переменной. Вычислим значения Di по строкам как частное от деления: bi / ai5 и из них выберем наименьшее: min (1 : 1/3 , - ) = 3 Следовательно, 1-ая строка является ведущей. Разрешающий элемент равен (1/3) и находится на пересечении ведущего столбца и ведущей строки. БазисBx1x2x3x4x5x6minx41-4052/311/3-1/33x2211-2/30-1/31/3-Z(X2)-2-160-91/301/3-1/3-M04. Пересчет симплекс-таблицы. Формируем следующую часть симплексной таблицы. Вместо переменной x4 в план 2 войдет переменная x5. Строка, соответствующая переменной x5 в плане 2, получена в результате деления всех элементов строки x4 плана 1 на разрешающий элемент РЭ=1/3 На месте разрешающего элемента в плане 2 получаем 1. В остальных клетках столбца x5 плана 2 записываем нули. Таким образом, в новом плане 2 заполнены строка x5 и столбец x5. Все остальные элементы нового плана 2, включая элементы индексной строки, определяются по правилу прямоугольника. Получаем новую симплекс-таблицу: БазисBx1x2x3x4x5x6x53-1201731-1x23-315100Z(X2)-3-120-15-10-M1. Проверка критерия оптимальности. Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи. Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. Оптимальный план можно записать так: x2 = 3 F(X) = -1∙3 + 8 = 5 Построим двойственную задачу по следующим правилам. 1. Количество переменных в двойственной задаче равно количеству неравенств в исходной. 2. Матрица коэффициентов двойственной задачи является транспонированной к матрице коэффициентов исходной. 3. Система ограничений двойственной задачи записывается в виде неравенств противоположного смысла неравенствам системы ограничений прямой задачи. Столбец свободных членов исходной задачи является строкой коэффициентов для целевой функции двойственной. Целевая функция в одной задаче максимизируется, в другой минимизируется. Расширенная матрица A. 3-1-5-333-2615-1100Транспонированная матрица AT. 3315-13-1-5-210-360Условиям неотрицательности переменных исходной задачи соответствуют неравенства-ограничения двойственной, направленные в другую сторону. И наоборот, неравенствам-ограничениям в исходной соответствуют условия неотрицательности в двойственной. Неравенства, соединенные стрелочками (↔), называются сопряженными. 3y1 + 3y2≤15 - y1 + 3y2≤-1 - 5y1 - 2y2≤10 - 3y1 + 6y2 + 8 → max y1 ≥ 0 , y2 ≥ 0 Исходная задача I Двойственная задача IIx1 ≥ 0↔3y1 + 3y2≤15x2 ≥ 0↔- y1 + 3y2≤-1x3 ≥ 0↔- 5y1 - 2y2≤1015x1 - x2 + 10x3 → min↔- 3y1 + 6y2 + 8 → max3x1 - x2 - 5x3≥-3↔y1 ≥ 03x1 + 3x2 - 2x3≥6↔y2 ≥ 0Решение двойственной задачи дает оптимальную систему оценок ресурсов. Используя последнюю итерацию прямой задачи найдем, оптимальный план двойственной задачи. Из теоремы двойственности следует, что Y = C*A-1. Составим матрицу A из компонентов векторов, входящих в оптимальный базис. EQ A = (A5, A2) = \b\bc\| (\a \al \co2 \hs2 (0;1;-1;3))Определив обратную матрицу D = А-1 через алгебраические дополнения, получим: EQ D = A-1 = \b\bc\| (\a \al \co2 \hs2 (3;-1;1;0))Как видно из последнего плана симплексной таблицы, обратная матрица A-1 расположена в столбцах дополнительных переменных. Тогда Y = C*A-1 = EQ (0, -1) x \b\bc\| (\a \al \co2 \hs2 (3;-1;1;0)) = (-1;0)Оптимальный план двойственной задачи равен: y1 = -1 y2 = 0 Z(Y) = 3∙(-1)+6∙0+8 = 5 Проверим решение 3. Решить транспортную задачу методом потенциалов и средствами Excel21.1.) Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов 12345Запасы18712145232210121861063854133444218913120Потребности111011211842 Проверим необходимое и достаточное условие разрешимости задачи. ∑a = 23 + 106 + 44 + 120 = 293 ∑b = 11 + 10 + 112 + 118 + 42 = 293 Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой. Занесем исходные данные в распределительную таблицу. 12345Запасы18712145232210121861063854133444218913120Потребности111011211842 Этап I. Поиск первого опорного плана. 1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел ai, или bj. Затем, из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Искомый элемент равен 1 Для этого элемента запасы равны 120, потребности 10. Поскольку минимальным является 10, то вычитаем его. x42 = min(120,10) = 10. 8x12145232x121861068x413344218913120 - 10 = 1101110 - 10 = 0112118420 Искомый элемент равен 2 Для этого элемента запасы равны 106, потребности 11. Поскольку минимальным является 11, то вычитаем его. x21 = min(106,11) = 11. xx12145232x12186106 - 11 = 95xx413344x1891311011 - 11 = 00112118420 Искомый элемент равен 3 Для этого элемента запасы равны 44, потребности 42. Поскольку минимальным является 42, то вычитаем его. x35 = min(44,42) = 42. xx1214x232x1218x95xx413344 - 42 = 2x189x1100011211842 - 42 = 00 Искомый элемент равен 4 Для этого элемента запасы равны 2, потребности 112. Поскольку минимальным является 2, то вычитаем его. x33 = min(2,112) = 2. xx1214x232x1218x95xx4x32 - 2 = 0x189x11000112 - 2 = 11011800 Искомый элемент равен 8 Для этого элемента запасы равны 110, потребности 110. Поскольку минимальным является 110, то вычитаем его. x43 = min(110,110) = 110. xxx14x232xx18x95xx4x30x18xx110 - 110 = 000110 - 110 = 011800 Искомый элемент равен 14 Для этого элемента запасы равны 23, потребности 118. Поскольку минимальным является 23, то вычитаем его. x14 = min(23,118) = 23. xxx14x23 - 23 = 02xx18x95xx4x30x18xx0000118 - 23 = 9500 Искомый элемент равен 18 Для этого элемента запасы равны 95, потребности 95. Поскольку минимальным является 95, то вычитаем его. x24 = min(95,95) = 95. xxx14x02xx18x95 - 95 = 0xx4x30x18xx000095 - 95 = 000 12345Запасы1871214[23]52322[11]101218[95]61063854[2]133[42]44421[10]8[110]913120Потребности1110112118422. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно: F(x) = 14∙23 + 2∙11 + 18∙95 + 4∙2 + 3∙42 + 1∙10 + 8∙110 = 3078 Искомый элемент равен 2 Для этого элемента запасы равны 106, потребности 11. Поскольку минимальным является 11, то вычитаем его. x21 = min(106,11) = 11. x7121452321012186106 - 11 = 95x5413344x1891312011 - 11 = 010112118420 Искомый элемент равен 1 Для этого элемента запасы равны 120, потребности 10. Поскольку минимальным является 10, то вычитаем его. x42 = min(120,10) = 10. xx12145232x1218695xx413344x18913120 - 10 = 110010 - 10 = 0112118420 Искомый элемент равен 3 Для этого элемента запасы равны 44, потребности 42. Поскольку минимальным является 42, то вычитаем его. x35 = min(44,42) = 42. xx1214x232x1218x95xx413344 - 42 = 2x189x1100011211842 - 42 = 00 Искомый элемент равен 4 Для этого элемента запасы равны 2, потребности 112. Поскольку минимальным является 2, то вычитаем его. x33 = min(2,112) = 2. xx1214x232x1218x95xx4x32 - 2 = 0x189x11000112 - 2 = 11011800 Искомый элемент равен 8 Для этого элемента запасы равны 110, потребности 110. Поскольку минимальным является 110, то вычитаем его. x43 = min(110,110) = 110. xxx14x232xx18x95xx4x30x18xx110 - 110 = 000110 - 110 = 011800 Искомый элемент равен 14 Для этого элемента запасы равны 23, потребности 118. Поскольку минимальным является 23, то вычитаем его. x14 = min(23,118) = 23. xxx14x23 - 23 = 02xx18x95xx4x30x18xx0000118 - 23 = 9500 Искомый элемент равен 18 Для этого элемента запасы равны 95, потребности 95. Поскольку минимальным является 95, то вычитаем его. x24 = min(95,95) = 95. xxx14x02xx18x95 - 95 = 0xx4x30x18xx000095 - 95 = 000 12345Запасы1871214[23]52322[11]101218[95]61063854[2]133[42]44421[10]8[110]913120Потребности1110112118422. Подсчитаем число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 8. Следовательно, опорный план является вырожденным. Строим новый план. Значение целевой функции для этого опорного плана равно: F(x) = 14∙23 + 2∙11 + 18∙95 + 4∙2 + 3∙42 + 1∙10 + 8∙110 = 3078 Искомый элемент равен 2 Для этого элемента запасы равны 120, потребности 11. Поскольку минимальным является 11, то вычитаем его. x41 = min(120,11) = 11. x71214523x1012186106x5413344218913120 - 11 = 10911 - 11 = 010112118420 Искомый элемент равен 1 Для этого элемента запасы равны 109, потребности 10. Поскольку минимальным является 10, то вычитаем его. x42 = min(109,10) = 10. xx1214523xx12186106xx413344218913109 - 10 = 99010 - 10 = 0112118420 Искомый элемент равен 3 Для этого элемента запасы равны 44, потребности 42. Поскольку минимальным является 42, то вычитаем его. x35 = min(44,42) = 42. xx1214x23xx1218x106xx413344 - 42 = 22189x990011211842 - 42 = 00 Искомый элемент равен 4 Для этого элемента запасы равны 2, потребности 112. Поскольку минимальным является 2, то вычитаем его. x33 = min(2,112) = 2. xx1214x23xx1218x106xx4x32 - 2 = 02189x9900112 - 2 = 11011800 Искомый элемент равен 8 Для этого элемента запасы равны 99, потребности 110. Поскольку минимальным является 99, то вычитаем его. x43 = min(99,110) = 99. xx1214x23xx1218x106xx4x30218xx99 - 99 = 000110 - 99 = 1111800 Искомый элемент равен 12 Для этого элемента запасы равны 23, потребности 11. Поскольку минимальным является 11, то вычитаем его. x13 = min(23,11) = 11. xx1214x23 - 11 = 12xxx18x106xx4x30218xx00011 - 11 = 011800 Искомый элемент равен 14 Для этого элемента запасы равны 12, потребности 118. Поскольку минимальным является 12, то вычитаем его. x14 = min(12,118) = 12. xx1214x12 - 12 = 0xxx18x106xx4x30218xx0000118 - 12 = 10600 Искомый элемент равен 18 Для этого элемента запасы равны 106, потребности 106. Поскольку минимальным является 106, то вычитаем его. x24 = min(106,106) = 106. xx1214x0xxx18x106 - 106 = 0xx4x30218xx0000106 - 106 = 000 12345Запасы18712[11]14[12]52322101218[106]61063854[2]133[42]4442[11]1[10]8[99]913120Потребности111011211842В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2. Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 8. Следовательно, опорный план является невырожденным. Значение целевой функции для этого опорного плана равно: F(x) = 12∙11 + 14∙12 + 18∙106 + 4∙2 + 3∙42 + 2∙11 + 1∙10 + 8∙99 = 3166 Этап II. Улучшение опорного плана. Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0. u1 + v3 = 12; 0 + v3 = 12; v3 = 12 u3 + v3 = 4; 12 + u3 = 4; u3 = -8 u3 + v5 = 3; -8 + v5 = 3; v5 = 11 u4 + v3 = 8; 12 + u4 = 8; u4 = -4 u4 + v1 = 2; -4 + v1 = 2; v1 = 6 u4 + v2 = 1; -4 + v2 = 1; v2 = 5 u1 + v4 = 14; 0 + v4 = 14; v4 = 14 u2 + v4 = 18; 14 + u2 = 18; u2 = 4 v1=6v2=5v3=12v4=14v5=11u1=08712[11]14[12]5u2=42101218[106]6u3=-8854[2]133[42]u4=-42[11]1[10]8[99]913Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых ui + vj > cij (1;5): 0 + 11 > 5; ∆15 = 0 + 11 - 5 = 6 (2;1): 4 + 6 > 2; ∆21 = 4 + 6 - 2 = 8 (2;3): 4 + 12 > 12; ∆23 = 4 + 12 - 12 = 4 (2;5): 4 + 11 > 6; ∆25 = 4 + 11 - 6 = 9 (4;4): -4 + 14 > 9; ∆44 = -4 + 14 - 9 = 1 max(6,8,4,9,1) = 9 Выбираем максимальную оценку свободной клетки (2;5): 6 Для этого в перспективную клетку (2;5) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-». 12345Запасы18712[11][-]14[12][+]52322101218[106][-]6[+]1063854[2][+]133[42][-]4442[11]1[10]8[99]913120Потребности111011211842Цикл приведен в таблице (2,5 → 2,4 → 1,4 → 1,3 → 3,3 → 3,5). Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 3) = 11. Прибавляем 11 к объемам грузов, стоящих в плюсовых клетках и вычитаем 11 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план. 12345Запасы1871214[23]52322101218[95]6[11]1063854[13]133[31]4442[11]1[10]8[99]913120Потребности111011211842Проверим оптимальность опорного плана. Найдем предварительные потенциалы ui, vj. по занятым клеткам таблицы, в которых ui + vj = cij, полагая, что u1 = 0.