Балаш О.С., Высочанская Е.Ю.,

Балаш О.С., Высочанская Е.Ю.,

Попова А.А.

Б20Методы оптимальных решений: методические указания /О.С. Балаш, Е.Ю. Высочанская, А.А. Попова – Саратов: Изд-во Сарат. ин-та РГТЭУ, 2011. – 42 с.

 

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

Для студентов 1 и 2 курсов, обучающихся на заочной форме обучения в Саратовском институте (филиале) РГТЭУ.

Методические указания предназначены для студентов, обучающихся по направлению 080100.62 «Экономика»

 

 

УДК 51

ББК 22.1

 

Согласовано:

Зав. библиотекой_________Е.А. Лазарева

 

 

© Саратовский институт РГТЭУ, 2011

Оглавление

Введение. 4

Линейное программирование. 5

1. Элементы линейной алгебры.. 5

2. Основные понятия линейного программирования. 6

3. Геометрическое решение задач линейного программирования. 8

4. Симплексный метод. 13

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

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

5.1. Математическая модель и анализ транспортной задачи. 22

5.2. Составление начального плана перевозок. 24

5.3. Распределительный метод решения транспортной задачи. 26

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

5.5 Особенности решения транспортной задачи с невыполненным балансом 37

Литература. 39

а) основная литература. 39

б) дополнительная литература. 39

 

 

Введение

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

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

Курс “Прикладная математика” содержит элементы математического программирования.

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

 

Линейное программирование

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

Элементы линейной алгебры

 

Определение. Упорядоченная совокупность n действительных чисел называется n - мерным вектором `a = (a ₁, a ₂, …, a_n).

Определение. а_i называется i-компонентой вектора a.

Определение. Нулевой вектор – это вектор, каждая компонента которого равна нулю.

Определение. i-й единичный вектор – этовектор, i -я компонента которого равна единице, а остальные нули:

` l_i = (0,0,…,1,…,0).

Определение. Сумма двух векторов – это вектор, каждая компонента которого представляет собой сумму соответствующих компонент этих векторов.

` =(a ₁+ b ₁, a ₂+ b ₂,…, a_n + b_n).

Определение. Вектор , умноженный на число l называется произведением вектора a на число, если каждая компонента вектора умножается на это число: l = (la ₁, la ₂,…, la _n).

Определение. Вектор (– ) называется противоположным вектору , если l = –1.

Матрицы и действия над ними

Определение. Прямоугольная таблица чисел размерности m´n, где m – число строк, n – число столбцов, называется прямоугольной матрицей размера m´n

A = .

Например, матрица А размером 2´3:

.

Определение. Матрица называется квадратной порядка n, если ее число строк и столбцов совпадает, то есть m = n.

Например, квадратная матрица А размером 4´4:

A = .

Определение. Единичной матрицей называется квадратная матрица, у которой на главной диагонали стоят единицы, а остальные элементы – нули.

Е = .

Определение. Нулевой матрицей называется квадратная матрица, все элементы которой равны 0.

 

 

Основные понятия линейного программирования

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

Z (x ₁, ...x_n) = c ₁ x ₁ +...+c_nx_n max (min) (1)

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

(2)

(3)

x_j 0, (j = 1, …, n). (4)

Определение. Функция (1) называется целевой функцией или линейной формой задачи линейного программирования, а условия (2) – (4) – ограничениями данной задачи.

Определение. Стандартной (симметричной) задачей линейного программирования называется задача, которая состоит в определении экстремального значения целевой функции (1) при выполнении условий (2) и (4).

Определение. Основной (канонической) задачей линейного программирования называется задача, которая состоит в определении экстремального значения целевой функции (1) при выполнении условий (3) и (4).

Определение. Вектор или совокупность чисел = (х ₁, х ₂, ...., х_n), удовлетворяющих ограничениям задачи (2) – (4), называется допустимым решением или планом задачи линейного программирования.

Определение. План `Х*= (х ₁^*, х ₂ ^*, ...., х_n^*), при котором целевая функция (1) принимает свое оптимальное (минимальное или максимальное) значение, называется оптимальным планом.

