МЕТОД ИСКУССТВЕННОГО БАЗИСА

Решение ЗЛП симплексными процедурами всегда начинается с определения какого-либо опорного плана. В рассмотренном ранее примере первоначальный опорный план выделялся за счет балансовых переменных.

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

Задача (29) – (31) называется исходной. На основании исходной составляют так называемую расширенную задачу.

Предполагая, что все в каждое из ограничений (30) вводят по искусственной переменной. Далее составляют искусственную линейную форму f, которая равна сумме всех введенных искусственных переменных.

Итак, в расширенной задаче будет переменных. Искусственные переменные образовывают базис, который называют искусственным. Основные переменные на первом этапе решения задачи будут свободными переменными. Расширенная задача имеет вид:

Представим расширенную задачу (32) – (35) в виде, разрешенном относительно базисных переменных

Вполне очевидно, что в системе ограничений (38) переменные входят в состав свободных. Тогда при условии имеем

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

Теорема 1.

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

Доказательство необходимости.

Пусть система ограничений-равенств (30) исходной задачи имеет допустимые планы. Например, это следующий набор чисел

.

Тогда, подставляя эти числа в систему ограничений (34) расширенной задачи, получим:

.

Тогда очевидно, что .

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

Доказательство достаточности.

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

Проанализируем набор чисел (40). Ясно, что такой набор будет удовлетворять системе ограничений (34), а значит, и системе ограничений (30). Из этого следует, что исходная система ограничений имеет, по крайней мере, одно допустимое решение, что и следовало доказать.

Теорема доказывает существование допустимых решений системы ограничений исходной задачи. Из существования допустимых решений следует существование опорных решений.

Для получения опорных решений необходимо из расширенной задачи вывести искусственный базис.

Теорема 2.

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

Доказательство аналогично доказательству теоремы 1.

Теорема 3.

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

Доказательство аналогично доказательству теоремы 1.

Метод искусственного базиса называют еще двухфазовым симплексным методом. Это объясняется следующим:

– Первая фаза решения задачи связана с оптиматизацией искусственной линейной формы f. На этом этапе решения выделяется первоначальный опорный план. Основная линейная форма F при этом ведет себя пассивно. Особенность первой фазы состоит в исключении из задачи искусственных переменных при условии выполнения прямодопустимости решения ЗЛП.

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

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

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

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

Представим расширенную задачу (44)–(46) в виде, разрешенном относительно базисных переменных

Далее составим первоначальную Жордановую таблицу, добавив в обычную таблицу ее одну строку – строку искусственной линейной формы f.

На первой фазе решения задачи исследуем на opt min искусственную линейную форму f (на каждом шаге модифицированных Жордановых исключений выводятся из задачи по одной искусственной переменной, так как они не будут участвовать в оптимизации линейной формы F).

–х2

–х3

–х4

–х 5

–х3

–х4

–х5

х1

–1

–2

–6

х1

–9

Þ

ξ2

–3

Þ

х2

–3

–9

:(3)

Þ

ξ3

–3

–6

ξ3

–9

–18

F

–1

F

–6

–3

f

f

–9

–18

Из последней Жордановой таблицы следует, что , следовательно, система ограничений исходной ЗЛП совместна. На левом бордюре сформировался базис переменных: х ₁, х ₂, х ₃ – базисные, х ₄, х ₅ – свободные переменные. Строка искусственной линейной формы, состоящая из одних нулей, может быть исключена из рассмотрения.

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

		–х4	–х5
х1			–1
х2			–1
х3		–1	–2
F		–2	–1

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

.

РЕШЕНИЕ ТРАНСПОРТНОЙ ЗАДАЧИ (ТЗ)
МЕТОДОМ ПОТЕНЦИАЛОВ

ТЗ – задача о наиболее экономном (оптимальном) плане перевозок однородного или взаимозаменяемого продукта из пунктов поставщика в пункты потребителя.

Постановка задачи. Имеется m пунктов А₁, А₂,..., А_m, в которых изготовляется либо хранится однородный или взаимозаменяемый продукт в количествах соответственно а₁, а₂,..., а_m. Этот продукт необходимо развести в n пункты потребителя В₁, В₂,..., В_n, где он востребован соответственно в количествах в₁, в₂,...в_n. Известны транспортные издержки (тарифы) c_ij, связанные с транспортировкой единицы продукции из i- ого пункта поставщика в j -ый пункт потребителя. Требуется составить такой план перевозок, который обеспечивал бы распределение продукта при минимальных транспортных издержках

Для наглядности ТЗ представляют в виде таблицы, которая называется распределительной.

Пост.	Потребитель	Зап.
В1	В2	В3	В4	Вn
А1	с11 х11	с12 х12	с13 х13		с1n х1n	a1
А2	с21 х21	с22 х22	с23 х23		с2n х2n	a2
А3	с31 х31	с32 х32	с33 х33		с3n х3n	a3
...	...	...	...	...	...	...
Аm	сm1 хm1	сm2 хm2	сm3 хm3		сmn хmn	am
Потр.	в1	в2	в3	...	вn

 

Матрица называется матрицей тарифов.

Для такой задачи неизвестной является матрица перевозок – (здесь х_ij означает количество груза, перевозимого из пункта i поставщика в пункт j потребителя.

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

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

Условием совместности системы ограничений является наличие баланса

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

Заметим, что открытую модель всегда можно привести к ее закрытому виду. Допустим, что , тогда в распределительную таблицу ТЗ вводится фиктивный (n + 1) пункт потребителя с запросом соответственно равным b . В то же время тарифы для данного пункта .

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

Особенности математической модели ТЗ:

1. Задача представлена первой канонической формой.

2. Коэффициенты при неизвестных в ограничениях равны 1.

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

4. Ранг системы ограничений ТЗ r = m + n –1.

5. Всего в ТЗ будет переменных, из них базисных , а свободных .

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

Поиск по сайту: