Симплекс-методом

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

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

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

Симплекс-метод применяется к задаче, записанной в канонической форме (используем одну из двойственных задач линейного программирования):

f(x) = 10Х₁ + 14Х₂ + 12Х₃ + 0×Х₄ + 0×Х₅ + 0×Х₆ ® max,

4X₁ + 2X₂ + X₃ + X₄ = 180,

3X₁ + X₂ + 3X₃ + X₅ = 210,

X₁ + 2X₂ + 5X₃ + X₆ = 244.

 

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

 

 

 

Базис Б	Коэффициенты функции цели Сi	План Хi	Коэффициенты функции цели Сj	q = (Хi / )min
Х1	Х2	Х3	Х4	Х5	Х6
Х2®Х4		180		2					180 / 2 = 90 min
Х5									210 / 1 =210
Х6									244 / 2 =122
F(x) = = 0	-10	-14	-12				ключевая строка
Значение целевой функции при данном опорном плане	min Ключевой элемент Оценки переменных Dj = - Cj
	Ключевой столбец

 

 

 

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

 

 

В первом столбце вписаны базисные неизвестные, второй содержит коэффициенты при базисных неизвестных в целевой функции, в третьем – правые части уравнений системы ограничений. Далее записана матрица из коэффициентов левой части системы ограничений , изменяющаяся в процессе пересчета. В верхней строке над неизвестными записаны соответствующие им коэффициенты в целевой функции. В последней строке записывается значение целевой функции при данном опорном плане, которое вычисляется по формуле f(x) = , и далее – оценки неизвестных, найденные по формуле D_j = - C_j.

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

Для определения ключевой строки находим отношения правых частей уравнений к положительным элементам ключевого столбца а^/_is. Полученные значения q записываются в последний столбец симплексной таблицы. Из них выбирается наименьшая величина, которая указывает на ключевую строку.

Пересчет таблицы производится по следующему правилу: элементы ключевой строки делятся на ключевой элемент. Далее, с помощью метода Жордана - Гаусса проводят пересчет таблицы таким образом, чтобы элементы ключевого столбца имели единицу на месте ключевого элемента и нули на месте всех остальных элементов. Для этого вычтем из элементов третьей строки соответствующие элементы первой строки, а из элементов второй строки – элементы первой строки, поделенные на два (на ключевой элемент).

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

Для каждого шага итерации строится своя симплексная таблица (рис.58).

Б	Сi	Х							q
Х1	Х2	Х3	Х4	Х5	Х6
Х2		90			1/2	1/2			90 : 1/2 = 180
Х5					5/2	-1/2			120 : 5/2 = 48
Х3®Х6			-3			-1			64 : 4 = 16 min
f(x) = 1260			-5
	Отрицательная оценка

Б	Сi	Х							q
Х1	Х2	Х3	Х4	Х5	Х6
Х2			19/8			5/8		-1/8
Х5			23/8			1/8		-5/8
Х3			-3/4			-1/4		1/4
f(x) = 1340	57/4		0	23/4		5/4
	Двойственные оценки сырья

 

Рис.58. Вторая и третья симплексные таблицы

Поскольку среди оценок неизвестных есть отрицательная, необходимо продолжить расчеты и составить новую таблицу. Для этого элементы третьей (ключевой) строки разделим на ключевой элемент. Умножив новые элементы третьей строки на 1/2, вычтем их из соответствующих элементов первой строки предыдущей таблицы. Затем, умножив новые элементы третьей строки на 5/2, вычтем их из соответствующих элементов второй строки предыдущей таблицы.

Поскольку среди оценок нет отрицательных, то это значит, что найдено оптимальное решение. Из таблицы видно, что при оптимальном плане следует выпускать изделий вида В в количестве 82 штук, изделий С – 16 штук. При этом остаются неиспользованными 80 кг сырья второго вида, а общий доход от продажи изделий составит 1340 ден.ед. Из таблицы также видно, что оптимальным решением двойственной задачи является Y* = (23/4, 0, 5/4), поскольку решение двойственной задачи находится в столбцах, соответствующих дополнительным переменным исходной задачи (Х₄, Х₅, Х₆).

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

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

Выпускать продукцию типа А невыгодно, а принудительный выпуск единицы данной продукции уменьшит доход на 57/4 = 14,25 ден.ед.

Так, увеличение количества сырья первого вида на 1 кг приведет к новому оптимальному плану производства изделий, при котором доход возрастет на 23/4 = 5,75 и станет равным 1345,75 ден.ед. При этом числа, стоящие в столбце Х₄ последней симплексной таблицы, покажут, что это может быть достигнуто за счет увеличения выпуска изделий В на 5/8 единиц и сокращения выпуска изделий С на 1/4 единицы. Использование сырья второго вида уменьшится при этом на 1/8 кг.

