Задачи 401 - 500 (с.153 - 162)

Ниже приведены комплексные задачи линейного программирования.

Необходимо выполнить в указанном порядке следующие задания.

1. Найти оптимальный план задачи графическим методом.

2. Построить двойственную задачу.

3. Найти оптимальный план двойственной задачи из графического решения прямой задачи, используя условия дополняющей нежесткости.

4. Найти оптимальный план прямой задачи симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).

5. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи (см. п.4). Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».

6. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности. Сравнить результат с результатом, который был получен графическим методом (см. п.1).

Задачи 501 – 600 (с.209– 219)

Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности – снизу.

Требуется построить начальный план методами северо-западного угла, минимального элемента, методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.

Задачи 601 – 700 (с.240– 274)

Ниже приведено 100 вариантов транспортной задачи в сетевой постановке. Каждая задача изображена в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей c_r, на вершинах (в кружках) – значения запасов-потребностей b_j. Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.