aqua-kop.ru

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

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

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

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

Таблица 1.

базисные переменные Свободные члены в ограничениях Небазисные переменные
x 1 x 2 ... x l ... x n
x n+1 b 1 a 11 a 12 ... a 1l ... a 1n
x n+2 b 2 a 21 a 22 ... a 2l ... a 2n
. . . . . . . .
. . . . . . . .
. . . . . . . .
x n+r b2 a r1 a r2 ... a rl ... a rn
. . . . . . . .
. . . . . . . .
. . . . . . . .
x n+m b m a m1 a m2 ... a ml ... a mn
F(x) max F 0 -c 1 -c 2 ... -c 1 ... -c n

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

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

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

Двойственный симплексный метод основан на теории двойственности (см. решение двойственной задачи) и используется для решения задач линейного программирования, свободные члены которых b i могут принимать любые значения, а система ограничений задана неравенствами смысла «≤», «≥» или равенством «=».

Назначение сервиса . Онлайн-калькулятор используется для решения задач линейного программирования P-методом в следующих формах записи: базовой форме записи симплекс-метода, в виде симплексной таблицы, модифицированным симплекс-методом.

Инструкция для решения задач двойственным симплекс-методом . Выберите количество переменных и количество строк (количество ограничений), нажмите Далее. Полученное решение сохраняется в файле Word . При этом ограничения типа x i ≥0 не учитывайте.

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Решение транспортной задачи
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных

Задачи динамического программирования
Распределить 5 однородных партий товара между тремя рынками так, чтобы получить максимальный доход от их продажи. Доход от продажи на каждом рынке G(X) зависит от количества реализованных партий товара Х и представлен в таблице.

Объем товара Х (в партиях) Доход G(X)
1 2 3
0 0 0 0
1 28 30 32
2 41 42 45
3 50 55 48
4 62 64 60
5 76 76 72

В P-методе оптимальный план получается в результате движения по псевдопланам. Псевдоплан - план, в котором условия оптимальности удовлетворяются, а среди значений базисных переменных x i имеются отрицательные числа. Алгоритм двойственного симплекс-метода включает следующие этапы:

  1. Составление псевдоплана . Систему ограничений исходной задачи приводят к системе неравенств смысла «≤».
  2. Проверка плана на оптимальность . Если в полученном опорном плане не выполняется условие оптимальности, то задача решается симплексным методом .
  3. Выбор ведущих строки и столбца . Среди отрицательных значений базисных переменных выбираются наибольшие по абсолютной величине. Строка, соответствующая этому значению, является ведущей.
  4. Расчет нового опорного плана . Новый план получается в результате пересчета симплексной таблицы методом Жордана-Гаусса . Далее переход к этапу 2.
Двойственный симплекс-метод заключается в построении оптимального недопустимого плана с последующим преобразованием его в допустимый, не нарушая оптимальности.

Алгоритм двойственного симплекс-метода

1) выбирают разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных членов;
2) выбирают разрешающий столбец по наименьшему по абсолютной величине отношению элементов L строки к отрицательным элементам разрешающей строки;
3) пересчитывают симплексную таблицу по правилам обычного симплекс-метода;
4) решение проверяют на оптимальность. Признаком получения допустимого оптимального решения является отсутствие в столбце свободных членов отрицательных элементов.
Замечания
1. Если в разрешающей строке нет ни одного отрицательного элемента, задача неразрешима.
2. Если ограничения задачи заданы неравенствами типа «≥», двойственный симплекс-метод позволяет избавиться от необходимости введения искусственных переменных.

Особенности двойственного симплекс-метода Используются при решении методом Гомори .

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

L = x 1 + 4x 2 → min
2х 1 +3х 2 +4х 3 ≥ 20
5х 1 -х 2 +2х 3 ≥ 12
х 1 +2х 2 -х 3 ≤ 2
х 1 +4х 2 -2х 3 ≤ 1
х 1 , х 2 , х 3 ≥ 0

Составляем исходную симплексную таблицу.

Баз. x 1 x 2 x 3 x 4 x 5 x 6 x 7 Св.
x 4 -2 -3 -4 1 0 0 0 -20
x 5 -5 1 -2 0 1 0 0 -12
x 6 1 2 -1 0 0 1 0 2
x 7 -1 4 -2 0 0 0 1 1
L -1 -4 -1 0 0 0 0 0

Отсутствие в L строке положительных оценок свидетельствует об оптимальности исходного решения, а наличие в столбце свободных членов отрицательных элементов – о его недопустимости. Согласно алгоритму двойственного симплекс-метода выбираем разрешающую строку по наибольшему по абсолютной величине отрицательному элементу столбца свободных элементов. В нашем примере разрешающая строка – первая. Разрешающий столбец выбирается в соответствии с правилом, изложенным в пункте 2 схемы алгоритма. Разрешающий элемент равен (-4). После пересчета получаем следующую таблицу

Баз. х 1 х 2 х 3 х 4 х 5 х 6 х 7 Св.
х 3 1/2 3/4 1 -1/4 0 0 0 5
х 5 -4 5/2 0 -1/2 1 0 0 -2
х 6 3/2 11/4 0 -1/4 0 1 0 7
х 7 0 11/2 0 -1/2 0 0 1 11
L -1/2 -13/4 0 -1/4 0 0 0 5

Аналогично рассуждая, получим еще одну таблицу

Баз. х 1 х 2 х 3 х 4 х 5 х 6 х 7 Св.
х 3 0 17/16 1 -5/16 1/8 0 0 19/4
х 1 1 -5/8 0 1/8 -1/4 0 0 1/2
х 6 0 59/16 0 -7/16 3/8 1 0 25/4
х 7 0 11/2 0 -1/2 0 0 1 11
L 0 -57/16 0 -3/16 -1/8 0 0 21/4

Отсутствие в столбце свободных членов отрицательных элементов свидетельствует о том, что получено оптимальное решение Lmin=21/4, X min(1/2; 0; 19/4; 0; 25/4; 11).
Замечание . Если решение ЗЛП и недопустимо и неоптимально, то сначала получаем допустимое решение, используя алгоритм двойственного симплекс-метода, а затем по правилам обычного симплекс-метода получаем оптимальное решение.

Пример .
L = 5x 1 – x 2 – x 3 → max
или

Составляем исходную симплекс-таблицу

x 1 x 2 x 3 x 4 x 5 x 6 x 7 Св.
x 4 0 -1 -2 1 0 0 0 -9
x 5 1 -1 0 0 1 0 0 -1
x 6 -1 -1 3 0 0 1 0 -8
x 7 1 0 -1 0 0 0 1 4
L -5 1 4 0 0 0 0 0

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