Также увеличение на 1 кг сырья третьего вида дает новый оптимальный план, при котором доход возрастет на 5/4 = 1,25 ден.ед. и составит 1341,25 ден.ед. Это будет достигнуто за счет увеличения выпуска изделия С на 1/4 единицы и уменьшения выпуска изделия В на 1/8 единицы, причем объем используемого сырья второго вида возрастет на 5/8 кг.

Вычислим минимальное значение целевой функции двойственной задачи:

F(y) = 180 × 23/4 + 210 × 0 + 244 × 5/4 = 1340,

оно совпадает с максимальным значением целевой функции исходной задачи.

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

23 + 5/4 > 10,

23/2 + 5/2 = 14,

23/4 + 25/4 = 12.

 

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

 

Для расчёта оптимизационных задач линейного программирования в среде Excel (рис. 59) необходимо ввести в таблицу коэффициенты левой части ограничений (например, в ячейки B3 : D5) и коэффициенты функции цели (например, в ячейки B6 : D6). Для размещения искомых значений переменных необходимо зарезервировать свободные ячейки (например, ячейки B8 : D8). Математические выражения для системы ограничений и целевой функции вводятся (например, в ячейки Е3 : Е5 и Е6 соответственно) с помощью функции СУММПРОИЗВ из категории Математические (рис. 60). Для этого необходимо выбрать в меню Вставка строку Функция….

 

 

Рис. 59. Ввод исходной информации оптимизационной задачи

 

 

Рис. 60. Выбор функции СУММПРОИЗВ

 

При заполнении диалоговой формы функции СУММПРОИЗВ одним из массивов являются адреса ячеек коэффициентов левой части каждого из ограничений в отдельности (для первого ограничения D3:D3) и коэффициентов целевой функции (B6:D6), выделяемых с помощью мышки. Другим массивом являются адреса ячеек, предназначенных для размещения искомых переменных (B8:D8). Для копирования функции с помощью протягивания за маркер заполнения, необходимо установить абсолютную адресацию для ячеек, предназначенных для размещения переменных путём нажатия служебной клавиши F4 на клавиатуре. Адреса ячеек примут вид $B$3:$D$3 (рис. 61).

 

 

Рис. 61. Заполнение диалоговой формы

функции СУММПРОИЗВ

 

Маркер заполнения находится в нижнем правом углу выделенной ячейки. Для копирования формулы необходимо подвести курсор мышки к маркеру заполнения до появления чёрного крестика (рис. 62) и при нажатой левой кнопке мышки протянуть её через ячейки, в которые должны быть помещены копии формулы. При этом, адреса ячеек, имеющие абсолютную адресацию (например, B3:D3) будут изменяться, а ячейки, имеющие абсолютную адресацию (например, $B$8:D$8) не изменят её (рис. 59). Для просмотра формул в меню Сервис выбрать строку Параметры установить флажок Отображать формулы.

 

 

Рис. 62. Копирование функции протягиванием за маркер

заполнения

 

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

 

 

Рис. 63. Установка программы Поиск решения

 

В MS Office 2007 для загрузки надстройки Поиск решения следует щёлкнуть значок – кнопку MS Office, выбрать Параметры Excel, команду Надстройки, в окне Управление – Надстройки Excel, нажать кнопку Перейти, в окне Доступные надстройки установить флажок Поиск решения.

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

 

 

Рис. 64. Диалоговая форма Поиск Решения

 

Затем нужно выбрать направление поиска экстремума целевой функции (max или min), поставив точку у максимального или минимального значения.

Изменяя значения ячеек, в которых располагаются искомые переменные Поиск решения ищет оптимальное решение. Указать это можно щёлкнув левой кнопкой мышки в окне Изменяя ячейки и выделив мышкой адреса B8:D8.

Добавить к задаче ограничения следует нажав кнопку Добавить, заполнить соответствующую форму (рис. 65).

 

 

Рис. 65. Диалоговая форма Добавить ограничения

 

В левое окно формы Добавить ограничения нужно ввести адреса ячеек, содержащих математические выражения (формулы) левых частей ограничений (E3:E5), затем нужно выбрать знак ограничения (< = , =или > =) и в правое окно формы ввести адреса ячеек (F3:F5), содержащих числовые значения правой части ограничений (менее предпочтительно введение в окно конкретных чисел).

Добавить новое ограничение, изменить или удалить его можно с помощью соответствующих кнопок. Кроме того, необходимо установить Параметры поиска решения (рис. 66), нажав одноимённую кнопку.

 

 

Рис. 66. Заполнение диалоговой формы Параметры

 

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

Решение задачи получим, нажав кнопки ОК и Выполнить. В диалоговом окне Результаты поиска решения (рис. 67) для вывода необходимых отчётов следует выделить их последовательно щёлкнув левой кнопкой мышки.

 

 

