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

Август 6, 2022

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

Содержание

2. Вычислительные методы решения задач линейного программирования. Сущность симплекс – метода. Примеры решения с использованием симплекс-метода. Учебные
3. Вычислительные методы решения задач линейного программирования Учебный вопрос № 1
4. Геометрическая интерпретация, при решении задач линейного программирования, перестает быть пригодной для этой цели при числе свободных
5. Симплекс-метод — алгоритм решения оптимизационной задачи (ОЗ) линейного программирования путём перебора вершин выпуклого многогранника в многомерном
6. Сущность симплекс-метода Учебный вопрос № 2
7. Идея симплекс-метода относительно проста. Пусть в задаче линейного программирования имеется n переменных и m независимых линейных
8. Предположим, что все свободные переменные х1, х2, …, хk равны нулю. При этом получим: хk+1 =
9. Очевидно, что при х1 = х2 = … = хk =0, F = γ0. Проверим, может
10. Пусть, например, коэффициент γi в (2) отрицателен. Значит, есть смысл увеличить х1, т. е. перейти от
11. Допустим, что это не так и что среди уравнений (1) есть такие, в которых коэффициент при
12. Если оставить х2 = х3 = … = хk =0, то х1 можно увеличивать только до
13. Первое опорное решение получим, положив равными нулю все прежние свободные переменные х1 , х2 , …
14. Предположим, что уравнения типа (1) для нового набора базисных и свободных переменных составлены. Тогда можно выразить
15. Примеры решения с использованием симплекс-метода Учебный вопрос № 3
16. Пример. Пусть имеется задача линейного программирования с ограничениями-неравенствами: – 5х1 – х2 + 2х3 ≤ 2;
17. Приводя неравенства к стандартному виду (≥ 0) и вводя добавочные переменные у1, у2, у3, переходим к
18. Пусть в качестве свободных переменных выступают х1, х2, х3, х4. Положим их равными нулю и получим
19. Определим, какая из этих переменных (у1 или у2) раньше обратится в нуль при увеличении х3. Очевидно,
20. Это выражение подставляется вместо х3 во второе уравнение: (5) Пример (продолжение)
21. Что касается третьего уравнения, то оно, как не содержащее х3 не изменится. Система (4) приведена к
22. Это решение все еще не оптимально, так как коэффициент при х2 в выражении (6) отрицателен, и
23. Выразим F через новые свободные переменные: F = 3х1 + 2у2 – у1 + 2х4 –
24. В рассмотренном примере не пришлось искать опорное решение: оно сразу же получилось, когда положили свободные переменные
25. ЗАДАНИЕ. Компания производит полки для ванных комнат двух размеров – А и В. Агенты по продаже
26. РЕШЕНИЕ. Составим математическую модель задачи. Пусть х1 – количество полок вида А, х2 – количество полок
27. Таким образом, приходим к задаче линейного программирования. Решим ее симплекс-методом. Введем три дополнительные переменные x3, x4,
28. В качестве опорного плана выберем X0=(0,0,550,1200,9600). Составим симплекс-таблицу. В последней оценочной строке есть отрицательные оценки, поэтому
29. Пример
30. В последнем плане строка f не содержит отрицательных значений, план x1 = 450, x2 = 100
31. ЗАДАНИЕ. Решить задачу линейного программирования симплекс-методом. РЕШЕНИЕ. Будем решать эквивалентную задачу Пример
32. Введем дополнительные переменные, чтобы привести задачу к каноническому виду: Так как нет единичных векторов, вводим искусственный
33. Получили расширенную задачу с опорным планом (0,0,0,0,0,0,8,2,1). Составим cимплекс-таблицу: В последней оценочной строке есть отрицательные оценки
34. Пример
35. Искусственный базис выведен, но в единственном столбце с отрицательной оценкой (Х2) все коэффициенты отрицательны, то есть
37. Скачать презентацию

Слайд 2

Вычислительные методы решения задач линейного программирования.
Сущность симплекс – метода.
Примеры решения с

использованием симплекс-метода.

Учебные вопросы:

Слайд 3

Вычислительные методы решения задач линейного программирования
Учебный вопрос № 1

Слайд 4

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

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

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

Слайд 5

Симплекс-метод — алгоритм решения оптимизационной задачи (ОЗ) линейного программирования путём перебора

вершин выпуклого многогранника в многомерном пространстве. Метод был разработан американским математиком Джорджем Данцигом (George Dantzig) в 1947 году.
Википедия

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

Слайд 6

Сущность симплекс-метода
Учебный вопрос № 2

Слайд 7

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

