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

24.1 ОБЩАЯ ФОРМУЛИРОВКА ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

 

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

x_j – искомые неизвестные, переменные величины (j = 1,…., n);

a_ij – коэффициенты при неизвестных в уравнениях и неравенствах исходных ограничений;

b_i - величина ограничения в соответствующем уравнении или неравенстве;

с_j – коэффициенты, с которыми неизвестные х_j входят в целевую функцию.

 

Формулировка задачи на максимум при n неизвестных дает функцию цели вида

F = c₁x₁ + c₂x₂ + ….+ c_jx_j +….+ c_nx_n ® max.

Если мы имеем дело с канонической формой, то исходные ограничения задаются равенствами (в количестве m), т.е.

Выделяются требования неотрицательности неизвестных х_j, т.е.

х_j > 0.

Если мы имеем дело с производственными задачами, то ограничения в них обычно принимают форму неравенств (хотя бывают и равенства). Функция цели формулируется в них как на максимум, так и на минимум.

Тогда в общем виде и не в канонической форме задача линейного программирования записывается так:

F=c₁x₁+c₂x₂+...+c_jx_j+….+c_nx_n→max(min).

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

1. Если в ограничениях не все значения b_i положительны, т.е. имеются некоторые b_i < 0, то необходимо все члены соответствующего уравнения (неравенства) умножить на (-1).

2. Чтобы преобразовать ограничение, записанное в форме неравенства, его превращают в уравнение. Для этого в него добавляется фиктивное неизвестное. При этом стараются в каждое неравенство ограничения ввести собственную фиктивную переменную, знак которой зависит от вида неравенства. Так, в неравенстве вида «<» фиктивные переменные вводятся со знаком плюс, а в неравенства вида «>» - со знаком минус.

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

Примечание

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

 

 

24.2 ЗАПОЛНЕНИЕ СИМПЛЕКСНОЙ ТАБЛИЦЫ ПО СТРОКАМ

 

1. В первой верхней строке симплексной таблицы записываются показатели критерия оптимальности, т.е. коэффициенты при неизвестных в уравнении целевой функции F.

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

 

Симплексная таблица

			Показатели критерия оптимальности
с0	р^k	х0	Шапка матрицы (номера неизвестных хj)	å	a	b
Показатели критерия опти-мальности при неизвестных хj вошедших в план	Номера неизвестных хj вошедших в план	Итоговый столбец	Основание матрицы (коэффициенты при неизвестных хj в матрице ограничений)	Сумма элементов по строкам	Отношение элементов столбца х0 к элементам ключевого столбца	Коэффициент для пересчета элементов матрицы
		Значе-ние F	Целевая строка (двойственные оценки)

 

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

4. Последняя строка носит название целевой строки и заполняется двойственными оценками.

 

 

24.3 ЗАПОЛНЕНИЕ СИМПЛЕКСНОЙ ТАБЛИЦЫ ПО СТОЛЦАМ

 

1. Первый столбец – коэффициенты с_j.

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

a) Первая строка, в отличие от столбца, сохраняется лишь в первой симплексной таблице. Начиная со второй итерации верхняя строка перестает быть обязательной.

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

2. Второй столбец – р^k (индеек k – номер итерации).

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

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

3. Третий столбец – х₀.

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

4. Значение целевой функции F^k.

На пересечении итогового столбца в целевой строке указывается значение функционала F^k, соответствующее данному этапу решения, данной итерации k.

5. Столбцы «основания матрицы».

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

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

6. Последующие три столбца таблицы (å, a, b) имеют вспомогательное значения. Без этих столбцов можно обойтись, но они существенно облегчают проведение расчетов. Более подробно содержание этих столбцов будет рассматриваться ниже.

 

Пример

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

F = 15x₁ + 20x₂ +5x₃ ® max.

Приведем задачу к канонической форме. Для этого в каждое из неравенств системы введем по одному неизвестному (дополнительному) – х₄, х₅. х₆. Тогда

F = 15x₁ + 20x₂ +5x₃ ® max.

 

Заполним первую симплексную таблицу.

с0	р^0	х0	х1	х2	х3	х4	х5	х6	å	a	b
	х4
	х5
	х6
		F^0=?	?	?	?	?	?	?

 

Мы заполним все клетки, исходя из условий задачи.

Чтобы заполнить клетку F⁰ в первой таблице, необходимо просуммировать произведения элементов столбца х⁰ на элементы столбца с⁰, т.е.

F⁰ = 600∙0 + 520∙0 +600∙0 =0.

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

Для столбца х₁ величина двойственной оценки будет определяться

(0∙80+0∙15+0∙5) – 15=-15;

Для х₂: (0 35+0 60+0 5) – 20=-20;

х₃: (0 10+0 0+0 90) – 5=-5 и т.д.

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

Таблица 1

с0	р^0	х0	х1	х2	х3	х4	х5	х6	å	a	b
	х4
	х5
	х6
		F^0=0	-15	-20	-5

 

 

Решение:

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

Определение

Решение считается оптимальным, если все значения чисел в целевой строке положительны.

Если полученное решение не является оптимальным, то его можно улучшить. Для этого нужно:

1. Выбрать максимальное по абсолютной величине отрицательное значение числа в целевой строке.

В нашем примере таким числом будет (-20), находящееся в столбце «х₂». Именно это значение задает ключевой столбец.

Обратите внимание:

Ключевой столбец показывает, какое из х_j войдет в новое решение задачи. В нашем случае - неизвестное х₂.

Обратите внимания:

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

2. Выбрать минимальное значение частного от деления элементов столбца х₀ на элементы ключевого столбца. Результаты этих расчетов заносятся в столбец «a» симплексной таблицы.

В нашем примере эти отношения равны:

600/35=17,14;