Рис. 67. Диалоговое окно Результаты поиска решения

 

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

 

 

Рис. 68. Результаты решения задачи

 

Отчёт по результатам, который выводится на отдельный лист (рис. 69), помогает проанализировать решение. Так, для получения дохода, равного 1340 ден.ед. (ячейка Е6), необходимо выпускать продукцию вида В в количестве 82 штук (ячейка С8) и продукцию вида С – в количестве 16 штук (ячейка D8). Продукцию вида А выпускать нерентабельно (ячейка В8). Из 210 единиц сырья II вида используется только 130 (ячейка Е4). Другие два вида сырья используются полностью. Второе ограничение задачи не связанное, т.е. оно не равно правой части, а отличается, в данном случае остаются неизрасходованными запасы сырья II вида в количестве 80 единиц (210 – 130 = 80).

 

Рис. 69. Отчёт по результатам

 

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

 

Рис. 70. Отчёт по устойчивости

 

Отчёт по пределам (рис. 71) показывает, в каких границах может изменяться выпуск продукции, вошедший в оптимальное решение, при сохранении структуры оптимального решения. Также показаны значения целевой функции при выпуске данного вида продукции на нижнем пределе. Так, если не выпускать продукцию вида В, то доход составит 192 ден.ед., если же не выпускать продукцию вида С, то доход будет равен 1148 ден.ед.

 

Рис. 71. Отчёт по пределам

Тема 5. ТРАНСПОРТНАЯ ЗАДАЧА

Математическая постановка задачи состоит в определении оптимального плана перевозок некоторого груза из m пунктов отправления A₁, A₂, …, A_m в n пунктов назначения B₁, B₂, …, B_n. При этом в качестве критерия оптимальности обычно выбирается либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки.

Обозначим через C_ij стоимость перевозки единицы груза из i–го пункта отправления в j–й пункт назначения; а_i - запасы груза в i–м пункте отправления (величина предложения); b_j - потребности в этом грузе в j–м пункте назначения (величина спроса); X_ij - объем перевозок (количество перемещаемых единиц груза) из i–го пункта отправления в j–й пункт назначения. Тогда математическая модель транспортной задачи имеет следующий вид: определить минимум целевой функции

f(x) = ® min (5.1)

при выполнении следующих ограничений:

= а_i; i = , (5.2)

= b_j; j = , (5.3)

Х_ij ³ 0; i = ; j = . (5.4)

 

Обычно исходные данные транспортной задачи представляются в виде таблицы. Внутренняя часть этой таблицы является объединением двух матриц: матрицы перевозок Х = { X_ij } и матрицы стоимостей С = { С_ij }.

 

Пункты отправления	Пункты назначения	Запасы (предложение)
В1	В2	…	Вj	…	Вn
А1	С11 Х11	С12 Х12	…	C1j Х1j	…	C1n Х1n	а1
А2	С21 Х21	С22 Х22	…	C2j Х2j	…	C2n Х2n	а2
…	…	…	…	…	…	…	…
Аi	Сi1 Хi1	Сi2 Хi2	…	Сij Хij	…	Сin Хin	аi
…	…	…	…	…	…	…	…
Аm	Сm1 Хm1	Сm2 Хm2	…	Сmj Хmj	…	Сmn Хmn	аm
Потреб-ности (спрос)	b1	b2	…	bj	…	bm	Sbj = Sаi

 

Если общий запас груза у поставщиков равен потребности в грузе у потребителей, т.е. если выполняется условие

= , (5.5)

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

Определение 1. Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей Х = { X_ij }; i = ; j = , называется планом транспортной задачи.

Определение 2. План Х* = {X_ij*}, при котором функция цели 1 принимает минимальное значение, называется оптимальным планом транспортной задачи.

Ограничения 2 и 3 транспортной задачи представляют собой две группы уравнений. Первая из них, т.е. система уравнений 2, означает то, что сумма перевозок по каждой строке таблицы должна быть равна соответствующему запасу а_i. Каждое уравнение второй системы 3 означает то, что сумма перевозок по каждому столбцу таблицы должна быть равна соответствующей потребности b_j. Транспортная задача представляет собой задачу линейного программирования, записанную в каноническом виде. Следовательно, ее можно решать симплексным методом. Однако для решения транспортных задач существуют специальные методы.

Особенности транспортной задачи:

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

2. Если значения и а_i-е и b_j-е – целые и неотрицательные, то транспортная задача имеет целочисленное решение.

3. Клетки таблицы транспортной задачи с координатами, в которых проставлены значения перевозок, называются базисными и соответствуют базисным переменным, а остальные клетки остаются свободными. Для невырожденного опорного плана в таблице транспортной задачи будет заполнена положительными числами m + n – 1 клетка. Если же опорный план задачи вырожден, то часть базисных клеток будет заполнена нулями.