переменных и m независимых линейных ограничений, заданных в форме уравнений. Известно, что оптимальное решение (если оно существует) достигается в одной из опорных точек (вершин ОДР), где по крайней мере k = n - m из переменных равны нулю. Выберем какие-то k переменных в качестве свободных и выразим через них остальные m базисных переменных. Пусть, например, в качестве свободных выбраны первые k = n - m переменных х1, х2, …, хk, а остальные m выражены через них:
хk+1 = α k+1,1 х1 + α k+1,2 х2 + … + α k+1,k хk + β k+1;
хk+2 = α k+2,1 х1 + α k+2,2 х2 + … + α k+2,k хk + β k+2; (1)
…
хn= α n1 х1 + α n2 х2 + … + α nk хk + β n.

Сущность симплекс-метода

Слайд 8

Предположим, что все свободные переменные
х1, х2, …, хk равны нулю.
При

этом получим:
хk+1 = β k+1;
хk+2 = β k+2;
…
хn= β n.
Это решение может быть допустимым или недопустимым. Оно допустимо, если все свободные члены β k+1, β k+2, … , β n неотрицательны. Предположим, что это условие выполнено. Тогда мы получили опорное решение. Но является ли оно оптимальным? Чтобы проверить это, выразим целевую функцию F через свободные переменные х1, х2, …, хk :
F = γ0 + γ1х1 + γ2х2 + … + γk хk . (2)

Сущность симплекс-метода

Слайд 9

Очевидно, что при х1 = х2 = … = хk =0,

F = γ0. Проверим, может ли быть улучшено решение, т. е. получено уменьшение функции F c увеличением каких-нибудь из переменных х1, х2, …, хk (уменьшать их мы не можем, так как все они равны нулю, а отрицательные значения переменных недопустимы). Если все коэффициенты γ1, γ2, … , γk в (2) положительны, то увеличение каких-либо из переменных х1, х2, …, хk не может уменьшить F; следовательно, найденное опорное решение является оптимальным. Если же среди коэффициентов γ1, γ2, … , γk есть отрицательные, то, увеличивая некоторые из переменных х1, х2, …, хk (те, коэффициенты при которых отрицательны), можно улучшить решение.

Сущность симплекс-метода

Слайд 10

Пусть, например, коэффициент γi в (2) отрицателен. Значит, есть смысл увеличить

х1, т. е. перейти от данного опорного решения к другому, где переменная х1 не равна нулю, а вместо нее равна нулю какая-то другая. Однако увеличивать х1 следует с осторожностью, так чтобы не стали отрицательными другие переменные хk+1, хk+2, … , хn выраженные через свободные переменные, в частности через х1 формулами (1).
Например, если коэффициент при х1 в соответствующем хi уравнении (1) отрицателен, то увеличение х1 может сделать хi отрицательным. Наоборот, если среди уравнений (1) нет уравнения с отрицательным коэффициентом при х1 то величину х1 можно увеличивать беспредельно, а, значит, линейная функция F не ограничена снизу и оптимального решения ОЗ не существует.

Сущность симплекс-метода

Слайд 11

Допустим, что это не так и что среди уравнений (1) есть

такие, в которых коэффициент при х1 отрицателен. Для переменных, стоящих в левых частях этих уравнений, увеличение х1 опасно — оно может сделать их отрицательными.
Возьмем одну из таких переменных х1 и посмотрим, до какой степени можно увеличить х1, пока переменная хi не станет отрицательной. Выпишем i-е уравнение из системы (1):
хi = αi 1 х1 + α i 2 х2 + … + α i k хk + β i
Здесь свободный член β i ≥ 0, а коэффициент αik отрицателен.

Сущность симплекс-метода

Слайд 12

Если оставить х2 = х3 = … = хk =0, то

х1 можно увеличивать только до значения, равного (– βi / α1i), а при дальнейшем увеличении х1 переменная хi станет отрицательной.
Выберем ту из переменных хk+1, хk+2, … , хn, которая раньше всех обратится в нуль при увеличении х1 т. е. ту, для которой величина (– βi / α1i) наименьшая. Пусть это будет хr . Тогда имеет смысл разрешить систему уравнений (1) относительно других базисных переменных, исключая из числа свободных переменных х1 и переводя вместо нее в группу свободных переменных хr . Перейдём от опорного решения, задаваемого равенствами х1 = х2 = … = хk = 0, к опорному решению, в котором уже х1 ≠ 0, а х2 = … = хk = хr = 0.

Сущность симплекс-метода

Слайд 13

Первое опорное решение получим, положив равными нулю все прежние свободные переменные

х1 , х2 , … , хk второе ‒ если обратим в нуль все новые свободные переменные
Базисными переменными при этом будут
х1 , хk+1 , хk+2 , … , хr‒1 , хr , хr+1 , … , хn

Сущность симплекс-метода

Слайд 14

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

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

Сущность симплекс-метода

Слайд 15

Примеры решения с использованием симплекс-метода
Учебный вопрос № 3

Слайд 16