Баз. x 1 x 2 x 3 x 4 x 5 x 6 x 7 Св.
x 2 0 1 2 -1 0 0 0 9
x 5 1 0 2 -1 1 0 0 8
x 6 -1 0 5 -1 0 1 0 1
x 7 -1 0 -1 0 0 0 1 4
L -5 0 2 1 0 0 0 -9
В столбце свободных членов нет отрицательных элементов, но в строке L есть отрицательная оценка (-5), значит решение допустимо, неоптимально.
Используем обычный симплекс-метод и получаем следующие таблицы
Баз. x 1 x 2 x 3 x 4 x 5 x 6 x 7 Св.
x 2 0 1 2 -1 0 0 0 9
х 5 0 0 3 -1 1 0 -1 4
х 6 0 0 -4 -1 0 1 1 5
x 1 1 0 -1 0 0 0 1 4
L 0 0 -3 1 0 0 5 11
Баз. x 1 x 2 x 3 x 4 x 5 x 6 x 7 Св.
x 2 0 1 0 -1/2 0 -1/2 -1/2 13/2
x 5 1 0 0 -1/4 1 -3/4 -7/4 1/4
x 6 0 0 1 -1/4 0 1/4 1/4 5/4
x 1 0 0 0 -1/4 0 1/4 5/4 21/4
L 0 0 0 1/4 0 3/4 23/4 59/4

Отсутствие в строке L отрицательных оценок свидетельствует о том, что получено оптимальное решение.
Lmax=59/4, X max(21/4; 13/2; 5/4; 0; 1/4; 0; 0).

Пример . Предприятию необходимо выпустить по плану продукции А1 единиц, А2 единиц, А3 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P–метода.

Известно, что содержание n питательных веществ A, B и С в рационе должно быть не менее m1, m2, m3 единиц соответственно. Указанные питательные вещества содержат три вида продуктов. Содержание единиц питательных веществ в одном килограмме каждого из видов продукта приведено в таблице. определите дневной рацион, обеспечивающий получение необходимого количества питательных веществ при минимальных денежных затратах.

Задание : Решить задачу, используя алгоритм двойственного симплекс-метода.
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = 4x 1 + 2x 2 + x 3 при следующих условиях-ограничений.
- x 1 - x 2 ≤-10
2x 1 + x 2 - x 3 ≤8
переход к канонической форме).
В первом неравенстве смысла (≤) вводим базисную переменную x 4 . Во втором неравенстве смысла (≤) вводим базисную переменную x 5 .
-1x 1 -1x 2 + 0x 3 + 1x 4 + 0x 5 = -10
2x 1 + 1x 2 -1x 3 + 0x 4 + 1x 5 = 8

A =
-1 -1 0 1 0
2 1 -1 0 1
Решим систему уравнений относительно базисных переменных:
x 4 , x 5 ,
Полагая, что свободные переменные равны нулю, получим первый опорный план:
X1 = (0,0,0,-10,8)
Базис B x 1 x 2 x 3 x 4 x 5
x 4 -10 -1 -1 0 1 0
x 5 8 2 1 -1 0 1
F(X0) 0 -4 -2 -1 0 0

Итерация №1

План 0 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.


Ведущей будет первая строка, а переменную x 4 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует 2-му столбцу, т.е. переменную x 2 необходимо ввести в базис.

Базис B x 1 x 2 x 3 x 4 x 5
x 4 -10 -1 -1 0 1 0
x 5 8 2 1 -1 0 1
F(X0) 0 -4 -2 -1 0 0
θ 0 -4: (-1) = 4 -2: (-1) = 2 - - -

4. Пересчет симплекс-таблицы. Выполняем преобразования симплексной таблицы методом Жордано-Гаусса .
Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 5 -2 1 0 -1 1 1
F(X0) 20 -2 0 -1 -2 0

Представим расчет каждого элемента в виде таблицы:
B x 1 x 2 x 3 x 4 x 5
-10: -1 -1: -1 -1: -1 0: -1 1: -1 0: -1
8-(-10 1):-1 2-(-1 1):-1 1-(-1 1):-1 -1-(0 1):-1 0-(1 1):-1 1-(0 1):-1
0-(-10 -2):-1 -4-(-1 -2):-1 -2-(-1 -2):-1 -1-(0 -2):-1 0-(1 -2):-1 0-(0 -2):-1

Итерация №2
1. Проверка критерия оптимальности.
План 1 в симплексной таблице является псевдопланом, поэтому определяем ведущие строку и столбец.
2. Определение новой свободной переменной.
Среди отрицательных значений базисных переменных выбираем наибольший по модулю.
Ведущей будет вторая строка, а переменную x 5 следует вывести из базиса.
3. Определение новой базисной переменной. Минимальное значение θ соответствует третьему столбцу, т.е. переменную x 3 необходимо ввести в базис.
На пересечении ведущих строки и столбца находится разрешающий элемент (РЭ), равный (-1).

Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 5 -2 1 0 -1 1 1
F(X0) 20 -2 0 -1 -2 0
θ 0 - - -1: (-1) = 1 - -

4. Пересчет симплекс-таблицы. Выполняем преобразования.
Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 3 2 -1 0 1 -1 -1
F(X1) 22 -3 0 0 -3 -1
Или более подробно:
B x 1 x 2 x 3 x 4 x 5
10-(-2 0):-1 1-(1 0):-1 1-(0 0):-1 0-(-1 0):-1 -1-(1 0):-1 0-(1 0):-1
-2: -1 1: -1 0: -1 -1: -1 1: -1 1: -1
20-(-2 -1):-1 -2-(1 -1):-1 0-(0 -1):-1 -1-(-1 -1):-1 -2-(1 -1):-1 0-(1 -1):-1

В базисном столбце все элементы положительные. Переходим к основному алгоритму симплекс-метода.

Итерация №3
1. Проверка критерия оптимальности.
Среди значений индексной строки нет положительных. Поэтому эта таблица определяет оптимальный план задачи.

Базис B x 1 x 2 x 3 x 4 x 5
x 2 10 1 1 0 -1 0
x 3 2 -1 0 1 -1 -1
F(X1) 22 -3 0 0 -3 -1

Оптимальный план можно записать так: x 1 = 0, x 2 = 10, x 3 = 2
F(X) = 2 10 + 1 2 = 22