Таким образом, линейное программирование является частью математического программирования, особенностью которого является то, что исследуемая целевая функция является линейной: Z (x ₁, ...,x_n) = c ₁ x ₁ +...+c_nx_n, а ограничения, накладываемые на переменные, представляют собой линейные уравнения или неравенства.

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

Если требуется провести поиск целочисленных значений x_j, то приходим к задаче целочисленного линейного программирования (ЦЛП).

 

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

 

Геометрическое решение задач линейного программирования приемлемо для случаев n 3.

Как известно, линейное уравнение a ₁ x ₁ +a ₂ x ₂ = b задает на плоскости (в пространстве R ²) прямую; уравнение a ₁ x ₁ + a ₂ x ₂ + a ₃ x ₃ = b – плоскость в R ³. Точно так же уравнение a_{i 1} x ₁ +... + a_inx_n = b_i (i -ое ограничение в канонической задаче ЛП) определяет в пространстве Rⁿ некоторое множество, называемое гиперплоскостью.

Определение. Фигура на плоскости называется выпуклой, если наряду с любыми ее точками М ₁ и М ₂ ей принадлежат и все точки отрезка М ₁ М ₂.

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

Определение. Множество X называется выпуклым, если вместе с любыми двумя точками (элементами) (x ₁, y ₁);(x ₂, y ₂) X оно содержит отрезок между этими точками, т.е. точки вида

y+ (1 – ) x, (0 1).

Это уравнение является уравнением отрезка.

Теорема. Пересечение любого числа выпуклых множеств является выпуклым множеством.

Очевидно, прямая в R ², плоскость в R ³ являются выпуклыми множествами. Точно так же, выпуклым множеством является гиперплоскость a_{i 1} x ₁ +... + a_inx_n = b_i и полупространство (вместе с границей) в Rⁿ, определяемое i -м ограничением в стандартной задаче:

a_i1x₁ +... + a_inx_n £ b_i.

Система ограничений (2) задает множество М – пересечение m выпуклых множеств в n -мерном евклидовом пространстве Rⁿ, поэтому само является выпуклым множеством. Множество М называется выпуклым многогранником (областью) допустимых решений.

При наличии только двух переменных М задает многоугольник решений в R ², а в случае переменных x ₁, x ₂, x ₃ – выпуклый многогранник в пространстве R ³.

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

Теорема. Функция цели (1) задачи линейного программирования достигает экстремума в угловой точке выпуклого множества допустимых решений.

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

 

Симплексный метод

 

Алгебраический метод решения (симплекс-метод) разработан американским математиком Д. Данцигом и опубликован в 1951 году. В его основе лежит использование элементарных преобразований матрицы ограничений канонической задачи линейного программирования (метод Жордана-Гаусса).

Переход от общей задачи линейного программирования (1), (2), (4) к задаче в канонической форме (1), (3), (4), осуществляется с помощью введения m неотрицательных дополнительных переменных , , . Эти переменные добавляются к каждому из неравенств системы (2), обращая их в равенства, и входят в функцию цели с коэффициентами, равными нулю. В этом случае задача линейного программирования в канонической форме формулируется так: требуется найти совокупность неотрицательных чисел

, (5)

которые удовлетворяют системе линейных уравнений:

(6)

и дают экстремум функции цели:

max (min) (7)

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

Рассмотрим задачу линейного программирования на нахождение минимума целевой функции.

Справедливы теоремы.

Теорема 1. Если для некоторого фиксированного индекса j выполняется условие Z_j – c_j > 0, то можно построить хотя бы один опорный план, для которого значение целевой функции Z будет меньше первоначального, то есть Z < Z₀.

Теорема 2. Если для некоторого опорного плана` x выполняется соотношение Z<sub>j</sub> – c<sub>j</sub> £ 0, то план` x является оптимальным.

