Занятие 3. Тема Решение ЗЛП симплекс-методом.
Вид занятия: лекция
Тип занятия: усвоения новых знаний
Цель:
· Закрепление основных понятий о ЗЛП,
· Повторение моделей ЗЛП,
· Повторение алгоритма перехода от одной формы ЗЛП к другой;
· Повторение алгоритма графического метода решения ЗЛП;
· Изучение идеи симплекс-метода;
· Изучение алгоритма симплекс-метода;
· формирование навыков самостоятельной работы по заданному алгоритму решения ЗЛП симплекс-методом;
· формирование умений самостоятельно пополнять знания, пользоваться учебной литературой и др. источниками.
В результате изучения темы студент должен знать:
ü Постановку ЗЛП, модели ЗЛП,
ü алгоритм перехода от одной формы ЗЛП к другой,
ü алгоритм графического метода решения ЗЛП;
ü алгоритм симплекс-метода.
В результате изучения темы студент должен уметь:
ü По заданному алгоритму осуществлять переход от одной формы ЗЛП к другой,
ü используя алгоритм симплекс-метода решения ЗЛП, по заданному образцу решать ЗЛП симплекс- методом.
Литературные источники:
1. Богомолов Н.В. Практические занятия по математике. - М.: Дрофа - 2010.- 400 с.
2. Богомолов Н.В., Сергиенко Л.Ю. Сборник дидактических заданий по математике. - М.-Дрофа-2009.
3. Григорьев С.Г. Математика: учебник для студентов сред. проф. учреждений / С.Г. Григорьев, С.В. Задулина; под ред. В.А. Гусева. - 2-е изд., стер. - М.: Издательский центр «Академия», 2007. - 384 с.
4. Кремер Н.Ш. Теория вероятностей и математическая статистика: Учебник для вузов. - 4-е изд., перераб. и доп. - М.: ЮНИТИ-ДАНА, 2010. - 573 с.
5. Спирина М.С. Теория вероятностей и математическая статистика: учебник для студ. учреждений сред. проф. образования / М.С. Спирина, П.А. Спирин. - М.: Издательский центр «Академия», 2007. - 352 с.
6. Спирина М.С. Дискретная математика: учебник для студ. учреждений сред. проф. образования / М.С. Спирина, П.А. Спирин. - М.: Издательский центр «Академия», 2010. - 368 с.
7. П.Е. Данко, А.Г. Попов, Т.Я. Кожевникова Высшая математика в упражнениях и задачах. Часть 1 и 2. - М.: Высшая школа, 2008.
8. Н.В. Богомолов Задачи по математике с решениями. - М.: Высшая школа, 2006
9. Н.В. Богомолов, П.И. Самойленко Математика. - М.: Дрофа, 2004
10. З.И. Гурова, С.Н. Каролинская, А.П. Осипова Математический анализ. Начальный курс с примерами и задачами- М.: ФИЗМАТЛИТ, 2002
11. И.Д. Пехлецкий Математика. - М.: Мастерство, 2001
12. В.Ф. Бутузов, Н.И. Крутицкая. Математичесий анализ в вопросах и задачах. - М.: Физматлит, 2000
1. Изучение нового материала.
Идея симплекс-метода.
Симплекс-метод применяется для решения любых задач линейного программирования. Это универсальный, точный метод. Он принадлежит к категории методов последовательного улучшения плана.
- ОДЗ ЗЛП – выпуклое множество.
- Целевая функция принимает свое оптимальное значение в одной из целевых точек
Идея симплекс-метода в том, что он дает способ целенаправленного перебора части угловых точек (метод последовательного улучшения опорного плана).
| Последовательное улучшение плана идет по точкам А1, А2, А3, А4, А5 А6, А7 не будут исследоваться z (A1), z (A2), z (A3), z (A4), z (A5) |
Идея симплекс-метода базируется на предположениях:
1) указывается способ построения начального опорного плана.
2) указывается критерий, с помощью которого оценивается проверяемый опорный план на оптимальность
3) если опорный план не оптимален, указывается способ перехода к новому опорному плану, более близкому к оптимальному.
Алгоритм симплекс-метода
1) проверяется каноническая форма
2) выделяется начальный опорный план и значение целевой функции для него
3) строится симплекс-таблица
4) проверяется значения оценок оптимальности в индексной строке. Если нет положительных оценок, то получим оптимальное решение
5) в базис вводится вектор, которому соответствует наибольшая положительная оценка. Этот столбец называется разрешающим
6) из базиса выводится вектор, которому соответствует симплексное отношение
Строка называется разрешающей
7) Строим новую симплекс-таблицу
2. Закрепление изученного материала.
Пример № 1. Решить ЗЛП симплекс-методом z = 2x1 – x2 + 3x3 – 2x4 → max
хj ≥ 0, j = 
Решение.
z′ = – z = – 2х1 + х2 – 3х3 + 2х4 + 0·х5 → min
хj ≥ 0, j = 
Р1 = 
Р2 = 
Р3 = 
Р4 = 
Р5 = 
| Б | СБ | АБ | 
| 
| 
| 
| 
| исходный опорный план
 = (0, 0, 1, 1, 2)