Пример №2 . Задание.
5x 1 + 6x 2 ≥1
15x 1 ≥1
7x 1 + 12x 2 ≥1
Приведем систему ограничений к системе неравенств смысла ≤, умножив соответствующие строки на (-1).
Определим минимальное значение целевой функции F(X) = x 1 + x 2 при следующих условиях-ограничений.
- 5x 1 - 6x 2 ≤-1
- 15x 1 ≤-1
- 7x 1 - 12x 2 ≤-1
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме ).
В 1-м неравенстве смысла (≤) вводим базисную переменную x 3 . В 2-м неравенстве смысла (≤) вводим базисную переменную x 4 . В 3-м неравенстве смысла (≤) вводим базисную переменную x 5 .
-5x 1 -6x 2 + 1x 3 + 0x 4 + 0x 5 = -1
-15x 1 + 0x 2 + 0x 3 + 1x 4 + 0x 5 = -1
-7x 1 -12x 2 + 0x 3 + 0x 4 + 1x 5 = -1
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

A= -5 -6 1 0 0
-15 0 0 1 0
-7 -12 0 0 1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.

x 3 , x 4 , x 5 ,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,-1,-1,-1)
Базисное решение называется допустимым, если оно неотрицательно.
Базис B x 1 x 2 x 3 x 4 x 5
x 3 -1 -5 -6 1 0 0
x 4 -1 -15 0 0 1 0
x 5 -1 -7 -12 0 0 1
F(X0) 0 -1 -1 0 0 0

Пример решения Р-методом

Условие задачи . Предприятию необходимо выпустить по плану продукции А 1 – 500 единиц, А 2 – 300 единиц, А 3 – 450 единиц. Каждый вид изделия может производиться на двух машинах.
Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальны? Дана матрица затрат и ресурс времени каждой машины. Записать модель исследуемой операции в форме, допускающей использование P – метода.
Составим математическую модель задачи.
2x 11 + 3x 12 +3x 13 ≤ 1500
5x 21 + 4x 22 +x 23 ≤ 1000
x 11 + x 21 ≥ 500
x 12 + x 22 ≥ 300
x 13 + x 23 ≥ 450
Целевая функция:
2x 11 + 3x 12 +3x 13 + 5x 21 + 4x 22 +x 23 → min
Запишем в виде, решаемом Р-методом.
2x 11 + 3x 12 +3x 13 ≤ 1500
5x 21 + 4x 22 +x 23 ≤ 1000
-x 11 -x 21 ≤ -500
-x 12 -x 22 ≤ -300
-x 13 -x 23 ≤ -450
Определим минимальное значение целевой функции F(X) = 2x 1 +3x 2 +3x 3 +5x 4 +4x 5 +x 6 при следующих условиях-ограничений.
2x 1 +3x 2 +3x 3 ≤1500
5x 4 +4x 5 +x 6 ≤1000
-x 1 -x 4 ≤-500
-x 2 -x 5 ≤-300
-x 3 -x 6 ≤-450
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
2x 1 + 3x 2 + 3x 3 + 0x 4 + 0x 5 + 0x 6 + 1x 7 + 0x 8 + 0x 9 + 0x 10 + 0x 11 = 1500
0x 1 + 0x 2 + 0x 3 + 5x 4 + 4x 5 + 1x 6 + 0x 7 + 1x 8 + 0x 9 + 0x 10 + 0x 11 = 1000
-1x 1 + 0x 2 + 0x 3 -1x 4 + 0x 5 + 0x 6 + 0x 7 + 0x 8 + 1x 9 + 0x 10 + 0x 11 = -500
0x 1 -1x 2 + 0x 3 + 0x 4 -1x 5 + 0x 6 + 0x 7 + 0x 8 + 0x 9 + 1x 10 + 0x 11 = -300
0x 1 + 0x 2 -1x 3 + 0x 4 + 0x 5 -1x 6 + 0x 7 + 0x 8 + 0x 9 + 0x 10 + 1x 11 = -450
Матрица коэффициентов A = a(ij) этой системы уравнений имеет вид:

2

3

3

0

0

0

1

0

0

0

0

0

0

0

5

4

1

0

1

0

0

0

-1

0

0

-1

0

0

0

0

1

0

0

0

-1

0

0

-1

0

0

0

0

1

0

0

0

-1

0

0

-1

0

0

0

0

1
Базисные переменные это переменные, которые входят только в одно уравнение системы ограничений и притом с единичным коэффициентом.
Решим систему уравнений относительно базисных переменных:
x 7 , x 8 , x 9 , x 10 , x 11 ,
Полагая, что свободные переменные равны 0, получим первый опорный план:
X1 = (0,0,0,0,0,0,1500,1000,-500,-300,-450)

План

Базис

В

x 1

x 2

x 3

x 4

x 5

x 6

x 7

x 8

x 9

x 10

x 11

0

x 7

1500

2

3

3

0

0

0

1

0

0

0

0


x 8

1000

0

0

0

5

4

1

0

1

0

0

0


x 9

-500

-1

0

0

-1

0

0

0

0

1

0

0


x 10

-300

0

-1

0

0

-1

0

0

0

0

1

0


x 11

-450

0

0

-1

0

0

-1

0

0

0

0

1

Индексная строка

F(X0)

0

-2

-3

-3

-5

-4

-1

0

0

0

0

0

θ



2



5







Оптимальный план можно записать так: x 5 = 133.33, x 8 = 16.67, x 1 = 500, x 2 = 166.67, x 6 = 450
F(X) = 2*500 + 3*166.67 + 4*133.33 + 1*450 = 2483.33

Пример №1 . Предприятию необходимо выпустить по плану продукции, не менее, чем: А 1 - 500 единиц, А2 – 300 единиц, А 3 – 450 единиц. Каждый вид изделия может производиться на двух машинах. Как распределить работу машин, чтобы общие затраты времени на выполнение плана были минимальными, если задана матрица затрат. Ресурс времени каждой машины приведен справа от таблицы. Записать модель исследуемой операции в форме, допускающей использование Р-метода. Решить задачу Р-методом.

Пример №2 . Из 4 видов кормов необходимо составить рацион, в состав которого должно входить не менее в1 ед. вещества А, в 2 ед. вещества В и в 3 ед. вещества С. Количество единиц вещества, содержащегося в 1 кг корма каждого вида, указано в соответствующей таблице. В ней же приведена цена 1 кг корма каждого вида.
Составить рацион, содержащий не менее нужного количества указанных питательных веществ и имеющий минимальную стоимость.

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

