Каноническая задача линейного программирования

Содержание

Задача №219. 
Пусть имеется каноническая задача линейного программирования:
f(x) = x1+x2-3x3+x4-2x5
Необходимо последовательно выполнить следующие задания.
1. Задачу решить графическим методом.
2. Применяя симплекс-метод, решить задачу или установить, что задача не имеет решения. Начальный план рекомендуется искать методом искусственного базиса.
3. Построить двойственную задачу. Если вектор X найден, вычислить оптимальный план Y двойственной задачи, используя первую теорему двойственности Y = CD^-1. Вычислить значение функции ф(Y).
4. Провести анализ полученного решения, применяя условия дополняющей нежесткости.
Ответ -682/163.
Задача 319.
Ниже приведены числовые данные транспортных задач. Стоимость перевозки единицы продукции записаны в клетках таблицы. Запасы указаны справа от таблиц, а потребности - снизу. Требуется построить начальный план методами: «северо-западного угла», «минимального элемента», методом Фогеля. Из каждого плана найти оптимальный план методом потенциалов.
Ответ: 7098.
Задача 419. Дана транспортная задача в сетевой постановке. Задача изображена в виде неориентированного связного графа. На ребрах записаны значения удельных стоимостей cr, на вершинах (в кружках) — значения запасов-потребностей br. Построить пробный допустимый план, проверить его на оптимальность. В случае необходимости довести до оптимального плана методом потенциалов.
Ответ: 3129.
Задача 519.
Ниже приведены таблицы, в клетках которых проставлены элементы матрицы эффективностей cij задачи о разборчивой невесте.
Необходимо найти оптимальный вариант выбора, при котором средняя продолжительность семейной жизни каждой семьи будет наибольшей. Решить задачу методом потенциалов и венгерским методом.
Ответ: 348.
Задача 619.
Ниже приведены транспортные задачи с ограниченными пропускными способностями. Стоимость перевозки единицы продукции и предельные пропускные способности коммуникаций записаны через косую черту в клетках таблиц. Запасы указаны справа от таблиц, а потребности - снизу.
Найти оптимальное решение или доказать неразрешимость задачи.
На начальном этапе исследования задачи рекомендуется применить два метода: 1) классический; 2) минимального резерва пропускной способности.
Ответ: 1698.
Задача 719.
Предприятие выпускает скоропортящуюся продукцию А и В. Данные о её себестоимости, отпускных ценах и объемах реализации приведены в таблице. На реализацию всей произведенной продукции расходуется 300-219 рублей 
Определить ежедневный объем производства продукции, обеспечивающий наибольшую прибыль. 
Ответ: 15279,12, v1=2682, v2=2105.
Задача 819.
Ниже приведены комплексная задача линейного программирования. Необходимо выполнить в указанном порядке следующие задания.
1. Найти оптимальный план прямой задачи:
а) графическим методом;
б) симплекс-методом (для построения исходного опорного плана рекомендуется использовать метод искусственного базиса).
2. Построить двойственную задачу.
3. Найти оптимальный план двойственной задачи из графического решения прямой, используя условия дополняющей нежесткости.
4. Найти оптимальный план двойственной задачи по первой теореме двойственности, используя окончательную симплекс-таблицу, полученную при решении прямой задачи. Проверить утверждение «значения целевых функций пары двойственных задач на своих оптимальных решениях совпадают».
5. Двойственную задачу решить симплекс-методом, затем, используя окончательную симплекс-таблицу двойственной задачи найти оптимальный план прямой задачи по первой теореме двойственности.  Сравнить результат с результатом, полученный графическим методом.
6. Найти оптимальное целочисленное решение:
а) графическим методом;
б) Методом Гомори.
Сравнить значения функций целочисленного и нецелочисленного оптимальных решений.
Ответ: -162/11