Пример. Пусть имеется задача линейного программирования с ограничениями-неравенствами:
– 5х1 – х2

+ 2х3 ≤ 2;
– х1 + х3 + х4 ≤ 5; (3)
– 3х1 + 5 х4 ≤ 7.
Требуется минимизировать линейную функцию
F = 5х1 – 2х3

Пример

Слайд 17

Приводя неравенства к стандартному виду (≥ 0) и вводя добавочные переменные

у1, у2, у3, переходим к условиям-равенствам:
у1 = 5х1 + х2 – 2х3 + 2;
у2 = х1 – х3 – х4 + 5; (4)
у3 = 3х1 – 5 х4 + 7.
Число переменных (n = 7) на 4 превышает число уравнений (m = 3). Значит, четыре переменные могут быть выбраны в качестве свободных.

Пример (продолжение)

Слайд 18

Пусть в качестве свободных переменных выступают х1, х2, х3, х4. Положим

их равными нулю и получим опорное решение:
х1 = х2 = х3 = х4 = 0;
у1 = 2, у2 = 5, у3 = 7.
При этих значениях переменных F = 0.
Это решение не оптимально, поскольку в линейной функции F коэффициент при х3 отрицателен. Значит, увеличивая х3, можно уменьшить F.
Попробуем увеличивать х3 . Из выражений (4) видно, что в у1 и у2 переменная входит с отрицательным коэффициентом, значит, при увеличении х3 соответствующие переменные могут стать отрицательными.

Пример (продолжение)

Слайд 19

Определим, какая из этих переменных (у1 или у2) раньше обратится в

нуль при увеличении х3. Очевидно, что это у1: она станет равной нулю при х3 = 1, а величина у2 — только при х3= 5.
Выбирается переменная у, и вводится в число свободных вместо х3. Чтобы разрешить систему (4) относительно х3, у2, у3 необходимо:
Разрешить первое уравнение (4) относительно новой базисной переменной х3:

Пример (продолжение)

Слайд 20

Это выражение подставляется вместо х3 во второе уравнение:
(5)
Пример (продолжение)

Слайд 21

Что касается третьего уравнения, то оно, как не содержащее х3 не

изменится. Система (4) приведена к виду со свободными переменными х1, х2, у1, х4 и базисными х3, у2, у3.
Выразим функцию F через новые свободные переменные:
F = 5х1 – 5х1 – х2 + у1 – 2 = – х2 + у1 – 2 (6)
Положим теперь свободные переменные равными нулю. Функция приобретает значение F = – 2, что меньше (лучше), чем прежнее значение F = 0.

Пример (продолжение)

Слайд 22

Это решение все еще не оптимально, так как коэффициент при х2

в выражении (6) отрицателен, и переменная х2 может быть увеличена. Это увеличение, как это видно из системы (5), может сделать отрицательной у2 (в первое уравнение х2 входит с положительным коэффициентом, а в третьем — отсутствует).
Поменяем местами переменные х2 и у2 — первую исключим из числа свободных, а вторую — включим. Для этого разрешим второе уравнение (5) относительно х2 и подставим х2 в первое уравнение. Получим следующий вид системы (4):
(7)

Пример (продолжение)

Слайд 23

Выразим F через новые свободные переменные:
F = 3х1 + 2у2 –

у1 + 2х4 – 8 + у1 – 2 = 3х1 + 2у2 + 2х4 – 10 (8)
Полагая , что 3х1 + 2у2 + 2х4 = 0, получим F = – 10.
Это решение является оптимальным, так как коэффициенты при всех свободных переменных в выражении (8) неотрицательны. Итак, оптимальное решение ОЗ найдено:
При таких значениях переменных линейная функция F принимает минимальное значение:
Fmin= – 10.

Пример (продолжение)

Слайд 24

В рассмотренном примере не пришлось искать опорное решение: оно сразу же

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

Пример (продолжение)

Слайд 25

ЗАДАНИЕ. Компания производит полки для ванных комнат двух размеров – А

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

Пример

Слайд 26

РЕШЕНИЕ. Составим математическую модель задачи. Пусть х1 – количество полок вида

А, х2 – количество полок вида В, которые производятся в неделю (по смыслу задачи эти переменные неотрицательны). Прибыль от продажи такого количества полок составит 3х1 + 4х2, прибыль требуется максимизировать.
Выпишем ограничения задачи.
х1 + х2 ≤ 550 – в неделю на рынке может быть реализовано до 550 полок.
Затраты материала: 2х1 + 3х2 ≤ 1200
Затраты машинного времени: 12х1 + 30х2 ≤ 9600.

Пример

Слайд 27

Таким образом, приходим к задаче линейного программирования.
Решим ее симплекс-методом. Введем три

дополнительные переменные x3, x4, x5 и придем к задаче

Пример

Слайд 28