рубашка 1 рубашка 2 рубашка 3 Запасы нитки (м.) 1 9 3 96 пуговицы (шт.) 20 10 30 640 ткань ( 1 2 2 44 Прибыль (р.) 2 5 4

Решение задачи

Построение модели

Через и количество рубашек 1-го, 2-го и 3-го вида, предназначенных к выпуску.

Тогда ограничения на ресурсы будут иметь следующий вид:

Кроме того, по смыслу задачи

Целевая функция, выражающая получаемую прибыль:

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

Приведение задачи линейного программирования к каноническому виду

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

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

Заполняем симплексную таблицу:

Так как мы решаем задачу на максимум – наличие в индексной строке отрицательных чисел при решении задачи на максимум свидетельствует о том, что нами оптимальное решение не получено и что от таблицы 0-й итерации необходимо перейти к следующей.

Переход к следующей итерации осуществляем следующим образом:

ведущий столбец соответствует

Ключевая строка определяется по минимуму соотношений свободных членов и членов ведущего столбца (симплексных отношений):

На пересечении ключевого столбца и ключевой строки находим разрешающий элемент, т.е. 9.

Теперь приступаем к составлению 1-й итерации: Вместо единичного вектора вводим вектор .

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

Ключевой столбец для 1-й итерации соответствует

Разрешающим элементов является число 4/3. Вектор выводим из базиса и вводим вместо него вектор . Получаем таблицу 2-й итерации.

Ключевой столбец для 2-й итерации соответствует

Находим ключевую строку, для этого определяем:

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

БП c Б A o x 1 x 2 x 3 x 4 x 5 x 6 Симплексные 2 5 4 0 0 0 отношения 0 x 4 0 96 1 9 3 1 0 0 32/3 x 5 0 640 20 10 30 0 1 0 64 x 6 0 44 1 2 2 0 0 1 22 F j - c j 0 -2 -5 -4 0 0 0 1 x 2 5 32/3 1/9 1 1/3 1/9 0 0 32 x 5 0 1600/3 170/9 0 80/3 -10/9 1 0 20 x 6 0 68/3 7/9 0 4/3 -2/9 0 1 17 F j - c j 160/3 -13/9 0 -7/3 5/9 0 0 2 x 2 5 5 -1/12 1 0 1/6 0 -1/4 -- x 5 0 80 10/3 0 0 10/3 1 -20 24 x 3 4 17 7/12 0 1 -1/6 0 3/4 204/7 F j - c j 93 -1/12 0 0 1/6 0 7/4 3 x 2 5 7 0 1 0 1/4 1/40 -3/4 x 1 2 24 1 0 0 1 3/10 -6 x 3 4 3 0 0 1 -3/4 -7/40 17/4 F j - c j 95 0 0 0 1/4 1/40 5/4

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

Необходимо шить 24 рубашки 1-го вида, 7 рубашек 2-го вида и 3 рубашки 3-го вида. При этом получаемая прибыль будет максимальна и составит 95 руб.

Для разрешения выполнения апплета на вашем компьютере надо сделать следующее - нажать кнопку Пуск>Панель управления>Программы>Java. В окне Java Control Panel выбираем вкладку Security (Безопасность) нажимаем кнопку Edit Site List, кнопку add и вставляем в свободное поле путь к этой страницы из адресной строки браузера. Далее нажимаем кнопки ОК, после этого перезагружаем компьютер.

Для запуска апплета нажмите на кнопку "Simplex". Если над этой строкой не видна кнопка "Simplex", то на компьютере не установлена Java.

    После нажатия на кнопку « Simplex » выводится первое окно для ввода числа переменных и числа ограничений задачи на симплекс-метод.

    После нажатия на кнопку « ok » выводится окно для ввода остальных данных задачи на симплекс-метод: режима отображения (десятичные дроби или обыкновенные), тип критерия задачи min или max , ввод коэффициентов целевой функции и коэффициентов системы ограничений со знаками « ≤ », « ≥ » или « = », ограничения вида х i ≥ 0 вводить не надо, их учитывает в своем алгоритме.

    После нажатия на кнопку «Решить» выводится окно с результатами решения задачи на . Окно состоит из двух частей, в верхней части находится текстовое поле, содержащее описание приведения исходной задачи к канонической форме, которая используется для составления первой симплекс-таблицы. В нижней части окна в панели со вкладками расположены симплекс-таблицы каждой итерации с небольшим текстовым полем внизу с указанием разрешающего столбца, разрешающей строки и другой информации, что делает программу обучающей. Во вкладке с оптимальной (последней) таблицей в текстовом поле приведено полученное оптимальное решение задачи.

Замеченные ошибки и комментарии по работе апплета присылайте на [email protected] или звоните 8 962 700 77 06, за что мы будем Вам очень благодарны.

Программа М-метод

Программа для решения транспортной задачи

Здесь приведено ручное (не апплетом) решение двух задач симплекс-методом (аналогичным решению апплетом) с подробными объяснениями для того, чтобы понять алгоритм решения задач. Первая задача содержит знаки неравенства только " ≤ " (задача с начальным базисом), вторая может содержить знаки " ≥ ", " ≤ " или " = " (задача с искусственным базисом), они решаются по разному.

Симплекс-метод, решение задачи с начальным базисом

1)Симплекс-метод для задачи с начальным базисом (все знаки неравенств-ограничений " ≤ ").

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

Эта система является системой с базисом (базис s 1 , s 2 , s 3 , каждая из них входит только в одно уравнение системы с коэффициентом 1), x 1 и x 2 - свободные переменные. Задачи, при решении которых применяется симплекс-метод, должны обладать следующими двумя свойствами:
-система ограничений должна быть системой уравнений с базисом;
-свободные члены всех уравнений в системе должны быть неотрицательны.

Полученная система - система с базисом и ее свободные члены неотрицательны, поэтому можно применить симплекс-метод. Составим первую симплекс-таблицу (Итерация 0), т.е. таблицу коэффициентов целевой функции и системы уравнений при соответствующих переменных. Здесь "БП" означает столбец базисных переменных, «Решение» - столбец правых частей уравнений системы. Решение не является оптимальным, т.к. в z – строке есть отрицательные коэффициенты.

итерация 0

БП

Решение Отношение

Для улучшения решения перейдем к следующей итерации, получим следующую симплекс-таблицу. Для этого надо выбрать разрешающий столбец , т.е. переменную, которая войдет в базис на следующей итерации. Он выбирается по наибольшему по модулю отрицательному коэффициенту в z-строке (в задаче на максимум) – в начальной итерации это столбец x 2 (коэффициент -6).

