Вариант 8
Решите задачу графическим методом. Найти максимум и минимум функции при ограничениях
Решение:
Решим задачу графическим методом. С учетом системы ограничений построим множество допустимых решений. Строим в системе координат прямые:
Изобразим полуплоскости, определяемые системой ограничений. Находим множество допустимых решений как общую часть полученных полуплоскостей – неограниченная область Вектор градиентного направления
Минимальное значение функции
Чтобы найти минимальное значение целевой функции, перемещаем линию уровня в направлении вектору-градиенту до первого касания области допустимых решений На отрезке прямой от точки до точки целевая функция достигает минимума.
Координаты точки – точки пересечения и :
Координаты точки – точки пересечения и :
Значение целевой функции
Максимальное значение функции
Чтобы найти максимальное значение целевой функции, перемещаем линию уровня в направлении вектора-градиента до последнего касания области допустимых решений Так область допустимых решений неограниченна справа, целевая функция также неограниченна сверху. Задача на максимум не имеет решения.
Ответ: на отрезке прямой от точки до точки целевая функция неограниченна сверху.
Решить задачу ЛП симплексным методом
при ограничениях
Решение:
Решим задачу симплекс-методом. Преобразуем исходную модель. В ограничения типа добавим дополнительные переменные . Модель задачи будет выглядеть так:
при условиях:
Стандартная форма записи модели:
при условиях:
Заполним первую симплекс-таблицу. БП
|
|
|
|
|
|
|
| Решение
| Отношение
|
| 0
| 1
| 3
| 2
| 2
| 1
| 0
| 3
| 3/1=3
|
| 0
| 2
| 2
| 1
| 1
| 0
| 1
| 3
| 3/2
|
| -5
| -3
| -4
| 1
| 0
| 0
| 0
|
| В среди оценок есть отрицательные значения, следовательно, план не является оптимальным. Среди значений находим наибольшее по абсолютной величине , столбец выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений – ведущая строка. Элемент 2 на пересечении ведущего столбца и ведущей строки – разрешающий элемент. Переходим к следующей симплексной таблице. БП
|
|
|
|
|
|
|
| Решение
| Отношение
|
| 0
| 0
| 2
| 3/2
| 3/2
| 1
| -1/2
| 3/2
| 3/2/(3/2)=1
|
| 2
| 1
| 1
| 1/2
| 1/2
| 0
| 1/2
| 3/2
| 3/2/(1/2)=3
|
| 0
| 2
| -3/2
| 7/2
| 0
| 5/2
| 15/2
|
| В среди оценок есть отрицательное значение, следовательно, план не является оптимальным. Столбец выбираем в качестве ведущего. Для положительных элементов ведущего столбца находим наименьшее из симплексных отношений – ведущая строка. Элемент 5/2 на пересечении ведущего столбца и ведущей строки – разрешающий элемент. Переходим к следующей симплексной таблице. БП
|
|
|
|
|
|
|
| Решение
|
| 4
| 0
| 4/3
| 1
| 1
| 2/3
| -1/3
| 1
|
| 2
| 1
| 1/3
| 0
| 0
| -1/3
| 2/3
| 1
|
| 0
| 4
| 0
| 5
| 1
| 2
| 9
| В среди оценок нет отрицательных, следовательно, план является оптимальным.
Возвращаясь к исходной задаче четырех переменных, запишем оптимальное решение:
Ответ: .
Решить транспортную задачу методом потенциалов
| 80
| 120
| 70
| 30
| 80
| 3
| 1
| 2
| 1
| 100
| 2
| 4
| 2
| 2
| 120
| 1
| 3
| 5
| 2
| Решение:
Проверяем условие баланса:
Так как задача сбалансированная.
Строим начальный план методом «минимальной стоимости». Вписываем в ячейку (имеет наименьший тариф 1) наименьшее из значений и и исключаем из дальнейшего рассмотрения строку. Потребности второго потребителя уменьшаются на величину Далее в ячейку записываем наименьшее из значений и и исключаем из дальнейшего рассмотрения столбец. Запасы третьего поставщика уменьшаются на величину
С оставшейся матрицей поступаем аналогично предыдущему:
Поставщики
| Потребители
| Мощности
поставщиков
|
|
|
|
|
| 3
| 1
80
| 2
| 1
| 80
|
| 2
| 4
30
| 2
70
| 2
| 100
|
| 1
80
| 3
10
| 5
| 2
30
| 120
| Мощности
потребителей
| 80
| 120
| 70
| 30
| 300
| Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок равно Определим полную стоимость перевозок по найденному опорному плану:
Проверим план, построенный методом «минимальной стоимости» на оптимальность. С помощью метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен , то если известен , то Положим, например, Тогда будут вычислены и остальные потенциалы строк и столбцов.
|
|
|
|
|
| 3
| 1
80
| 2
| 1
|
| 2
|
- 4
30
| 2
70
| + 2
|
| 1
80
| + 3
10
| 5
| - 2
30
| Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Начиная с клетки разметим вершины контура попеременно знаками плюс «+», минус «-», обходя замкнутый контур в любом направлении. Из клеток, помеченных знаком «-», выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 30 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».
|
|
|
|
|
| 3
| 1
80
| 2
| 1
|
| 2
| 4
| 2
70
| 2
30
|
| 1
80
| 3
40
| 5
| 2
0
| Определим полную стоимость перевозок по найденному опорному плану:
Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:
Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален.
Ответ: оптимальный план перевозок, обеспечивающий минимальные затраты (усл.ед.): Поставщики
| Потребители
| Мощности
поставщиков
|
|
|
|
|
| 3
| 1
80
| 2
| 1
| 80
|
| 2
| 4
| 2
70
| 2
30
| 100
|
| 1
80
| 3
40
| 5
| 2
0
| 120
| Мощности
потребителей
| 80
| 120
| 70
| 30
| 300
| |