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

Пусть задана некоторая задача линейного программирования, система ограничений которой имеет следующий вид:

Решить данную задачу с помощью симплекс-метода, если целевая функция задана следующим соотношением:

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

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

1 итерация (k=1):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:

e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:

Для определения s-строки необходимо, прежде всего, рассчитать столбец g. Результаты расчетов представлены ниже:

			е
s

Тогда, очевидно (см. соотношение (14)), что на данной итерации индекс s строки равен 3, т.е.:

В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

			-18

2 итерация (k=2):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:

Для определения s-строки необходимо, прежде всего, рассчитать столбец g. Результаты расчетов представлены ниже:

		e
				-18
s

Тогда, очевидно (см. соотношение (14)), что на данной итерации индекс s строки равен 3, т.е.:

В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

	-1	-1	-20
	-1
		-1
	-2

3 итерация (k=3):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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

Пример. Задача о планировании производства.

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

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

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

, .

Решение:

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

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

Геометрическая интерпретация задачи о планировании производства

Решим теперь данную задачу симплекс-методом.

Прежде всего, как и в предыдущем примере, на основании исходных данных построим симплекс-таблицу:

1 итерация (k=1):

В соответствии с формулой (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма симплекс-метода найдем е-строку и s-столбец:

e-строке будет соответствовать максимальный положительный коэффициент при свободной переменной. Таким образом, определяем:

Для определения s-строки необходимо дополнительно рассчитать столбец значений g. Результаты расчетов представлены ниже:

			е
s

Тогда в соответствии с формулой (14) делаем вывод о том, что на данной итерации индекс s строки равен 4, т.е.:

Опираясь на соотношения (15), (16), (17) и (18), произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

		-1	-24

2 итерация (k=2):

В соответствии с формулой (13) вычислим текущее допустимое решение:

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

В соответствии с формулой (14) алгоритма найдем е-строку и s-столбец:

Для определения s-строки необходимо дополнительно рассчитать столбец значений g. Результаты расчетов представлены ниже:

		е
			-1	-24
s

Из приведенной таблицы видно (см. соотношение (14)), что на данной итерации индекс s строки равен 5, т.е.:

В соответствии с формулами (15), (16), (17) и (18) произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

	-2		-26
	-6
	-1

3 итерация (k=3):

В соответствии с формулой (13) вычислим текущее допустимое решение:

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

Снимем ранее введенные требования (A, B, C, D) к ЗЛП, расширив тем самым класс решаемых задач:

Требование А - если речь идет о минимизации функции F, то достаточно записать, что необходимо максимизировать (-F), то есть

min F = max (-F) (оператор М);

Требование В – если существует ограничения вида , то достаточно умножить их на (-1), чтобы требование В выполнялось (оператор N);

Требование C – если существуют переменные, принимающие отрицательные значения, то достаточно произвести замену:

, где (оператор P);

Требование D – если существует отрицательный свободный, член выполнить оператор К. Поиск опорного решения, иначе выполнить оператор L.

Поиск опорного решения (оператор К)

1. Выбрать любой отрицательные элемент строки, где стоит отрицательный свободный член, то есть выбираем е-столбец, если такого элемента нет, то система Ω допустимых решений не имеет.
2. Определяют s-строку:
3. Производят замену
4. Проверяют выполнение требования D.

Таким образом, общий алгоритм решений ЗЛП можно представить следующей схемой:

1.

Рассмотрим теперь решение симплекс-методом задачи линейного программирования заданной в форме, отличной от стандартной формы.

Пример. Задача линейного программирования в произвольной форме.

Пусть задана некоторая задача линейного программирования с линейной системой ограничений и целевой функцией, представленными ниже:

Решить данную задачу симплекс-методом.

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

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

По условию задачи необходимо минимизировать целевую функцию. Тогда, основываясь на результатах проверки условия A, применим к данной целевой функции оператор M. Новая симплекс таблица примет вид:

	-12	-8	-6

По условию задачи все неравенства системы линейных ограничений содержат знаки «больше или равно». Тогда, основываясь на результатах проверки условия B, применим к каждому неравенству данной системы ограничений оператор N. Новая симплекс таблица примет вид:

	-12	-8	-6
	-1	-1	-1	-2
	-2	-1		-3

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

1 итерация (k=1):

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

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

Для определения s-строки необходимо, прежде всего, рассчитать столбец g. Результаты расчетов представлены ниже:

		e
		-12	-8	-6
		-1	-1	-1	-2
S		-2	-1		-3

В соответствии с пунктом 2 алгоритма поиска опорного решения на данной итерации индекс s строки равен 5, т.е.:

В соответствии с формулами (15), (16), (17) и (18) алгоритма симплекс-метода произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

	-6	-2	-6
			-1

2 итерация (k=2):

Так как преобразованная система линейных ограничений содержит отрицательный свободный член (строка с индексом 4), т.е. выполняется условие D, то к полученной на предыдущем этапе симплекс-таблице необходимо снова применить оператор K – поиск опорного решения.

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

Для определения s-строки необходимо дополнительно рассчитать столбец g. Результаты расчетов представлены ниже:

			e
		-6	-2	-6
s				-1

В соответствии с пунктом 2 алгоритма поиска опорного решения на данной итерации индекс s строки равен 4, т.е.:

В соответствии с формулами (15), (16), (17) и (18) алгоритма симплекс-метода произведем замену e-столбца и s-строки. В результате получим следующую симплекс-таблицу:

	-4	-4	-2
		-2
	-1		-1

3 итерация (k=3):

В соответствии с выражением (13) вычислим текущее допустимое решение:

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