Затем выбирается разрешающая строка , т.е. переменная, которая выйдет из базиса на следующей итерации. Она выбирается по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца (столбец «Отношение») – в начальной итерации это строка s 3 (коэффициент 20).

Разрешающий элемент находится на пересечении разрешающего столбца и разрешающей строки, его ячейка выделена цветом, он равен 1. Следовательно, на следующей итерации переменная x 2 заменит в базисе s 3 . Заметим, что в z-строке отношение не ищется, там ставится прочерк " - ". В случае если есть одинаковые минимальные отношения, то выбирается любое из них. Если в разрешающем столбце все коэффициенты меньше или равны 0, то решение задачи бесконечно.

Заполним следующую таблицу «Итерация 1». Её мы получим из таблицы «Итерация 0». Цель дальнейших преобразований - превратить разрешающий столбец х 2 в единичный (с единицей вместо разрешающего элемента и нулями вместо остальных элементов).

1)Вычисление строки х 2 таблицы "Итерация 1". Сначала делим все члены разрешающей строки s 3 таблицы "Итерация 0" на разрешающий элемент (он равен 1 в данном случае) этой таблицы, получим строку x 2 в таблице «Итерации 1». Т.к. разрешающий элемент в данном случае равен 1, то строка s 3 таблицы "Итерация 0" будет совпадать со строкой х 2 таблицы "Итерация 1". Строку x 2 таблицы "Итерации 1" мы получили 0 1 0 0 1 20, остальные строки таблицы "Итерация 1" будут получены из этой строки и строк таблицы "Итерация 0" следующим образом:

2) Вычисление z-строки таблицы "Итерация 1". На месте -6 в первой строке (z-строке) в столбце х 2 таблицы "Итерация 0" должен быть 0 в первой строке таблицы "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на 6, получим 0 6 0 0 6 120 и сложим эту строку с первой строкой (z - строкой) таблицы "Итерация 0" -4 -6 0 0 0 0, получим -4 0 0 0 6 120. В столбце x 2 появился ноль 0 , цель достигнута. Элементы разрешающего столбца х 2 выделены красным цветом.

3) Вычисление строки s 1 таблицы "Итерация 1". На месте 1 в s 1 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -1, получим 0 -1 0 0 -1 -20 и сложим эту строку с s 1 - строкой таблицы "Итерация 0" 2 1 1 0 0 64, получим строку 2 0 1 0 -1 44. В столбце х 2 получен необходимый 0.

4) Вычисление строки s 2 таблицы "Итерация 1". На месте 3 в s 2 строке таблицы "Итерация 0" должен быть 0 в таблице "Итерация 1". Для этого все элементы строки х 2 таблицы "Итерация 1" 0 1 0 0 1 20 умножим на -3, получим 0 -3 0 0 -3 -60 и сложим эту строку с s 2 - строкой таблицы "Итерация 0" 1 3 0 1 0 72, получим строку 1 0 0 1 -3 12. В столбце х 2 получен нужный 0. Столбец х 2 в таблице "Итерация 1" стал единичным, он содержит одну 1 и остальные 0.

Строки таблицы «Итерация 1» получаем по следующему правилу:

Новая строка = Старая строка – (Коэффициент разрешающего столбца старой строки)*(Новая разрешающая строка).

Например для z -строки имеем:

Старая z-строка (-4 -6 0 0 0 0)
-(-6)*Новая разрешающая строка -(0
-6 0 0 -6 -120)
=Новая z-строка
(-4 0 0 0 6 120) .

Для следующих таблиц пересчет элементов таблицы делается аналогично, поэтому мы его опускаем.

итерация 1

Решение Отношение

Разрешающий столбец х 1 , разрешающая строка s 2 , s 2 выходит из базиса, х 1 входит в базис. Совершенно аналогично получим остальные симплекс-таблицы, пока не будет получена таблица со всеми положительными коэффициентами в z-строке. Это признак оптимальной таблицы.

Итерация 2

Решение Отношение

Разрешающий столбец s 3 , разрешающая строка s 1 , s 1 выходит из базиса, s 3 входит в базис.

Итерация 3

Решение Отношение

В z-строке все коэффициенты неотрицательны, следовательно, получено оптимальное решение x 1 = 24, x 2 = 16, z max = 192.

Симплекс-метод, решение задачи с искусственным базисом

2) Решим задачу с искусственным базисом (хотя бы один знак неравенств-ограничений " ≥ " или " = ").

Запишем задачу в канонической форме (в виде системы уравнений, что требует симплекс-метод), для этого введем две переменные х 3 ≥ 0 и х 4 ≥ 0 получим:

Система ограничений предлагает только одну допустимую базисную переменную x 4 , только она входит только в одно уравнение в третье с коэффициентом 1, поэтому в первое и второе уравнения добавляем искусственные переменные R 1 ≥ 0 и R 2 ≥ 0 Чтобы можно было примененить симплекс-метод система уравнений-ограничений должна быть системой с базисом, т.е. в каждом уравнении должна быть переменная с коэффициентом 1, которая входит только в одно уравнение системы, в нашем случае это R 1 , R 2 и x 4 . Получили, так называемую, М-задачу:

Данная система является системой с базисом, в которой R 1 , R 2 и x 4 базисные переменные, а x 1 , x 2 и x 3 свободные переменные, свободние члены всех уравнений неотрицательны. Следовательно, для решения задачи можно применить симплекс-метод. Запишем начальную симплекс-таблицу:

итерация 0

Решение Отношение
-16

В таблицу для задач с искусственным базисом добавлена строка «Оценка». Она получается суммированием соответствующих коэффициентов строк с искусственными переменными (R) с обратным знаком. Она будет присутствовать в таблице до тех пор, пока хотя бы одна из искусственных переменных есть в базисе. По наибольшему по модулю отрицательному коэффициенту строки "Оценка" определяется разрешающий столбец пока она есть в таблице. Когда строка "Оценка" выйдет из таблицы (в базисе нет искусственных переменных) разрешающий столбец будет определяться по z-строке, как и в задаче с начальным базисом. В данной таблице разрешающий столбец х 2 , он выбран по наибольшей по модулю отрицательной оценке (-7). Разрешающая строка R 2 выбрана по наименьшему отношению столбца "Решение" к соответствующим положительным элементам разрешающего столбца, как и в задаче без искусственных переменных. Это значит, что на следующей итерации переменная х 2 из свободной перейдет в базисную, а переменная R 2 из базисной – в свободную. Запишем следующую симплекс-таблицу:

