Задание для самостоятельной работы
Дано: целевая функция и ограничения в виде неравенств.
Требуется: решить ЗЛП графическим и симплекс-методами.
1. В системах координат Х1, Х2 на основании заданных ограничений построить область допустимых решений.
2. Найти решение ЗЛП с помощью построения графика целевой функции.
3. Найти решение ЗЛП посредством вычисления целевой функции в граничных точках области допустимых решений. Сравнить результаты двух методов.
4. Привести ЗЛП в каноническому виду. Если ограничение имеет вид неравенства типа «», а в правой части ограничения стоит отрицательное число, то следует левую и правую часть ограничения умножить на –1, при этом неравенство приобретет вид «».
5. Построить симплекс-таблицу и решить ЗЛП симплекс-методом.
6. Если в правой части некоторой строки симплекс-таблицы стоит «0», то данную строку следует принять в качестве разрешающей.
7. После каждого пересчета коэффициентов симплекс-таблицы следует проверять выполнение ограничений-равенств. Если ограничения не выполняются, то пересчет произведен неверно.
8. Если в столбце свободных членов симплекс-таблицы после пересчета коэффициентов появились отрицательные числа, то либо неверно произведен пересчет коэффициентов, либо неправильно выбран разрешающий элемент.
1. Q = –3x1 – 2x2 min 2. Q = x1 – 2x2 min
x1 + 2x2 7 –x1 + x2 0
2x1 + x2 8 2x1 + x2 3
x2 3 – x1 + x2 –1
x1, x2 0 x1, x2 0
3. Q = –x1 – 3x2 min 4. Q = –x1 – x2 min
2x1 + x2 2 x1 3
x1 – x2 0 x2 2
x1 – x2 1 x1 +x2 1
x1, x2 0 x1, x2 0
5. Q = x2 – x1 min 6. Q = 2x1 + 3x2 max
2x1 – x2 4 x1 + x2 5
–x1 + 2x2 –2 x1 + 3x2 9
x1 + x2 5 x1 4
x1, x2 0 x1 + 2x2 8
x1, x2 0
7. Q = x2 – x1 min 8. Q = 4x1 + 6x2 max
–2x1 + x2 2 x1 + x2 18
x1 – 2x2 2 0,5x1 + x2 12
x1 + x2 5 x1 12
x1, x2 0 x2 9
x1, x2 0
9. Q = 2x1 + x2 max 10. Q = x1 + x2 max
2x1 + x2 1 x1 – x2 –1
3x1 – x2 –1 x1 – x2 1
x1 – 4x2 2 x1 2
x1, x2 0 x2 2
x1, x2 0
11. Q = –9x1 – 11x2 min 12. Q = –4x1 – 3x2 min
4x1 + 3x2 10 4x1 + x2 10
x1 5 2x1 + 3x2 8
x1 + 2x2 8 x1, x2 0
x1, x2 0
13. Q = x1 – 10x2 min 14. Q = x1 – 20x2 min
3x1 + x2 12 –x1 + 10x2 40
–8x1 + 3x2 24 4x1 + 2x2 29
x1, x2 0 x1, x2 0
15. Q = –x1 – 2x2 min 16. Q = 9x1 + 4x2 mах
x1 + 2x2 7 2х1 + 4х2 –14
2x1 + x2 8 2х1 + х2 8
x2 3 2x2 6
x1, x2 0 x1, x2 0
17. Q = – 2x1 – 4x2 min 18. Q = 2x1 + 6x2 mах
x1 – x2 – 7 –2х1 – х2 –2
4x1 + 2x2 3 2х1 – 2х2 0
x1 – x2 1 x1 – x2 1
x1, x2 0 x1, x2 0
19. Q = x1 + x2 mах 20. Q = –x1 + x2 mах
2x1 –6 –2х1 – х2 – 4
x2 2 –2х1 + 4х2 4
x1 + x2 1 x1 + x2 5
x1, x2 0 x1, x2 0
2.5. Приведение злп к каноническому виду
Процесс приведения задачи к каноническому виду называется нахождением начальной вершины.
1 случай. Ограничения имеют вид неравенств типа (), ЦФ стремится к минимуму:
(2.10)
Задача приводится к каноническому виду путем введения искусственных переменных, которые являются базисными. ЦФ не меняется.
(2.11)
2 случай. Ограничения имеют вид неравенств (), ЦФ минимизируется. Кроме этого, все коэффициенты ЦФ неотрицательны, а среди bi хотя бы один положительный.
Вводятся искусственные переменные, которые вычитаются из правых частей ограничений. Все коэффициенты ограничений домножаются на (–1):
(2.12)
Далее задача решается двойственным симплекс-методом. Двойственный симплекс-метод применяется, когда имеются базисные переменные в ограничениях-равенствах, все коэффициенты ЦФ положительны, ЦФ минимизируется, а среди правых частей ограничений имеется хотя бы одно отрицательное значение. Алгоритм двойственного симплекс-метода рассмотрен в п. 2.6.
3 случай. Ограничения имеют вид равенств, ЦФ минимизируется.
(2.13)
К такому виду сводятся все задачи линейного программирования, т.е. этот случай является общим.
Существует несколько методов приведения таких задач к каноническому виду. Один из них – метод искусственного базиса.