Задача ЛП, эквивалентная задаче о критическом пути

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

Вид работы	Контрольная
ВУЗ	ОмГУПС
Дата	18.10.2015
Преподаватель	Болотюк Е.А.
Вариант	Не указан

Раздел № 1 «Задачи линейного программирования»
Задача 1. Решить задачу линейного программирования графически. Составить эквивалентную ей каноническую задачу. 
F = x1+4x2 → min. при системе ограничений:
3x1+x2≥13
x1+x2≤9
x1-3x2≤1
x2 ≥ 0
Задача 2. Решить задачу ЛП симплекс−методом.
F(X) = 3x1 - x2 =max
x1 + 4x2≤12 
3x1 + 2x2≤11 
2x1 - x2≤5 
Задача 3. Решить задачу ЛП. найдя начальный опорный план методом искусственного базиса.
F(X) = x1 + x2 + 3x3 + 4x4 = min
5x1 - 6x2 + x3 - 2x4=2 
11x1 - 14x2 + 2x3 - 5x4=2 
Задача 4. Записать задачу ЛП. двойственную данной. решить одну из пары двойственных задач и найти оптимальное решение второй с помощью теорем двойственности.
F = x1-4x2 → min. при системе ограничений:
4x1-x2≥-12
x1+3x2≤10
2x1+x2≤10
x2 ≥ 0
Раздел № 2 «Некоторые специальные задачи линейного программирования»


Задача 5. Для данной транспортной задачи требуется:
1) составить соответствующую ей задачу линейного программирования;
2) составить двойственную ей задачу;
3) построить начальный опорный план  . используя метод северо-западного угла;
4) найти оптимальный опорный план перевозок. применяя метод потенциалов.
	 	 
	25	15	40	20
60	6	4	10	18
30	12	14	6	8
10	14	16	2	6
Задача 6. Дан сетевой график. Найти:
1) его графическое изображение;
2) кратчайший срок выполнения всего комплекса работ;
3) оптимальный календарный план;
4) резервы времени всех событий;
5) критический путь;
6) задачу ЛП. эквивалентную задаче о кратчайшем сроке;
7) задачу ЛП. эквивалентную задаче о критическом пути.

s	1	2	3	4	5	6	7	8	9	10
i. j	1. 2	2. 4	2. 5	1. 3	3. 4	3. 6	5. 7	6. 5	4. 6	6. 7
t	3	5	2	10	20	20	8	10	15	30