Разрешающий столбец х 1 , разрешающая строка R 1 , R 1 выходит из базиса, x 1 входит в базис. После этого в базисе не остается искусственных переменных, поэтому строки «Оценка» в следующей таблице нет:

итерация 2

Решение Отношение

Далее разрешающий столбец выбирается по z-строке. В z-строке все коэффициенты неотрицательны кроме коэффициента при искусственной переменной R 1 , который не влияет на оптимальность, когда искусственные переменные вышли из базиса. Следовательно, получено оптимальное решение x 1 = 6/5; x 2 = 3/5; z max = 72/5.

Особые случаи применения симплекс-метода

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

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

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

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

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

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

Решение задач симплекс-методом: примеры онлайн

Задача 1. Компания производит полки для ванных комнат двух размеров — А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В — 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В — 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В — 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Составление математической модели и решение ЗЛП симплекс-методом (pdf, 33 Кб)

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

Решение симплекс-методом с искусственным базисом (pdf, 45 Кб)

Задача 3. Предприятие производит 3 вида продукции: А1, А2, А3, используя сырьё двух типов. Известны затраты сырья каждого типа на единицу продукции, запасы сырья на планируемый период, а также прибыль от единицы продукции каждого вида.

  1. Сколько изделий каждого вида необходимо произвести, чтобы получить максимум прибыли?
  2. Определить статус каждого вида сырья и его удельную ценность.
  3. Определить максимальный интервал изменения запасов каждого вида сырья, в пределах которого структура оптимального плана, т.е. номенклатура выпуска, не изменится.
  4. Определить количество выпускаемой продукции и прибыль от выпуска при увеличении запаса одного из дефицитных видов сырья до максимально возможной (в пределах данной номенклатуры выпуска) величины.
  5. Определить интервалы изменения прибыли от единицы продукции каждого вида, при которых полученный оптимальный план не изменится.

Решение задачи линейного программирования с экономическим анализом (pdf, 163 Кб)

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

Решение табличным симплекс-методом с поиском опорного плана (pdf, 44 Кб)

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

Решение табличным симплекс-методом (pdf, 47 Кб)

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

Решение ручным симплекс-методом (pdf, 60 Кб)

Задача 7. Решить задачу модифицированным симплекс-методом.
Для производства двух видов изделий А и Б используется три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется а1=4 часов, оборудование второго типа а2=8 часов, а оборудование третьего типа а3=9 часов. На производство единицы изделия Б оборудование первого типа используется б1=7 часов, оборудование второго типа б2=3 часов, а оборудование третьего типа б3=5 часов.
На изготовление этих изделий оборудование первого типа может работать не более чем t1=49 часов, оборудование второго типа не более чем t2=51 часов, оборудование третьего типа не более чем t3=45 часов.
Прибыль от реализации единицы готового изделия А составляет АЛЬФА=6 рублей, а изделия Б – БЕТТА=5 рублей.
Составить план производства изделий А и Б, обеспечивающий максимальную прибыль от их реализации.

Решение модифицированным симплекс-методом (pdf, 67 Кб)

Задача 8. Найти оптимальное решение двойственным симплекс-методом

Решение двойственным симплекс-методом (pdf, 43 Кб)

Примеры решений задач по линейному программированию

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

Опорные решения задачи линейного программирования

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

при условиях

Будем обозначать через множество решений системы (2) – (3). Предположим, что , где – ранг матрицы , – количество уравнений в системе (2).

Из системы векторов-столбцов матрицы выберем некоторую линейно независимую подсистему из векторов . Она существует, так как . Эта система образует базис в . Обозначим через , . Назовем множеством базисных значений индекса , – базиснойподматрицей матрицы . Координаты вектора будем называть базисными , если , и небазисными в противном случае.

Запишем систему (2) в виде . Разобьем слагаемые левой части на базисные и небазисные, то есть

Определим частное решение этой системы следующим образом. Положим в (4) все небазисные переменные равными нулю . Тогда система (4) примет вид

Назовем (5) базисной подсистемой системы уравнений (2). Обозначим через вектор, составленный из базисных координат вектора . Тогда систему (2) можно переписать в векторно-матричном виде

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

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

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

при условиях

Запишем систему (8) в виде

Напомним, что множество решений системы (8) обозначается через .

Определим вектор двойственных переменных из условия выполнения базисных ограничений в системе (9) как равенств. Получим следующую систему линейных уравнений:

Обозначим через вектор, составленный из ба-

зисных координат вектора . Тогда систему (10) можно переписать в векторно-матричном виде

Система (11) также имеет единственное решение .

Назовем его опорным (базисным ) решением двойственной задачи линейного программирования, соответствующим базису . Это опорное решение также определяется однозначно.

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

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

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

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

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

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

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

Поэтому достаточно убедиться в выполнении неравенств для всех .

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

Доказательство . Из определений опорных решений легко получить равенства

откуда и следует справедливость теоремы.

Теорема 2. (Критерий оптимальности опор-ных решений) Если базис одновременно допустим и двойственно допустим, то соответствующие ему опорные решения и являются решениями, соответственно, прямой и двойственной задач линейного программирования.

Доказательство. Справедливость этого утверждения следует из теории двойственности в линейном программировании и теоремы 1.

Теорема 3. Допустимое решение задачи (1) – (3) является опорным планом задачи тогда и только тогда, когда оно является вершиной выпуклого многогранного множества .

Доказательство. Пусть – опорный план задачи (1) – (3). Докажем, что – вершина множества . По определению опорный план допустимое опорное решение, соответствующее некоторому базису , то есть решениесистемы линейных уравнений относительно переменных

Легко увидеть, что эта система имеет единственное решение. Значит, несущая плоскость грани, содержащей точку , имеет размерность 0. Следовательно, – вершина множества .

Обратно. Пусть – вершина множества . Докажем, что – опорный план задачи (1) – (3). Так как – вершина, то она является гранью множества , размерность которой равна нулю. Следовательно, у вектора найдется не менее нулевых компонент, множество номеров которых обозначим . Таким образом, единственное решение системы

где . Поэтому осталось доказать, что система векторов линейно независима. Предположим противное. Тогда существуют числа не все равные нулю, такие что . Поэтому

Это означает, что система (12) имеет решение, отличное от , что противоречит единственности ее решения. Таким образом, – базис, а вектор – соответствующий ему опорный план задачи (1) – (3). Что и требовалось.

