Транспортная задача и задача об использовании сырья

Транспортная задача и задача об использовании сырья

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

Определим значение целевой функции

Проверим оптимальность плана

Подсчитаем оценки свободных клеток

План близок к оптимальному.

При дальнейшем перераспределении груза, задача входит в циклическую фазу, план не улучшается. Таким образом, полученное решение является наиболее оптимальным для нашей задачи

Список литературы

Для подготовки данной применялись материалы сети Интернет из общего доступа