Лабораторная работа №1
Тема «Построение коммуникационной сети минимальной длины
(минимальное порождающее дерево)»
Цель… Решение задач сетевой оптимизации
Задачи
Разработать алгоритм Прима.
Провести моделирование.
Предоставить реализацию и отчет.
Описание алгоритма Прима
Список источников и литературы
1. Prim R.C.Shortest connextion networks and some generalizations // Bell System Tech. J., 36(1957), pp.1389-1401.
Лабораторная работа №2
Тема «Задачи определения кратчайшего пути (Кратчайший маршрут)»
Цель Решение задач сетевой оптимизации …
Задачи
Разработать алгоритм Дейкстры.
Провести моделирование.
Предоставить реализацию и отчет.
Описание алгоритма Дейкстры.
Лабораторная работа №3
Тема «Задачи определения максимального потока»
Цель…
Задачи
Решить задачу "вручную"
выслать отсканированный рез-т
А. Б. Аронович и др «Сборник задач по исследованию операций», Задача 19.3
Нефтяная компания «Лукойл» владеет сетью нефтепроводов, через которые нефть перекачивается от месторождения до нефтехранилищ. Часть этой сети представлена на рисунке (пропускная способность нефтепроводов показана в тыс. т/ч).
1. Если фирма хочет поставить нефть в хранилище 7 и полностью использовать пропускную способность системы, то, сколько времени займёт поставка в седьмое нефтехранилище 10 тыс. т нефти?
2. Если на линии 2 – 3 случится авария, и она будет закрыта, каким будет максимальный поток для системы (тыс. т/ч)?
Лабораторная работа №4
Тема «Графический метод решения ЗЛП. Исследование решения на чувствительность»
Цель…
Задачи
Повторить теорию по графическому решению ЗЛП
Выполнить задание №1 в соотв.с номером варианта
Изучить теор.материал по исследовании. решения на чувствительность.
Выполнить задание №2 в соотв.с номером варианта
Подготовиться к ответу на контрольные вопросы.
Контрольные вопросы
Запишите ЗЛП в форме ОЗЛП.
Запишите ЗЛП в форме ОснЗЛП.
Запишите ЗЛП в форме КЗЛП.
Приведите ОЗЛП к каноническому виду.
Приведите ОснЗЛП к каноническому виду.
Дайте определение плана КЗЛП.
Перечислите свойства множества планов Р.
Дайте определение оптимального плана КЗЛП.
Какая ЗЛП называется разрешимой?
Дайте определение выпуклого множества.
Дайте определение гиперплоскости.
Дайте определение полупространства.
Что называется крайней, или угловой, точкой множества Р?
Дайте определение градиента функции.
Запишите градиент функции f(x) = с1x1 + c2x2.
Что называется линией уровня целевой функции?
В каких случаях при решении ЗЛП графическим методом можно убедиться в ее неразрешимости?
Что означает разрешимость ЗЛП при графическом методе ее решения?
Запишите КЗЛП в алгебраической форме.
Запишите КЗЛП в векторно-матричной форме.
Дайте определение опорного плана КЗЛП.
Число опорных планов конечно или нет?
Сформулируйте связь между опорным планом и крайней точкой.
Сформулируйте утверждение о существовании оптимального опорного плана.
Задание №1
2. Решить графическим методом задачу.
Из трех сортов бензина образуются две смеси.
Варианты для задачи 1
Первая состоит из
А1 % бензина первого сорта,
В1 % бензина 2-го сорта,
С1 % бензина 3-го сорта;
вторая:
А2 % – 1-го,
В2 % –2-го,
С2 % – 3-го сорта.
Цена 1-й смеси – 305 у.е.,
второй – 200 у.е. за тонну.
Сколько смеси первого и второго вида можно изготовить из “а” тонн 1-го сорта,
“b” тонн 2-го сорта и
“с”тонн 3-го сорта, чтобы получить максимальный доход?
Задание №2 (номера вариантов приведены)
Решить задачу графическим методом и провести анализ на чувствительность, ответив на вопросы 1–5.
Для приготовления двух видов продукции (A, B) используют три вида сырья. Ресурсы сырья, норма его расхода на единицу продукции и цена продукции заданы в соответствующей таблице.
1. Определить план выпуска продукции из условия максимизации его стоимости.
2. Определить интервал изменения цены на продукцию А, при котором структура оптимального решения останется неизменной.
3. Определить интервал изменения цены на продукцию В, при котором структура оптимального решения останется неизменной.
4. Определить статус, ценность каждого ресурса и его приоритет при решении задачи увеличения запаса ресурсов.
5. Определить максимальный интервал изменения запасов каждого из ресурсов, в пределах которого структура оптимального решения, то есть номенклатура выпускаемой продукции, остается без изменения.
В
арианты
для задачи 2.
