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

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

 

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

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

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

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

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