Сформулируем алгоритм симплексного метода.

По условию задачи составляется экономико-математическая модель задачи в общем виде:

Z (x ₁, ..., x_n) = c ₁ x ₁ +...+c_nx_n max

x_j 0, (j = 1,…, n)

Переходят от задачи на максимум к задаче на минимум Z. Для этого целевую функцию умножают на (–1).

– Z(x ₁,..., x_n) = – c ₁ x ₁– ... – c_nx_n min.

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

x_j 0,(j = 1, …, n+m).

Запишем систему ограничений в векторной форме:

или

.

 

Составляется первая симплексная таблица:

Таблица 1

Базис	C	b	-c1	-c2	…	-cn	cn+ 1=0	…	cn+m =0
a 1	a 2	…	an	an+ 1	…	an+m
an+ 1	cn+ 1 = 0	b 1	a 11	a 12	…	a 1 n		…
an+ 2	cn+ 2 = 0	b 2	a 21	a 22	…	a 2 n		…
…	…	…	…	…	…	…	…	…	…
an+m	cn+m= 0	bm	am 1	am 2	…	amn		…
Zj-cj	Z0	c 1	c 2	…	cn		…

Столбец «Базис» – столбец векторов, входящих в базис.

Столбец «C» – столбец коэффициентов, стоящих в целевой функции при векторах базиса.

Строка «Z_j – c_j» – называется индексной строкой.

Столбец «b» – столбец ограничений по ресурсам, входящих в базис.

Столбцы a ₁ … a_m, …, a_{m+ 1}, …, a_n – это коэффициенты, стоящие при неизвестных в системе ограничений.

Заполним индексную строку «Z_j – c_j». Для столбца «b» это значение равно сумме попарных произведений элементов столбца «C» на элементы столбца «b», т. е.

.

Решение находится в столбце «b»:

=(b ₁, b ₂, …, b_m,0,…, 0); Z = Z₀..

Две верхние строки таблицы содержат коэффициенты функции цели и n+m векторов системы ограничений.

Просматриваются числа Z_j – c_j индексной строки.

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

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

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

После выбора разрешающего элемента симплексная таблица преобразовывается по формулам прямоугольника:

, (8)

a_ij – разрешающий элемент матрицы, a_ij 0.

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

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

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

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

 

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

Требуется найти максимум функции доходов:

Z = 4 x ₁ + 6 x ₂ max

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

 

Сведем задачу на максимум к задаче на минимум. Для этого умножим функцию цели на (–1).

– Z = –4 x ₁ – 6 x ₂ min.

Для приведения задачи к каноническому виду (с ограничениями-равенствами), пригодному к решению симплекс-методом, вводим дополнительные неотрицательные переменные x ₃, x ₄, x ₅ 0.

Имеем:

– Z = –4 x ₁ – 6 x ₂ + 0 х ₃ + 0 х ₄ + 0 х ₅ min

В производственной задаче дополнительные переменные x ₃, x ₄, x ₅ означают количество неиспользованного сырья (остаток) соответственно первого, второго и третьего вида.

Запишем задачу в векторной форме:

– Z = –4 x ₁ – 6 x ₂ + 0 х ₃ + 0 х ₄ + 0 х ₅ min

.

Составим первую симплекс-таблицу (таблица 2).

Коэффициенты при дополнительных переменных x ₃, x ₄, x ₅ образуют единичную матрицу. Принимаем вектора коэффициентов при x ₃, x ₄, x ₅ за базис, то есть в столбец «Базис» записываем вектора .

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

В столбец b поставим ограничения по ресурсам. Коэффициенты в столбцах а ₁, а ₂, …а ₅ – это коэффициенты, соответствующие переменным х ₁, х ₂,… х ₅ в системе ограничений, записанной в векторной форме.

Последняя строка называется индексной. Ее заполняют следующим образом. Находят сумму попарных произведений столбца b на С, затем вычитают соответствующий коэффициент при целевой функции.