z' ( ) = – 1
| |
| – 2 | –3 | ||||||||
| – 3 | – 1 | |||||||
| |||||||||
| – 1 | → разрешающая строка | |||||||
| z'j – cj | – 1 | – 6 | индексная (оценочная) строка | ||||||
| ↑ | |||||||||
| разрешающий столбец | |||||||||
Вместо 
вводим в базис 
Симплексное отношение Q = min 
= 1
Таблица 2
| Б | СБ | АБ | 
| 
| 
| 
| 
| |
| – 2 | –3 | |||||||
| – 3 | |||||||
| – 1 | → разрешающая строка | ||||||
|
| – 2 | – 1 | ||||||
| z'j – cj | – 8 | – 7 | ||||||
| ↑ | ||||||||
| разрешающий столбец |
Вместо 
вводим в базис 
Симплексное отношение Q = min 
= 
Таблица 3
| Б | СБ | АБ | 
| 
| 
| 
| 
|
| – 2 | –3 | ||||||
| – 3 | ||||||
| 
| – 
| 
| ||||
| – 2 | 
| 
|
| |||
| z'j – cj | – 
| – 
| – 
| ||||
| ↑ оптимальное значение целевой функции |
Оптимальный план
х1 = 
, х2 = 
, х3 = 2, х4 = 0, х5 = 0.
Задача была преобразована, значит,
хopt =( 
; 
; 2; 0)
zmax = 
Пример № 2. Решить задачу симплекс-методом:
Найти max Z = – 2х1 + х2 при 
Решение.
I этап
а) если среди свободных членов в системе ограничения есть отличные, то соответствующие ограничения умножить на (– 1). В нашем случае это правило относится к III ограничению.
если в ограничении есть неравенство, тогда вводят дополнительные переменные, превращающие их в уравнения
Мы имеем канонический вид задачи:
min (– Z) = 2х1 – х2
б) в ограничениях, где дополнительные переменные вычитаются, прибавляют искусственные переменные с последовательными номерами х6, х7, их также прибавляют в целевую функцию:
,
где х1, х2 – главные переменные;
х3, х4, х5 – дополнительные переменные;
х6, х7 – искусственные переменные.
min (– Z) = 2х1 – х2 = Мх6 + Мх7
в) запишем векторы и коэффициенты при неизвестных и вектор свободных членов.
Р1 = 
Р2 = 
Р3 = 
Р4 = 
Р5 = 
Р6 = 
Р7 = 
Р8 = 
г) строим первую симплекс-таблицу:
| Базис | С | Р0 | 2 | – 1 | 0 | 0 | 0 | М | М | СВ |
| Р1 | Р2 | Р3 | Р4 | Р5 | Р6 | Р7 | ||||
| Р6 | М | – 1 | ||||||||
| Р7 | М | – 1 | ||||||||
| Р5 | О | – 1 | – | |||||||
| Z – строка | – 2 | |||||||||
| M - строка | – 1 | – 1 |
Заполним таблицу:
1. Заносим все векторы (Рі).
2. в самой верхней строке записываем коэффициенты целевой функции при неизвестных.
3. Первичным базисом берем единичные векторы, образующие единичную матрицу, в данном случае Р6, Р7, Р5.
4. В столбец С переносят из верхней строки числа базисных векторов.
5. Для того, чтобы получить элементы последних двух строк, вектор С умножают последовательно на векторы Р0, … Р7 и от произведения вычитают числа из верхней строки.
| СР0 – О = 4М + 5М +3О = 9М | СР1 = М + 5М + (– 1)О – 2 = 6М – 2 |
| СР2 + 1 = 2М + М + 1О – (– 1) = 3М + 1 | СР3 – О = – М – О = – М и т.п. |
В М строку записывают коэффициенты при М, а в строку Z – коэффициенты без М.
ІІ этап. Проверка оптимальности решения.
а) Критерий оптимальности. Функция достигает минимума, когда среди элементов М -строки (а потом Z -строки, начиная со ІІ-ой), нет положительных чисел. В противном случае нужно оптимизировать решение. Согласно таблице 1 решение не является оптимальным.
б) Тогда находим ключевой столбец – по наибольшему положительному числу в М-строке (а потом Z -строки, начиная со ІІ-го. Ключевой столбец показывает, какой вектор войдет в новый базис) у нас наибольшее М = 6, в новый базис вводим вектор Р1.
в) Находим симплексное отношение, для чего элементы Р0: отрицательные элементы ключевого столбца (на положительные и нули не разделяются). Ключевой столбец берется по min СВ = 1. Ключевая строка вторая, базис покидает вектор Р7.
г) Элемент, стоящий на пересечении ключевой строки и ключевого столбца, называется генеральным. В таблице 1 = 5 он обозначен.
III этап. Построение нового решения. (таблица 2)
а) Формирование нового базиса изменяя один вектор. В данном случае новый базис из векторов Р6, Р1 и Р7. Так как Р7 – искусственный вектор, то выбрасывают и М -строку.
б) Столбец С заполняют по правилу, указанному ранее – верхней строки.
в) Вычисления ведут таким образом:
1. Элементы ключевой строки делят на генеральный элемент и записывают в новую таблицу;
2. Ключевой столбец заполняют нулями;
3. Если в ключевой строке есть нули, то их столбцы переносятся без изменений.
4. Последние элементы находят по правилу прямоугольника. Для его построения в предыдущей таблице старый элемент соединяют с ключевой строкой и ключевым столбцом, а потом по строке и столбцу ведут до генерального элемента.
Таблица 2
| Базис | С | Р0 | 2 | – 1 | 0 | 0 | 0 | М | СВ |
| Р1 | Р2 | Р3 | Р4 | Р5 | Р6 | ||||
| Р6 | М | 
| – 1 | 
| 
| ||||
| Р7 | 2 |
| 
| ||||||
| Р5 | 0 | 
| 
| 
| |||||
| Z – строка | 1 
| –
| |||||||
| M - строка |
| – 1 |
|
3М + 2 – 0 = 3М + 2 
+ 
– (– 1) = + 
и т.д.
Проверка показала, что в таблице 2 условия оптимальности не выполняются.
Снова ключевой столбец Р2. Находим симплексные отношения:
СВ1 = 3: 
= 
, СВ2 = 1: 
, СВ1 = 4: 
Ключевая строка I. СВ min = . В новый базис вводится вектор Р2, а его покидает вектор Р6. Генеральный элемент , т.к. Р6 выводится из базиса, то М будет отсутствовать.
Таблица 3
| Базис | С | Р0 | 2 | – 1 | 0 | 0 | 0 | СВ |
| Р1 | Р2 | Р3 | Р4 | Р5 | ||||
| Р6 | – 1 | 
| –
| 
| – | |||
| Р7 | 2 | 
|
| – 
| ||||
| Р5 | 0 |
| 
| |||||
| Z – строка | 
| 
| – 
|
3: = 
Z -строка
– 
– 
В столбце 3 не выполняются условия оптимальности. СВ1 = не имеет – 
< 0
2: 
. Из базиса выводим вектор Р5, а в базис будет введен Р3; генеральный элемент 
; построим таблицу 4:
Таблица 4
| Базис | С | Р0 | 2 | – 1 | 0 | 0 | 0 | СВ |
| Р1 | Р2 | Р3 | Р4 | Р5 | ||||
| Р2 | – 1 | 
| 
| |||||
| Р7 | 2 | 
| 
| |||||
| Р5 | 0 | 
| ||||||
| Z – строка | 
|
|
Условия оптимальности выполняются. Оптимальное решение имеет вид:
Х1 = 
Х2 = 
min (– Z) = – 
max = 
Задание:
1. Изучив опорный конспект, ответить на вопросы:
Ø Назвать, в каких формах существуют задачи линейного программирования (ЗЛП), в чем особенности каждой из форм;
Ø Алгоритм перехода от одной формы ЗЛП к другой;
Ø Алгоритм графического метода решения задач линейного программирования;
Ø Сформулировать идею симплекс-метода;
Ø Охарактеризовать симплекс-метод решения ЗЛП.
2. Внимательно разобрать образцы решенных примеров, записать их в тетрадь.
3. По образцу выполнить аналогичное задание домашней контрольной работы. Задание для домашней контрольной работы необходимо взять из «Методических рекомендаций», представленных далее, по порядковому номеру в списке группы. Можно выполнить в обычной тетради, сфотографировать или решить с использованием ПК и выслать на электронную почту преподавателя.