Исходную расширенную систему занести в первую симплексную таблицу

Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной. В ней указать коэффициенты функции цели с противоположным знаком: d_i = - c_i. В левом столбце таблицы записать основные переменные (базис), в первой строке таблицы – все переменные (отмечая при этом основные), во втором столбце – свободные члены расширенной системы b₁,b₂, …b_m. Последний столбец подготовлен для оценочных отношений, необходимых при расчете наибольшего возможного значения переменной. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занести коэффициенты a_ij при переменных из расширенной системы задачи. Далее таблицу следует преобразовывать по определенным правилам.

3. Проверить выполнение оптимальности при решении задачи на максимум – наличие в последней строке отрицательных коэффициентов d_i<0 (c_i >0). Если таких нет, то решение оптимально, достигнут максимум функции = с₀. Имеет место оптимальное базисное решение.

4. Если критерий оптимальности не выполнен, то наибольший по модулю отрицательный коэффициент d_i<0 в последней строке определяет разрешающий столбец S. Составить оценочные ограничения каждой строки. Определить: . Эта строка называется разрешающей строкой. На пересечении разрешающих строки и столбца находится разрешающий элемент a_qs.

5. Перейти к следующей таблице по правилам:

¾ в левом столбце записать новый базис: вместо основной переменной x_q - переменную x_s;

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

1 – против «своей» основной переменной;

0 – против «чужой» основной переменной;

0 – в последней строке для всех основных переменных.

¾ новую строку с номером q получаем из старой делением на разрешающий элемент a_qs;

¾ все остальные элементы a_ij вычисляем по правилу прямоугольника: , гдеА – элемент ведущего столбца, стоящий в одной строке с а_ij; В – элемент ведущей строки, стоящий в одном столбце с а_ij.

¾ далее переходим к п.3 алгоритма.

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

Пример: Предположим, составляется план производства для предприятия, выпускающего два вида продукции А и В. На изготовление единицы изделия требуется затратить а₁ = 2 кг сырья первого типа, а₂ = 3 кг сырья второго типа и а₃ = 4 кг сырья третьего типа. Для единицы изделия В: b₁ = 1 кг сырья первого типа, b₂ = 4 кг сырья второго типа и b₃ = 3 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количествах 400 кг, 900 кг и 600 кг соответственно. Стоимость реализации единицы изделия А составляет 60 (д.ед.), а единицы изделия В – 40 (д.ед.). Следует составить план производства изделий А и В, обеспечивающий максимум прибыли от реализации.

Сформулируем задачу математически. Пусть х₁ и х₂ – неизвестные количества изготавливаемых изделий А и В, соответственно. Необходимо найти такие х₁ и х_2, чтобы выполнялись условия.

и при этом функция f = 60x₁ + 40x₂, была максимальна.

Система ограничений описывает условии производства. Функция f – целевая функция, а х₁ и х₂ – аргументы целевой функции.

Задача имеет стандартную форму. Представим эту задачу в канонической форме, введя дополнительные переменные х₃, х₄, х₅, которые имеют смысл остатков неиспользованного сырья, соответственно, первого, второго и третьего типов.

Функцию f представим в неявном виде: .

Пусть переменные х₁, х_2, входящие в функцию f, будут свободными, а переменные х₃, х₄, х₅ – базисными. Базисные переменные выразятся через свободные следующим образом: . Полагая свободные переменные равными нулю получим первое опорное решение: х₁ = х₂ = 0, х₃ = 400, х₄ = 900, х₅ = 600. При этом f = 0. экономический смысл полученного решения состоит в том, что ни один из видов продукции не производится, все ресурсы остаются неиспользованными, а, следовательно, и прибыли нет.

№1	х1	х2	х3	х4	х5	bi	bi/aij
х3							400/2=200
х4							900/3=300
х5							600/1=600
f	-60	-40

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

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

В последней строке таблицы среди отрицательных значений находим наибольший по абсолютной величине элемент (это (-60)). Столбец, в котором находится этот элемент, называется ведущим, он соответствует новой базисной переменной х₁. Делим свободные члены (b_i) на соответствующие элементы ведущего столбца (отрицательные элементы ведущего столбца и нули во внимание не принимаются) и среди частных от деления находим минимальное, т.е. . Строка, которой соответствует минимальное значение, называется ведущей строкой. Смысл этой операции – гарантировать получение новой вершины многоугольника решений за счет выбора строки, наиболее ограничивающей сверху значение новой базисной переменной х_1. Ведущая строка - первая – соответствует старой базисной переменной х₃, которая переводится в свободные. На пересечении ведущей строки и ведущего столбца расположен разрешающий элемент а^* = 2.

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

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

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

В На рис. элементы а_ij и а^* вершины прямоугольника; А – элемент ведущего столбца, стоящий в одной строке с а_ij; В – элемент ведущей строки, стоящий в одном столбце с а_ij. Тогда

а_ij

А

№2	х1	х2	х3	х4	х5	bi	bi/aij
х1		1/2	1/2
х4		2,5	-1,5				120
х5		2,5	-0,5
f		-10

Пользуясь изложенными правилами, получим симплексную таблицу №2. базисные переменные: х₁ = 200, х₄ = 300, х₅ = 400. Переменные х₂, х₃ являются свободными и равны нулю: х₂ = х₃ = 0. Прибыль составляет: f = 12000 (д.ед.)

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

№3	х1	х2	х3	х4	х5	bi
х1			4/5	-1/5
х2			-3/5	2/5
х5				-1
f

Преобразуя таблицу №2 как и ранее методом Гаусса, получим таблицу №3. В последней строке таблицы все элементы положительны, что означает, что полученное решение является оптимальным. Предприятие получит максимальную прибыль от реализации выпускаемых изделий при выпуске х₁ = 140 ед. изделия А, х₂ = 120 ед. изделия В. При этом ресурсы первого и второго вида будут использованы полостью х₃ = х₄ = 0. По ресурсу третьего вида будет остаток х₅ = 100 кг. Прибыль предприятия от реализации изделий составит: f = 13200 (д.ед.).

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

Под названием «Транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

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

Ввиду того, что ранг системы векторов условий транспортной зада­чи равен m+n-1, опорное решение не может иметь отличных от нуля координат более m+n-1. Число отличных от нуля координат невы­рожденного опорного решения равно m+ n-1, а для вырожденного опорного решения меньше m+n-1.

Любое допустимое решение транспортной задачи можно записать в ту же таблицу, что и исходные данные. Клетки таблицы транспортной задачи, в которых находятся отличные от нуля или базисные нулевые перевозки, называются занятыми, остальные - незанятыми или свобод­ными. Клетки таблицы нумеруются так, что клетка, содержащая пере­возку x_ij, т.е. стоящая в i-й строке и j-м столбце, имеет номер (i, j). Каждой клетке с номером (i, j) соответствует переменная x_ij, которой соответствует вектор-условие A_ij..