Столбец b: Z ₀=0×784 + 0×552 + 0×567 = 0.

Столбец а ₁: Z ₁ – c ₁ = 0×16 + 0×8 + 0×5 – (– 4) = 4.

Столбец а ₂: Z ₂ – c ₂ = 0×4 +0×7 + 0×6 – (– 6) = 6.

Столбец а ₃: Z ₃ – c ₃ = 0×1 +0×0 + 0×0 – 0 = 0

Столбец а ₄: Z ₄ – c ₄ = 0×0 + 0×1 + 0×0 – 0 = 0

Столбец а ₅: Z ₅ – c ₅ = 0×0 + 0×0 + 0×1– 0 = 0

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

Таблица 2

Базис	C	b	с 1 =– 4	с 2 =– 6	с 3 = 0	с 4 = 0	с 5 = 0
`a 1	`a 2	`a 3	`a 4	`a 5
`a 3	с 3 =0
`a 4	с 4 =0
`a 5	с 5 =0
Zj - Cj

Первое базисное решение находится в столбце b: x ₁ = 0; x ₂ = 0; x ₃ = 784; x ₄ = 552; x ₅ = 567. При этом Z = 0. В индексной строке имеются положительные числа 4, 6. Следовательно, план не оптимальный.

Применяем алгоритм симплексного метода.

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

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

.

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

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

3. Элемент, стоящий на пересечении направляющей строки и направляющего столбца называется разрешающим. В данном случае он равен 9.

4. Строим вторую симплексную таблицу. Для этого переменную, соответствующую разрешающему столбцу а ₂ введем в базис на место переменной а ₅.

5. Элементы направляющей строки делим на разрешающий и результаты вносим в соответствующую строку второй симплекс-таблицы. То есть в третьей строке второй симплексной таблицы (таблица 3), получим:

(63; 5/9; 1; 0; 0; 1/9).

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

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

строка а₃:

; ; ; ; .

строка а ₄:

; ; ; ; .

индексная строка:

; ; ; ; .

Полученные значения записываем на соответствующие места таблицы 3.

Таблица 3

Базис	C	b	с 1 =– 4	с 2 =– 6	с 3 = 0	с 4 = 0	с 5 = 0
`a 1	`a 2	`a 3	`a 4	`a 5
a 3			124/9				-4/9
a 4			37/9				-7/9
a 2	-6		5/9				1/9
Zj-Cj	-378	2/3				-2/3

 

Получили второе базисное решение: x ₁ = 0; x ₂ = 63; x ₃ = 532; x ₄ = 111; x ₅ = 0и– Z ₂ = –378(значение –378 находится на пересечении индексной строки и столбца из свободных членов). Это решение не оптимально, так как в индексной строке имеется положительное число 2/3.

Повторяем процедуру симплексного метода.

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

 

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

.

Направляющей строкой будет строка а₄. Разрешающий элемент 37/9.

Составим третью симплекс-таблицу (табл.4).

Таблица 4.

	Базис	C	b	с 1 =– 4	с 2 =– 6	с 3 = 0	с 4 = 0	с 5 = 0
	`a 1	`a 2	`a 3	`a 4	`a 5
	a 3						-124/37	80/37
	a 1	-4					9/37	-7/37
	a 2	-6					-7/37	8/37
	Zj-Cj	-396				-6/37	-20/37

 

Получили третье базисное решение: x ₁ = 27; x ₂ = 48; x ₃ = 16; x ₄ = 0; x ₅ = 0; -Z=- 396.

В индексной строке нет положительных чисел. Решение оптимальное.

Вывод. Для получения максимальной стоимости готовой продукции Z_max =396 руб. необходимо изготовить 27 единиц продукции вида A и 48 единиц продукции вида В. При этом сырье первого вида останется неизрасходованным в количестве x ₃ = 16 кг, а сырье второго и третьего вида будет израсходовано полностью x ₄ = 0; x ₅ = 0.

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

 

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