Заметим, что допустимое решение задачи (7), (8) (двойственной задаче (1) – (3)) также является опорным планом тогда и только тогда, когда оно является вершиной допустимого множества .

Дата публикования: 2015-01-10; Прочитано: 695 | Нарушение авторского права страницы

Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.005 с)…

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

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

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

Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены; в противном случае используем так называемый М – метод, который будет рассмотрен ниже.

2. Определить базисные и свободные переменные.

3. Исходную расширенную систему заносим в первую симплекс – таблицу. Последняя строка таблицы, в которой приведено уравнение для линейной функции цели, называется оценочной . В ней указываются коэффициенты функции цели . В левом столбце таблицы записываем основные переменные (базис), в последующих – коэффициенты при свободных переменных. В предпоследнем столбце – свободные члены расширенной системы . Последний столбец подготовлен для оценочных отношений, необходимых для определения базисной переменной на основании соотношения (6.29).

4. Определить возможность решения задачи по значениям согласно теоремам 6.7,…, 6.9.

5. Выбрать разрешающий (опорный) элемент .

Решение производственной задачи табличным симплекс-методом

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

Составляем оценочные отношения каждой строки по следующим правилам:

1 0) , если все и имеют разные знаки;

2 0) , если все и ;

3 0) , если ;

4 0) 0, если и ;

5 0) , если и имеют одинаковые знаки.

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

6 0) Переход к следующей таблице по правилам:

а) в левом столбце записываем новый базис: вместо основной переменной – переменную , т.е. поменяем местами переменные и ;

б) на место опорного элемента поставить 1;

в) на остальных местах опорной строки в новой таблице оставить элементы исходной таблицы;

г) на остальные места в опорном столбце поставить соответствующие элементы исходной таблицы, умноженные на –1;

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

Для упрощения вычислений по этим формулам их можно сформулировать в виде «правила прямоугольника» (рис. 6.8): элементы на диагоналях прямоугольника с вершинами (или , , , , или , , , ) перемножаются (произведение, не содержащее опорного элемента , берется со знаком минус) и полученные произведения складываются;

е) все полученные элементы новой таблицы разделить на опорный элемент .

7 0) По значению элемента определить, найдено ли оптимальное значение целевой функции. В случае отрицательного ответа продолжить решение (возврат к пункту 6).

Рис. 6.8. Правило прямоугольника для определения чисел:

а − , б − , в − .

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

Пример 6.8. Решить задачу, приведенную в примере 6.7, симплекс методом.

⇐ Предыдущая45678910111213Следующая ⇒

Дата публикования: 2015-01-23; Прочитано: 174 | Нарушение авторского права страницы

Studopedia.org — Студопедия.Орг — 2014-2018 год.(0.002 с)…

Главная >> Пример №3. Симплекс метод. Нахождение наибольшего значения функции (искусственный базис)

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

x 1 + x 2 1
x 1 + 3 x 2 15
2 x 1 + x 2 4
Переменная называется базисной для данного уравнения, если она входит в данное уравнение с коэффициентом один и не входит в оставшиеся уравнения (при условии, что в правой части уравнения стоит положительное число).

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

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

Как осуществляется переход от одного базиса к другому?
Запись решения удобнее вести в виде таблиц. Каждая строка эквивалентна уравнению системы. Выделенная строка состоит из коэффициентов функции (сравните сами). Это позволяет не переписывать переменные каждый раз, что существенно экономит время.
B выделенной строке выбираем наибольший положительный коэффициент. Это необходимо для того, чтобы получить значение функции, как минимум, не меньше имеющегося.
Выбран столбец.
Для положительных коэффициентов выбранного столбца считаем отношение Θ и выбираем наименьшее значение. Это необходимо для того, чтобы после преобразования столбец свободных членов остался положительным.
Выбрана строка.
Следовательно, определен элемент, который будет базисным. Далее считаем.

x 1 = 0 x 2 = 0 S 1 = 0
S 2 = 15 S 3 = 4 R 1 = 1
=> W = 1
x 1 x 2 S 1 S 2 S 3 R 1 св. член Θ
-1 1 -1 0 0 1 1 1: 1 = 1
1 3 0 1 0 0 15 15: 3 = 5
-2 1 0 0 1 0 4 4: 1 = 4
1 -1 1 0 0 0 W — 1
-1 1 -1 0 0 1 1
4 0 3 1 0 -3 12
-1 0 1 0 1 -1 3
0 0 0 0 0 1 W — 0
x 1 x 2 S 1 S 2 S 3 св. член Θ
-1 1 -1 0 0 1
4 0 3 1 0 12 12: 4 = 3
-1 0 1 0 1 3
4 0 1 0 0 F — 1
-1 1 -1 0 0 1
1 0 3/4 1/4 0 3
-1 0 1 0 1 3
4 0 1 0 0 F — 1
0 1 -1/4 1/4 0 4
1 0 3/4 1/4 0 3
0 0 7/4 1/4 1 6
0 0 -2 -1 0 F — 13
S 1 = 0 S 2 = 0
x 1 = 3 x 2 = 4 S 3 = 6
=> F — 13 = 0 => F = 13

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

Ответ:

x 1 = 3 x 2 = 4

F max = 13

Перейти к решению своей задачи

© 2010-2018, по всем вопросам пишите по адресу [email protected]

Условие задачи

Для реализации трех групп товаров коммерческое предприятие располагает тремя видами ограниченных материально-денежных ресурсов в количестве b 1 = 240, b 2 = 200, b 3 = 160 единиц. При этом для продажи 1 группы товаров на 1 тыс. руб. товарооборота расходуется ресурса первого вида в количестве a 11 = 2 единицы, ресурса второго вида в количестве a 21 = 4 единицы, ресурса третьего вида в количестве a 31 = 4 единицы. Для продажи 2 и 3 групп товаров на 1 тыс. руб. товарооборота расходуется соответственно ресурса первого вида в количестве a 12 = 3, a 13 = 6 единицы, ресурса второго вида в количестве a 22 = 2, a 23 = 4 единицы, ресурса третьего вида в количестве a 32 = 6, a 33 = 8 единиц. Прибыль от продажи трех групп товаров на 1 тыс.

Симплексный метод решения ЗЛП

руб. товарооборота составляет соответственно c 1 = 4, c 2 = 5, c 3 = 4 (тыс. руб.). Определить плановый объем и структуру товарооборота так, чтобы прибыль торгового предприятия была максимальной.

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

Решение задачи симплекс методом

