Транспортная задача и задача об использовании сырья
1. Решить задачу об использовании сырья геометрическим способом и симплекс методом, дать экономическую интерпретацию.
| 75 | 5 | 3 |
| 83 | 4 | 7 |
| 50 | 1 | 5 |
| 4 | 5 |
Геометрический способ.
Пусть количество выпускаемой продукции первого вида, тогда количество выпускаемой продукции второго вида. Прибыль от реализации всей продукции составляет .
Цель задачи (максимализация прибыли) запишется в виде
Структура всех трёх ограничений одинакова
Перейдём из неравенств к уравнениям
Построим прямые на плоскости
Многоугольник решений . Для нахождения максимума функции построим начальную прямую и вектор . Передвигая прямую вдоль вектора получим, что максимальное значение наша прямая принимает в точке точке пересечения прямых и .
.
Симплекс метод.
Приведём систему неравенств к системе уравнений
Целевая функция – функция прибыли
Составим симплекс таблицу:
- Первое ограничение запишем в первую строку
- Второе ограничение запишем во вторую строку
- Третье ограничение запишем в третью строку
Целевую функцию запишем в строку
| Б | З | |||||
| 75 | 5 | 3 | 1 | 0 | 0 | |
| 83 | 4 | 7 | 0 | 1 | 0 | |
| 50 | 1 | 5 | 0 | 0 | 1 | |
| 0 | 0 | 0 | 0 |
В строке есть отрицательные начальный план не оптимален. Найдём наименьший отрицательный элемент строки . Переменная будет включена в базис. Столбец переменной – ведущий. Подсчитаем симплексные отношения и найдём среди них минимальное третья строка ведущая, а элемент разрешающий. Следовательно переменная выйдет из базиса.
Проведём одну интеракцию метода замещения Жордано-Гаусса. Столбцы. Разрешающий элемент
равен поделим третью строку на 5, столбец сделаем единичным для этого третью строку умножим на и прибавим к первой строке, третью строку умножим на и сложим со второй строкой; третью строку сложим со строкой . Получим новую симплексную таблицу
| Б | З | |||||
| 45 | 0 | 1 | 0 | |||
| 13 | 0 | 0 | 1 | |||
| 10 | 1 | 0 | 0 | |||
| 50 | 0 | 0 | 0 | 1 |
В строке есть отрицательные план не оптимальный. Рассчитаем симплексные отношения и найдём среди них минимальное вторая строка ведущая разрешающий
Следовательно, переменная выйдёт из базиса. Так как разрешающий элемент , поделим строку, соответствующую переменной на . Элементы столбца, соответствующего переменной отличны от элемента сделаем нулевыми, для этого вторую строку умножим на и прибавим к первой; вторую строку умножим на и прибавим к третьей; вторую строку умножим на и прибавим к строке . Получим новую симплексную таблицу
| Б | З | |||||
| 23 | 0 | 0 | 1 | |||
| 5 | 1 | 0 | 0 | |||
| 9 | 0 | 1 | 0 | |||
| 65 | 0 | 0 | 0 |
В строке есть
| Б | З | |||||
| 13 | 0 | 0 | 1 | |||
| 12 | 1 | 0 | 0 | |||
| 5 | 0 | 1 | 0 | |||
| 73 | 0 | 0 | 0 |
Так как в строке все элементы неотрицательны, то найден оптимальный план
Оптимальный план найденный геометрическим способом и симплексным методом совпадают. Предприятию необходимо выпускать 12 единиц продукции первого вида и 5 единиц продукции второго вида. В этом случае предприятие получит прибыль денежных единиц.
2. Решить транспортную задачу распределительным методом, оценивая свободные клетки по методу потенциалов.
|
|
60 |
50 |
85 |
75 |
| 65 | 8 | 10 | 6 | 5 65 |
| 80 | 4 30 |
3 50 |
5 | 9 |
| 35 | 11 25 |
4 | 4 | 8 10 |
| 90 | 5 5 |
5 | 3 85 |
6 |
Проверим необходимое и достаточное условие разрешимости задачи
Потребность в грузе равна запасам груза задача закрытая, следовательно, имеет единственное решение.
Используя метод наименьшей стоимости заполним таблицу.
Среди тарифов наилучшим является и . Направим например,
в клетку
в клетку
в клетку
в клетку
в клетку
в клетку
в клетку
Запасы поставщиков исчерпаны, запросы потребителей удовлетворены полностью. В результате получили первый опорный план. Подсчитаем число занятых клеток таблицы их 7, а должно быть опорный план не вырожденный.
Определим значение целевой функции первого опорного плана
Проверим оптимальность плана.
Найдём потенциалы и по занятым клеткам таблицы
Пусть , тогда:
Подсчитаем оценки свободных клеток
Первый опорный план не является оптимальным так как .
Переходим к его улучшению. Для клетки строим цикл перераспределения
В результате получили новый опорный план
|
|
60 |
50 |
85 |
75 |
| 65 | 8 | 10 | 6 | 5 65 |
| 80 | 4 55 |
3 25 |
5 | 9 |
| 35 | 11 |
4 25 |
4 | 8 10 |
| 90 | 5 5 |
5 | 3 85 |
6 |
Определим значение целевой функции
Проверим оптимальность плана
Подсчитаем оценки свободных клеток
План близок к оптимальному.
При дальнейшем перераспределении груза, задача входит в циклическую фазу, план не улучшается. Таким образом, полученное решение является наиболее оптимальным для нашей задачи