Транспортная задача является специальной задачей линейного программирования.

Имеется m баз (пунктов отправления) A ₁, A ₂,..., A _m, в которых сосредоточены запасы однородного груза в количествах соответственно. Груз необходимо перевезти n потребителям (магазинам) B ₁, B ₂,..., B _n в количествах соответственно. Известна стоимость перевозки единицы груза с базы A_i (i= 1,2,…, m) потребителю B_j (j= 1,2,…, n). Требуется спланировать перевозки грузов так, чтобы их общая стоимость была минимальная.

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

. (9)

Рассмотрим закрытую модель транспортной задачи с матрицей перевозок, заданной в таблице 5.

Таблица 5

Базы	Потребители	Запасы (ai)
B 1	B 2	.................	B n
A 1	c 11	c 12	..................	c 1 n	a 1
A 2	c 21	c 22	..................	c 2 n	a 2
................	..............	.................	..................	.........	...................
A m	cm 1	cm 2	...................	cmn	am
Потребности (bj)	b 1	b 2	.................	bm

5.1. Математическая модель и анализ
транспортной задачи

 

Обозначим x_ij – величина груза, перевозимого с базы A_i (i= 1,2,…, m) потребителю B_j (j= 1,2,…, n).

Так как стоимости перевозок c_ij (тарифы) известны, запишем функцию общих затрат на перевозку:

min. (10)

Величина перевозимых грузов не может быть отрицательна:

(i= 1,2,…, m)(j= 1,2,…, n). (11)

Если задача с выполненным балансом, то есть выполняется условие (9), то количество вывозимого с i -ой базы груза должно совпадать с запасами на этой базе:

, (12)

количество груза, перевозимого j -ому потребителю, должно совпадать с его потребностями

. (13)

Математическая модель задачи: требуется минимизировать функцию затрат (функцию цели) Z:

min (14)

При наличии ограничений:

(15)

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

1. Все коэффициенты в системе ограничений равны единице.

2. Не все m + n уравнений являются независимыми. В силу условия одно из ограничений можно исключить и тогда для общего числа m´n переменных будет m + n –1 ограничений. То есть опорный план должен содержать не более m + n –1 компонент. В этом случае план называется невырожденным. В случае вырожденного опорного плана число компонент будет меньше, чем m + n –1. Если план оказывается вырожденным, то в клетку следует ввести пустую поставку (груз, равный 0) и считать ее заполненной.

При решении транспортной задачи выделяются следующие шаги:

1. Составление начального плана перевозок.

2. Проверка плана на оптимальность и его пошаговое улучшение.

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

 

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

Каждой строке с номером i в матрице перевозок приписывается числовое значение , а каждому столбцу с номером j значение . , называются потенциалами, если для каждой заполненной клетки (i; j) выполняется условие:

, (16)

где – тариф перевозки.

Определение. Сумма потенциалов для свободных клеток называется косвенными тарифами .

. (17)

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

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

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

Алгоритм решения транспортной задачи
методом потенциалов

Пусть имеется исходное базисное решение.

1. Для каждой строки и столбца матрицы перевозок необходимо задать потенциалы и для каждой базисной (заполненной) клетки записать уравнение вида (16). Получим систему уравнений для потенциалов.

2. Так как заполненных клеток , то соотношение (16) задают систему простейших уравнений с неизвестными. Дополняя ее условием: , получают единственное решение системы потенциалов. Числа удобно записать в дополнительном столбце справа от матрицы перевозок, а числа в дополнительной строке внизу таблицы.

3. Для каждой свободной строки находят косвенный тариф .

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

5. Среди разностей между косвенным и истинным тарифами, найденных в пункте 3, выбирают наибольшую. Находят соответствующую ей свободную клетку.

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

7. Возвращаются к пункту 1 алгоритма.

Литература

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

1. Акулич И.Л. Математическое программирование в решениях и задачах: Учебное пособие для студентов экономических специальностей ВУЗов - М.: Высшая школа,1986

2.