Задача 1. Предприятие располагает тремя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 час работы первым способом выпускается 20 единиц продукции, а вторым – 30

Задача 1. Предприятие располагает тремя видами сырья и может выпускать одну и ту же продукцию двумя способами. При этом за 1 час работы первым способом выпускается 20 единиц продукции, а вторым – 30. Исходные данные приведены в таблице:

Виды сырья	Расход сырья (кг) за 1 час работы способом	Запасы сырья, кг
первым	вторым
I
II
III

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

Решение

1. Составим математическую модель задачи:

Пусть - время производства продукции при первом способе расхода сырья, значит – время производства продукции при втором способе расхода сырья. Целевая функция – выручка от реализации продукции.

Таким образом приходим к следующей системе неравенств:

На неизвестные задачи накладываем условие неотрицательности:

Целевая функция подлежит максимизации.

2. Графический метод решения.

Меняем в системе знаки неравенств на равно:

Строим графики функций.

(1); (2); (3)

По рисунку видно, что все ограничения соблюдаются в многоугольнике ABCDE. Построив график целевой функции и сдвинув его в направлении вектора получаем точку С, в которой целевая функция принимает максимальное значение. Точка С лежит на пересечении прямых (1) и (3). Решаем систему уравнений:

Получаем:

Вычислим значение целевой функции в этой точке:

(ед)

Ответ: целевая функция максимальна в точке С(2;4) и равна 160 ед.

3. Решаем задачу симплексным методом.

Приведём задачу к каноническому виду:

Получили задачу в базисной форме, где переменные – базис­ные. Находим первое опорное решение: , ; ; . Значение целевой функции при данном плане равно .

Используя запись задачи в базисной форме и найденный опорный план, заполняем первые три строки первой симплексной таблицы.

Первая симплексная таблица

				20	30	0	0	0
1	0		100	10	20	1	0	0	5
2	0		100	20	10	0	1	0	10
3	0		90	15	15	0	0	1	6
4			0	-20	-30	1	0	0

Рассчитываем показатели четвертой строки:

,

.

Так как оценка отрицательна, то ключевым на данной итерации будет столбец переменной , строка 1, ключевой элемент .

Переходим ко второй симплексной таблице.

Вторая симплексная таблица

				20	30	0	0	0
1	30		5	0,5	1	0,05	0	0	10
2	0		50	15	0	-0,5	1	0
3	0		15	7,5	0	-0,75	0	1	2
4			150	-5	0	1,5	0	0

В столбце вместо переменной записываем переменную .

Определяем показатели оценочной строки:

Новый опорный план задачи: , , , ; . Так как в оценочной строке имеется оценка , то полученное решение не является оптимальным.

Переходим к третьей симплексной таблице. Заменяем на .

Третья симплексная таблица

				20	30	0	0	0
1	30		4	0	1	0,1	0	0
2	0		20	0	0	1	1	0
3	20		2	1	0	-0,1	0	0
4			160	0	0	1	0	0

Значения всех -оценок неотрицательны, поэтому полученное решение является оптимальным и при этом целевая функция принимает значение .

Ответ: , это означает, что наибольшее количество продукции 160 шт. будет выпущено при условии, что время производства продукции при первом способе расхода сырья составит 2 часа, при втором 4 часа.

Задача 2. В три пункта отправления поступил однородный груз в количествах 115, 175, 130 единиц соответственно. Этот груз требуется в четырех пунктах назначения в количествах соответственно равных 70, 220, 40 и 30 единиц. Тарифы на перевозку единицы груза (д.е.) известны и задаются матрицей С:

.

Найти план перевозок груза от отправителей к потребителям, при котором общие транспортные расходы минимальны.

Решение.

1. Методом северо-западного угла.

Общий запас груза в пунктах отправления составляет 420 единиц, а общая потребность в грузе в пунктах назначения – 360 единиц. Следовательно, модель транспортной задачи открытая. Введем фиктивный пятый пункт назначения с потребностью 60 единиц, а будем считать равными нулю.

Первый опорный план

Пункты отправления	Пункты назначения	Запасы
B1	B2	B3	B4	B5
A1		5 45	2
A2							-4
A3		0	7
Потребности
Vj					-1

В результате получаем опорный план:

Согласно данному плану перевозок, транспортные расходы составляют:

(д.е.)

Полученный опорный план невырожденный, так как количество занятых клеток равно 3 + 5 – 1 = 7.

Опорный план проверяем на оптимальность. Для этого находим потенциалы поставщиков и потребителей. Положим U₁ = 0, тогда, работая с занятыми клетками.

Для каждой свободной клетки вычисляем :

Так как среди чисел имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану. Единственной положительной оценкой является .

Строим цикл перерасчета.

Пункты отправления	Пункты назначения	Запасы
B1	B2	B3	B4	B5
A1
A2							-4
A3
Потребности
Vj					-1

Получаем новый невырожденный опорный план, который проверяем на оптимальность. Находим потенциалы поставщиков и потребителей. Для свободных клеток вычисляем :

Так как среди чисел нет положительных, то полученный план

является оптимальным. При данном плане транспортные расходы составляют:

(д.е.)

Ответ: получен оптимальный план перевозок груза

с минимальными транспортными расходами 860 д.е. Это означает, что минимальные транспортные расходы на перевозку груза составят 860 д.е. при условии, что в первый пункт назначения груз доставят из первого пункта отправления в количестве 70 единиц; во второй пункт назначения груз доставят из первого, второго и третьего пунктов отправления в количествах соответственно 5, 175 и 40 единиц; в третий пункт назначения – из первого пункта отправления в количестве 40 единиц и в четвертый пункт назначения – из третьего пункта отправления в количестве 30 единиц.

2. Методом аппроксимации Фогеля.

Строим первый опорный план:

Пункты отправления

Пункты назначения

Запасы

Разности по строкам

В1

В2

В3

В4

В5

А1

А2

-

-

А3

Потребности

Разности по столбцам

-

-

-

-

-

-

-

-

-

-

-

-

-

(д.е.)

Ответ: Минимальные транспортные расходы на перевозку груза составят 860 д.е. при условии, что в первый пункт назначения груз доставят из первого пункта отправления в количестве 70 единиц; во второй пункт назначения груз доставят из первого, второго и третьего пунктов отправления в количествах соответственно 5, 175 и 40 единиц; в третий пункт назначения – из первого пункта отправления в количестве 40 единиц и в четвертый пункт назначения – из третьего пункта отправления в количестве 30 единиц.

Дата добавления: 2015-09-30