В качестве опорного плана выберем X0=(0,0,550,1200,9600). Составим симплекс-таблицу.
В последней оценочной строке

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

Пример

Слайд 29

Пример

Слайд 30

В последнем плане строка f не содержит отрицательных значений, план x1

= 450, x2 = 100 оптимален, целевая функция принимает значение 1750. Таким образом, чтобы получить максимальную прибыль, предприятию необходимо производить 450 полок вида А и 100 полок вида В, при этом прибыль составит 1750 ден. ед., а останется неиспользованными 1200 минут (20 часов) машинного времени.

Пример

Слайд 31

ЗАДАНИЕ. Решить задачу линейного программирования симплекс-методом.
РЕШЕНИЕ. Будем решать эквивалентную задачу
Пример

Слайд 32

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

единичных векторов, вводим искусственный базис:

Пример

Слайд 33

Получили расширенную задачу с опорным планом (0,0,0,0,0,0,8,2,1). Составим cимплекс-таблицу:
В последней оценочной

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

Пример

Слайд 34

Пример

Слайд 35

Искусственный базис выведен, но в единственном столбце с отрицательной оценкой (Х2)

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

Пример

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

Содержание

Вычислительные методы решения задач линейного программирования.Сущность симплекс – метода.Примеры решения с

Вычислительные методы решения задач линейного программированияУчебный вопрос № 1

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

Симплекс-метод — алгоритм решения оптимизационной задачи (ОЗ) линейного программирования путём перебора

Сущность симплекс-методаУчебный вопрос № 2

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

Предположим, что все свободные переменные х1, х2, …, хk равны нулю.При

Очевидно, что при х1 = х2 = … = хk =0,

Пусть, например, коэффициент γi в (2) отрицателен. Значит, есть смысл увеличить

Допустим, что это не так и что среди уравнений (1) есть

Если оставить х2 = х3 = … = хk =0, то

Первое опорное решение получим, положив равными нулю все прежние свободные переменные

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

Примеры решения с использованием симплекс-методаУчебный вопрос № 3

Пример. Пусть имеется задача линейного программирования с ограничениями-неравенствами:– 5х1 – х2

Приводя неравенства к стандартному виду (≥ 0) и вводя добавочные переменные

Пусть в качестве свободных переменных выступают х1, х2, х3, х4. Положим

Определим, какая из этих переменных (у1 или у2) раньше обратится в

Это выражение подставляется вместо х3 во второе уравнение:(5)Пример (продолжение)

Что касается третьего уравнения, то оно, как не содержащее х3 не

Это решение все еще не оптимально, так как коэффициент при х2

Выразим F через новые свободные переменные:F = 3х1 + 2у2 –

В рассмотренном примере не пришлось искать опорное решение: оно сразу же

ЗАДАНИЕ. Компания производит полки для ванных комнат двух размеров – А

РЕШЕНИЕ. Составим математическую модель задачи. Пусть х1 – количество полок вида

Таким образом, приходим к задаче линейного программирования.Решим ее симплекс-методом. Введем три

В качестве опорного плана выберем X0=(0,0,550,1200,9600). Составим симплекс-таблицу.В последней оценочной строке

Пример

В последнем плане строка f не содержит отрицательных значений, план x1

ЗАДАНИЕ. Решить задачу линейного программирования симплекс-методом.РЕШЕНИЕ. Будем решать эквивалентную задачуПример

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

Получили расширенную задачу с опорным планом (0,0,0,0,0,0,8,2,1). Составим cимплекс-таблицу:В последней оценочной

Пример

Искусственный базис выведен, но в единственном столбце с отрицательной оценкой (Х2)

Похожие презентации

Вычислительные методы решения задач линейного программирования.
Сущность симплекс – метода.
Примеры решения с

Вычислительные методы решения задач линейного программирования
Учебный вопрос № 1

Сущность симплекс-метода
Учебный вопрос № 2

Предположим, что все свободные переменные
х1, х2, …, хk равны нулю.
При

Примеры решения с использованием симплекс-метода
Учебный вопрос № 3

Пример. Пусть имеется задача линейного программирования с ограничениями-неравенствами:
– 5х1 – х2

Это выражение подставляется вместо х3 во второе уравнение:
(5)
Пример (продолжение)

Выразим F через новые свободные переменные:
F = 3х1 + 2у2 –

Таким образом, приходим к задаче линейного программирования.
Решим ее симплекс-методом. Введем три

В качестве опорного плана выберем X0=(0,0,550,1200,9600). Составим симплекс-таблицу.
В последней оценочной строке

ЗАДАНИЕ. Решить задачу линейного программирования симплекс-методом.
РЕШЕНИЕ. Будем решать эквивалентную задачу
Пример

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

Получили расширенную задачу с опорным планом (0,0,0,0,0,0,8,2,1). Составим cимплекс-таблицу:
В последней оценочной