Линейное программирование

Дисциплина Методы оптимизации

Вид работы	Контрольная
ВУЗ	ОмГУПС
Дата	18.02.2016
Вариант	Не указан

Задача 1. Решить задачу линейного программирования графически. Составить эквивалентную ей каноническую задачу.
f(x)=x1+4x2=min
3x1+x2>=13
x1+x2<=9
x1-3x2<=1
x2>=0
Задача 2. Решить задачу ЛП симплекс&#8722;методом.
f(x)=-2x1+3x2=max
-5x1+4x2<=4
4x1+6x2<=29
5x1+x2<=20
x1,x2>=0
Задача 3. Решить задачу ЛП, найдя начальный опорный план методом искусственного базиса.
f(x)=x1+x2+3x3+4x4=min
5x1-6x2+x3-2x4=2
11x1-14x2+2x3-5x4=2
x1,x2,x3,x4>=0
Задача 4. Записать задачу ЛП, двойственную данной, решить одну из пары двойственных задач и найти оптимальное решение второй с помощью теорем двойственности.
f(x)=2x1-5x2=min
2x1+x2>=-2
x1-8x2>=-35
5x1-2x2<=15
x2>=0
1) составить соответствующую ей задачу линейного программирования;
2) составить двойственную ей задачу;
3) построить начальный опорный план  , используя метод северо-западного угла;
4) найти оптимальный опорный план перевозок, применяя метод потенциалов.
		40	25	15	20
	30	3	5	2	5
	25	4	7	8	1
	45	8	6	4	3
Задача 6. Дан сетевой график. Найти:
1) его графическое изображение;
2) кратчайший срок выполнения всего комплекса работ;
3) оптимальный календарный план;
4) резервы времени всех событий;
5) критический путь;
6) задачу ЛП, эквивалентную задаче о кратчайшем сроке;
7) задачу ЛП, эквивалентную задаче о критическом пути.
	s	1	2	3	4	5	6	7	8	9	10	11
	i, j	1, 2	3, 5	6, 7	3, 4	5, 7	1, 3	3, 6	4, 6	1, 4	5, 6	2, 3
	t	5	4	8	7	3	8	6	10	3	5	2