520/60=8,67;

600/5=120.

Минимальное значение соответствует х₅ и равно 8,67. Это отношение задает ключевую строку.

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

В нашем примере ключевой элемент равен 60 и находится на пересечении столбца х₂ и строки х₅.

Обратите внимание:

Ключевым не может быть столбец, все элементы которого оказались отрицательными или нулевыми.

4. Просуммировать элементы матрицы по строкам (начиная от столбца х₀ и кончая столбцом х₆). Полученные суммы записываются в столбец «å».

5. Преобразовать ключевую строку. Для этого

a) Каждый элемент ключевой строки делится на ключевой элемент, начиная с элемента столбца «х₀»;

Фрагмент

х0	х1	х2	х3	х4	х5	х6
520/60	15/60	60/60	0/60	0/60	1/60	0/60

b) В столбце р¹ записывается х₂ вместо х₅;

c) В столбце с_j записывается значение критерия оптимальности при х₂, т.е. 20.

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

 

*

 

 

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

 

.

При пересчете величины функции цели получаем:

.

Аналогичным образом поступаем со всеми другими элементами таблицы. В итоге получаем новую симплексную таблицу.

Таблица 2.

с0	Р^1	х0	х1	х2	х3	х4	х5	х6	å	a	b
	х4	296,7	71,25				-0,58
	х2	8,7	0,25				0,017
	х6	556,7	3,75				-0,08
		1/3	-10				-0,33

 

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

Примечание 1.

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

Примечание 2.

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

Самостоятельно дорешайте эту задачу. В результате должно получиться:

F=236.7; x₁=3.31; x₂=7.8; x₃=6.05.

Примечание 3.

В столбце «b» записываются частные от деления элемента в ключевом столбце и строке i на ключевой элемент.

Примечание 4.

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

 

 

24.4 ДВОЙСТВЕННЫЕ ЗАДАЧИ, ОЦЕНКИ, ПРОБЛЕМЫ.

ДВОЙСТВЕННАЯ ФОРМУЛИРОВКА ЗАДАЧИ О ЗАГРУЗКЕ ОБОРУДОВАНИЯ

 

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

Есть несколько станков: А₁, А₂, …, А_m.

Задано максимальное время использования каждого из них: b₁, b₂, …, b_m.

На станках можно выпустить детали нескольких видов: В₁, В₂, …, В_n.

Известна величина прибыли, получаемой при продаже каждого изделия: с₁, с₂, …, с_j, …, c_n.

Известны показатели, характеризующие затраты времени станка А_i на выпуск одной детали В_j – матрица чисел (a_ij).

Требуется установить, сколько и каких деталей выпускать, т.е. найти значение неизвестных х₁, х₂, …, х_n.

Математически задача формулируется так:

F = c₁x₁ + c₂x₂ + ….+ c_jx_j +….+ c_nx_n ® max.

Двойственная постановка этой задачи естественна и ее легко объяснить.

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

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

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

Обозначим величины цен через , т.е. - цена за 1 час аренды станка А₁, - цена за 1 час аренды станка А₂ и т.д.

Сумма произведений возможного времени работы каждого станка на соответствующую цену должна быть минимальна:

.

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

Для выпуска одной детали расходуется а₁₁ часов работы станка А₁, а₂₁ часов работы станка А₂ и т.д. Значит за время, достаточное для ее выпуска, плата за аренду должна составить

.

Общая сумма должна быть не меньше прибыли при продаже им оной детали В₁.

Тогда система ограничений имеет вид

 

Решение двойственной задачи дает тот же результат, что и решение прямой задачи.

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

 

Ответы к вариантам:

Вар.1 S1-D1/40/, S2-D1/10/, S2-D2/10/, S2-D3/30/, S3-D3/40/, S4-D3/30/, S4-D4/20/.

Вар.2 S1-D1/90/, S2-D2/10/, S2-D2/50/, S3-D2/10/, S3-D3/80/, S3-D1/10/, S4-D4/20/.

Вар.3 S1-D1/20/, S2-D1/30/, S2-D2/40/, S3-D2/20/, S3-D3/10/,S4-D3/40/, S4-D4/40/.

Вар.4 S1-D1/40/, S2-D1/30/, S2-D2/30/, S3-D2/30/, S3-D3/10/, S4-D3/60/, S4-D4/20/.

Вар.5 S4-D1/30/, S1-D1/20/, S1-D2/40/, S2-D2/30/, S2-D2/30/,S3-D3/10/, S3-D4/40/.

Вар.6 S2-D1/60/, S1-D1/10/, S1-D2/30/, S4-D2/30/, S3-D3/20/, S3-D4/10/, S4-D4/60/.

Вар.7 S2-D1/20/, S1-D2/50/, S4-D2/50/, S2-D3/10/, S3-D4/10/, S4-D4/30/, S2-D4/10/.

Вар.8 S4-D1/20/, S2-D1/10/, S3-D1/70/, S3-D2/60/, S1-D3/80/, S3-D4/20/, S1-D4/10/.

Вар.9 S2-D1/10/, S4-D1/40/, S4-D3/10/, S3-D4/20/, S1-D3/80/, S3-D2/10/, S3-D3/10/.

Вар.10 S4-D1/20/, S2-D1/10/, S3-D2/60/, S1-D1/70/, S3-D3/80/, S1-D4/20/, S3-D4/10/.

Вар.11 S1-D3/50/, S2-D4/40/, S1-D2/10/, S3-D1/30/, S3-D2/30/, S4-D2/20/, S2-D2/10/.

Вар.12 S1 –D2/50/, S2-D1/40/, S2-D3/30/, S3-D3/10/, S3-D4/10/, S4-D4/50/, S1-D4/10/.

Вар.13 ЦФ=940, число итереций=5.