2. Билет № 11

3. Применение метода ветвей и границ для решения задачи коммивояжера. Приведение матрицы издержек. Нижняя оценка издержек. Верхняя граница издержек для оптимальных гамильтоновых циклов. Восстановление матрицы издержек для любого подмножества гамильтоновых циклов.

Проиллюстрировать изложение на примере задачи с матрицей издержек

С =

2. Московский Государственный Университет Экономики, Статистики и Информатики

3. Кафедра Прикладной математики

4. Предмет: Исследование операций и Методы оптимизации

5. Билет № 10

2. 1. Математическая модель задачи производственного планирования представлена ниже.

3. 3x₁+2x₂+3x₃  max

4. 2x₁+x₂+x₃ 20

5. 3x₁+4x₂+2x₃ 80

6. x₁ ,x₂ , x₃  0

7. С помощью модифицированного симплекс-метода (алгоритм 2) составить план выпуска продукции, максимизирующий суммарную стоимость продукции. Определить максимальный интервал изменения запасов каждого сырья, в пределах которого структура оптимального плана остается без изменения. Определить удельную ценность каждого сырья и суммарную стоимостную оценку сырья обоих видов, используемого при производстве единицы каждого изделия.

2. Найти решение транспортной задачи, исходные данные которой приведены в таблице, при дополнительных условиях: из А1 в В2 и из А3 в В5 перевозки не могут быть осуществлены, а из А3 в В4 будет завезено 20 единиц груза.

Поставщики	Потребители В1 В2 В3 В4 В5					Запасы
А1	1	2	3	1	4	200
А2	6	3	4	5	2	230
А3	8	2	1	9	3	100
Потребности	120	80	160	90	50

Зав. кафедрой ( Мастяева И.Н.)