- •Лекция 2
- •Симплексные таблицы
- •Транспортная задача
- •3.Метод Фогеля.
- •Теория графов. Основные понятия и определения
- •Способы задания графов
- •Сеть. Потоки на сетях. Задача нахождения патока максимальной мощности. Алгоритм Форда-Фалкерсона
- •Нахождение потока заданной мощности минимальной стоимости. Алгоритм Басокера-Гоуэна
Соловей Галина Николаевна
Линейное программирование. Постановка задач линейного программирования
Линейное программирование занимается изучением решений экстремальных задач, которые характеризуются линейной зависимостью между переменной и линейным критерием. Необходимое условие таких задач – наличие ограничения на ресурсы, величину спроса, производственную мощность и другое.
Математическая модель ЗЛП :
1.Максимум или минимум целевой функции(критерий оптимальности).
2.Система ограничений в форме линейных уравнений и неравенств.
3.Неотрицательность переменных.
Пример:
Фирма производит 2 модели А и В сборных полок, их производство ограничено наличием сырья(доски) и временем машинной обработки. Для одного изделия модели А требуется 3 метра кв. досок, модели В – 4. Фирма может получать до 1700 метров кв. досок. Для изделия А – 12 минут машинного времени, В – 30 мин. В неделю можно использовать 160 часов. Сколько изделий каждой модели следует выпускать в неделю макс прибыль, если А – 2$,B – 4$.
Ресурсы |
А |
В |
Ограничения |
Доски |
3 |
4 |
1700 |
Время |
0,2 |
0,5 |
160 |
Прибыль |
2 |
4 |
Макс |
|
|
|
|
|
|
|
|
Х1 – кол-во изделий А, Х2 – В.
(1)Zmax = 2X1+4X2
(2)3X1+4X2<=1700
0,2X1+0,5X2<=160
(3)X1,X2>=0
Решение, удовлетворяющее системе ограничения (2) и требованием (3) – допустимое, а (2),(3) + условия мин-макс – оптимизированное.
Общий вид задачи линейного программирования
Макс(мин)f(x)=C1X1+C2X2+…+CnXn (1)
A11X1+A12X2+…+A1nXn<=b1
A21X1+A22X2+…+A2nXn<=b2
Am1X1+Am2X2+…AmnXn<=bm
X1,x2…>=0
Свойства:
1.Допкстимое множество решений ЗЛП либо пустое, либо является выпуклым многогранником.
2.Если допустимое множество не пустое, а целевая функция ограничена сверху для максимизации , а снизу – для минимизации, то она имеет оптимальное решение.
3.Оптимпльное решение задач линейного программирования (если они существуют)то находятся на границе, т.е. если существует оптимальное решение, то им является одна из вершин многогранника допустимых решений, если 2 или несколько вершин допустимые решения, то любая их комбинация является оптимальным решением.
При изготовлении изделий И1 и И2 используются токарные и фрезерные станки, а так же сталь и цветные металлы. По технологическим нормам на производство изделия И1 требуется 300 и 200 единиц соответственно токарного и фрезерного оборудования, 10 и 20 единиц стали и цвет мет; для И2 – 400, 100, 70, 50. Цех располагает 12400, 6800, 640, 840 . Прибыль от реализации И1 – 6, И2 -16.
Ресурсы |
И1 |
И2 |
Ограничения |
Токарный |
300 |
400 |
12400 |
Фрезерный |
200 |
100 |
6800 |
Сталь |
10 |
70 |
640 |
Цвет мет |
20 |
50 |
840 |
Прибыль |
6 |
16 |
Макс |
|
|
|
|
Х1 – кол-во И1, Х2 – кол-во И2.
300Х1+400Х2<=12400
200X1+100X2<=6800
10X1+70X2<=640
20X1+50X2<=840
Zmax=6X1+16X2
X1,X2>=0
3 формы записи
Формы записи задач линейного программирования
Модель задачи линейного программирования может быть записана в одной из приведенных ниже форм:
1.Общая форма записи – целевая фунуция записывается: max(min)z=
///
2.Симметричная – maxZ= , minZ=
Указанные выше формы записи задач линейного программирования эквивалентны в том смысле, что каждая из них с помощью несложных преобразований может быть сведена к другой форме.
Лекция 2
Графический метод решения ЗЛП
Если число неизвестных равно 2, то ее можно решить графическим методом. Найти решение Найти решение х=(х1,х2)
Макс(мин)Z=C1X1+C2X2 (1)
Sum(AijXj)<=bi (2)
X1,X2>=0
Каждое из неравенств 2 определяет на координатной плоскости полуплоскость, а система неравенств 2 и 3 в случае ее совместимости – пересечение плоскостей. Это будет выпуклое множество, которое может быть представлено как:
1.Выпуклый многоугольник.
2.Выпуклая неограниченная многоугольная область.
3.Отрезок.
4.Луч.
5.Одна точка.
6.Пустое множество.
Геометрическая интерпретация целевой функции:
Z=C1X1+C2X2 (1)
При фиксированных значениях Z=Z0 определяет линию. При изменении Z получим семейство параллельных прямых, называемых линиями уровня. Вектор С=(С1 , С2) перпендикулярен каждой из линий уровня. Вектор С показывает направления наибольшего возрастания(убывания) целевой функции.
Если построить на одном рисунке область допустимых решений вектор С и одну из линий уровня, например Z=0, то задача сводится к определению области допустимых решений точки направления вектора С, через которую проходит линия уровня Z макс(мин), соответствующая наибольшему(меньшему) значению функции Z. Если задача рерзрешима могкт представиться следующие случаи:
1.Задача имеет единств решение.
2.Задача имеет бесконечное множество решений(альтернативный оптимум).
3.Целевая функция не ограничена, область допустимых решений – единственная точка(рис. 1).
Х1
Х2
Max(min)Z=2X1+3X2
X2
1 3
2
X1
Проверяем каждую вершину.
Zmin()=2*(4/9)+3*(8/9)=32/9
Zmax=2*2+3*4=16
Симплекс-метод
Построение начального опорного плана
Рассмотрим 3 случая.
Пусть система ограничений имеет вид
Xi+ ijXj=bi , bi=>0,(i=1,m)
X0=(0,0,…,0,bi)
Ограничение канонической задачи линейного программирования имеет предпочтительный вид, если при неотрицательной его части левая часть содержит переменную, входящую с коэффициентом равным 1, а остальные с коэффициентом равным 0. Если каждое ограничение канонической задачи линейного программирования имеет предпочтительный вид, т.е. система ограничений приведена к единичному неотрицательному базису, то начальный опорный план строиться следующим образом: Предпочтительные переменные выбираются в качестве базисных, а все остальные свободные. Свободные переменные приравниваются к нулю, а базисные – к свободным членам(bi).
Пример:
minZ=-5X1+6X3
2X1-2 X3+ X4=2| X4
2 X1+ X2- X3=3 | X2
X1>=0
X0=(0,3,0,2)
ijXj<=bi, bi>=0
Xn+i>=0
ijXj+Xn+1=bi, bi>=0
X0=(0,…,0,bi,...,bm)
Пример 2:
minZ=10 X1-7 X2-5 X3
6 X1+15 X2+6 X3<=9
14 X1+42 X2+16 X3<=21
2X1+8 X2+2 X3<=4
тогда
6 X1+15 X2+6 X3+ X4=9
14 X1+42 X2+16 X3+ X5=21
2X1+8 X2+2 X3+ X6=4
X0=(0,0,0,9,21,4)
ijXj>=bi , bi>=0
ijXj-Xn+i=bi
M-задача
Max(min)Z= jXj-(+)M i
minZ=-5 X1+4X2+3 X3+6X4
X1+21X2+ X3+2X4<=3
-X1-14X2-2X3+3X4>=2
-X1-6X2+X3-X4>=1
X1+21X2+ X3+2X4+ X5=3
-X1-14X2-2X3+3X4- X6+W1=2
-X1-6X2+X3-X4- X7 +W2=1
X0=(0,0,0,0,3,0,0,2,1)
Z(X0)=3M
Пример:
maxZ=5 X1+7 X2+6 X3+11X4
3X1+4 X2 -3 X3 <=12|+ X5
X1 -4 X4 <=22 | +X6
X2 + X3 +3 X4 <=6 |+ X7
X0 =(0,0,0,0,12,22,6)
Пример 2:
maxZ= X1 +2 X2 +3 X3 +4 X4
4X1+3X2+7X3 =9 |+Wi
X1 +2 X2 -5 X4 >=21|- X5 +W2
4 X2 +7 X3 – X4 >=7|- X6 +W3
X0 =(0,0,0,0,0,0,9,21,7)
Z(X0)=37M
Симплексные таблицы
maxZ= 18X1 +20 X2 +32 X3
18X1+15X2+12X3 <=720
6X1 +4 X2 +8 X4 <=384
5X1 +3X2 +12X3 >=360
БП |
СБ |
А0 |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|
|
|
18 |
20 |
32 |
0 |
0 |
0 |
Х4 |
0 |
720 |
18 |
15 |
12 |
1 |
0 |
0 |
Х5 |
0 |
384 |
6 |
4 |
8 |
0 |
1 |
0 |
Х6 |
0 |
360 |
5 |
3 |
12 |
0 |
0 |
1 |
|
Сj |
0 |
-18 |
-20 |
-32 |
0 |
0 |
0 |
Рабочая часть таблицы начинается с 3 строки и 3 столбцы. В БП занесены базисные(предпочтительные) переменные; СБ содержит коэффициенты целевой функции, стоящие при базисных переменных; Ао содержит свободные члены Вi. Сверху, над рабочей частью таблицы указаны все переменные и коэффициенты целевой функции.
Хо=(0,0,0,720,384,360)
Z(Xo)=0