Транспортная задача и задача об использовании сырья
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 Определим значение целевой функции
Проверим оптимальность плана
Подсчитаем оценки свободных клеток
План близок к оптимальному. При дальнейшем перераспределении груза, задача входит в
циклическую фазу, план не улучшается. Таким образом, полученное решение
является наиболее оптимальным для нашей задачи
Больше работ по теме:
Предмет: Финансы, деньги, кредит
Тип работы: Не выбран
Новости образования
КОНТАКТНЫЙ EMAIL: [email protected]
Скачать реферат © 2017 | Пользовательское соглашение
ПРОФЕССИОНАЛЬНАЯ ПОМОЩЬ СТУДЕНТАМ