Пусть x 1 , x 2 , x 3 — количество реализованных товаров, в тыс. руб., 1, 2, 3 — ей групп, соответственно. Тогда математическая модель задачи имеет вид:

F = 4·x 1 + 5·x 2 + 4·x 3 ->max

Решаем симплекс методом.

Вводим дополнительные переменные x 4 ≥ 0, x 5 ≥ 0, x 6 ≥ 0, чтобы неравенства преобразовать в равенства.

В качестве базиса возьмем x 4 = 240; x 5 = 200; x 6 = 160.

Данные заносим в симплекс таблицу

Симплекс таблица № 1

Целевая функция:

0 · 240 + 0 · 200 + 0 · 160 = 0

Вычисляем оценки по формуле:

Δ 1 = 0 · 2 + 0 · 4 + 0 · 4 - 4 = - 4
Δ 2 = 0 · 3 + 0 · 2 + 0 · 6 - 5 = - 5
Δ 3 = 0 · 6 + 0 · 4 + 0 · 8 - 4 = - 4
Δ 4 = 0 · 1 + 0 · 0 + 0 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 0 · 0 - 0 = 0
Δ 6 = 0 · 0 + 0 · 0 + 0 · 1 - 0 = 0

Поскольку есть отрицательные оценки, то план не оптимален. Наименьшая оценка:

Вводим переменную x 2 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 2 .

= 26.667

Наименьшее неотрицательное: Q 3 = 26.667. Выводим переменную x 6 из базиса

3-ю строку делим на 6.
Из 1-й строки вычитаем 3-ю строку, умноженную на 3
Из 2-й строки вычитаем 3-ю строку, умноженную на 2

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 2

Целевая функция:

0 · 160 + 0 · 440/3 + 5 · 80/3 = 400/3

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 8/3 + 5 · 2/3 - 4 = - 2/3
Δ 2 = 0 · 0 + 0 · 0 + 5 · 1 - 5 = 0
Δ 3 = 0 · 2 + 0 · 4/3 + 5 · 4/3 - 4 = 8/3
Δ 4 = 0 · 1 + 0 · 0 + 5 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 5 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1)/3 + 5 · 1/6 - 0 = 5/6

Поскольку есть отрицательная оценка Δ 1 = - 2/3, то план не оптимален.

Вводим переменную x 1 в базис.

Определяем переменную, выходящую из базиса. Для этого находим наименьшее неотрицательное отношение для столбца x 1 .

Наименьшее неотрицательное: Q 3 = 40. Выводим переменную x 2 из базиса

3-ю строку делим на 2/3.
Из 2-й строки вычитаем 3-ю строку, умноженную на 8/3

Вычисляем:

Получаем новую таблицу:

Симплекс таблица № 3

Целевая функция:

0 · 160 + 0 · 40 + 4 · 40 = 160

Вычисляем оценки по формуле:

Δ 1 = 0 · 0 + 0 · 0 + 4 · 1 - 4 = 0
Δ 2 = 0 · 0 + 0 · (-4) + 4 · 3/2 - 5 = 1
Δ 3 = 0 · 2 + 0 · (-4) + 4 · 2 - 4 = 4
Δ 4 = 0 · 1 + 0 · 0 + 4 · 0 - 0 = 0
Δ 5 = 0 · 0 + 0 · 1 + 4 · 0 - 0 = 0
Δ 6 = 0 · (-1)/2 + 0 · (-1) + 4 · 1/4 - 0 = 1

Поскольку отрицательных оценок нет, то план оптимален.

Решение задачи:

Ответ

x 1 = 40; x 2 = 0; x 3 = 0; x 4 = 160; x 5 = 40; x 6 = 0; F max = 160

То есть необходимо реализовать товар первого вида в объеме 40 тыс.

руб. Товар 2-го и 3-го видов реализовывать не надо. При этом максимальная прибыль составит F max = 160 тыс. руб.

Решение двойственной задачи

Двойственная задача имеет вид:

Z = 240·y 1 + 200·y 2 + 160·y 3 ->min

Вводим дополнительные переменные y 4 ≥ 0, y 5 ≥ 0, y 6 ≥ 0, чтобы неравенства преобразовать в равенства.

Сопряженные пары переменных прямой и двойственной задач имеют вид:

Из последней симплекс таблицы № 3 прямой задачи, находим решение двойственной задачи:

Z min = F max = 160;
y 1 = Δ 4 = 0; y 2 = Δ 5 = 0; y 3 = Δ 6 = 1; y 4 = Δ 1 = 0; y 5 = Δ 2 = 1; y 6 = Δ 3 = 4;

Ответ

y 1 = 0; y 2 = 0; y 3 = 1; Z min = 160;

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

Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной симплекса, приходят к искомому оптимуму. На этом принципе основан симплекс-метод.

Симплекс – это выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).

Например, линия бюджетных ограничений делит блага на доступные и недоступные.

Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число итераций (шагов), кроме случаев «зацикливания».

Алгоритм симплексного метода состоит из ряда этапов.

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

а) правые части условий (свободные члены bi) являются величинами неотрицательными;

б) сами условия являются равенствами;

в) матрица условий содержит полную единичную подматрицу.

Если свободные члены отрицательные, то обе части неравенства умножаются на — 1, а знак неравенства меняется на противоположный. Для преобразования неравенств в равенства вводятся дополнительные переменные, которые, обычно, обозначают объем недоиспользованных ресурсов. В этом их экономический смысл.

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

В оптимальном решении задачи все искусственные переменные (ИП) должны быть равными нулю. Для этого вводят искусственные переменные в целевую функцию задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение искусственной переменной будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.

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

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

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

Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом.

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

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

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

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

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

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

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

Пусть необходимо найти оптимальный план производства двух видов продукции (х1 и х2).

Исходные данные:

Построим оптимизационную модель

– ограничение по ресурсу А;

– ограничение по ресурсу В.

Приведем задачу к приведенной канонической форме. Для этого достаточно ввести дополнительные переменные Х3 и Х4. В результате неравенства преобразуются в строгие равенства.

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

1-я итерация. Находим генеральный столбец и генеральную строку:

Генеральный элемент равняется 5.

2-я итерация. Найденное базисное решение не является оптимальным, т.к. cтрока оценок (Fj-Cj) содержит один положительный элемент. Находим генеральный столбец и генеральную строку:

max (0,0.3,-1.4,0) = 0.2

Найденное решение оптимально, так как все специальные оценки целевой функции Fj – Cj равны нулю или отрицательны. F(x)=29 x1=2; x2=5.

Загрузка...