Главная » Статьи » Решение задач » Задачи по математическим методам в экономике

Задача №24. Решение оптимизационной задачи симплексным методом

Задание

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

М – мука, кг

С – сахар, кг

О – орехи, кг.

УМ – упаковочный материал, м2

В – времени, чел-час.

Таблица 1

Сырье

Норма расхода ресурсов на 1 торт

Объем имеющихся ресурсов

А

Б

М

0,7

0,6

320

С

0,33

0,19

530

О

0,3

0,1

420

УМ

0,11

0,23

840

В

0,25

0,13

990

Прибыль на 1 торт, руб./шт.

24

48

 

 

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

Обозначим:         x1 – объём производства продукта А;
x2 – объём производства продукта Б.
x=(x1, x2 ) – план производства продукции А и Б.

Очевидно, что x1 ≥ 0, x2 ≥ 0.

Исходя из ограничений на сырье запишем неравенство:

Целевая функция – это прибыль от реализации всей продукции:

Z = 24x1 + 48x2 → max

Требуется найти x1 и x2 так чтобы они удовлетворяли системе ограничений и прибыль Z была бы максимальной.

Запишем эту задачу в форме основной задачи линейного программирования. Для этого перейдем от ограничений-неравенств к ограничениям-равенствам. Введем пять дополнительных переменных, в результате чего ограничения запишутся в виде системы уравнений:

Эти дополнительные переменные по экономическому смыслу означают не используемое при данном плане производства сырье того или иного вида. Составляем симплексную таблицу для первой итерации (табл. 1).

Таблица 2

Базис

Сб

P0

24

48

0

0

0

0

0

 

P1

P2

P3

P4

P5

P6

P7

P3

0

320

0,7

0,6

1

0

0

0

0

533,3

P4

0

530

0,33

0,19

0

1

0

0

0

2789,5

P5

0

420

0,3

0,1

0

0

1

0

0

4200,0

P6

0

840

0,11

0,23

0

0

0

1

0

3652,2

P7

0

990

0,25

0,13

0

0

0

0

1

7615,4

 

 

 

-24

-48

 

 

 

 

 

 

 

Наибольшее по модулю отрицательное число – -48, следовательно столбец Р2 включаем в базис. Для определения строки, исключаемой из базиса, столбец Р0 необходимо разделить на выбранный столбец Р2. Результат деления приведен в последнем столбце таблицы. Выбираем наименьший результат деления – 533,3. Следовательно, строка Р3 должна быть исключена из базиса.

Столбец вектора Р2 и первая строка являются направляющими, а элемент, находящийся на их пересечении, называется разрешающим элементом. Составляем таблицу для второй итерации (табл. 2).

Таблица 3

Базис

Сб

P0

24

48

0

0

0

0

0

P1

P2

P3

P4

P5

P6

P7

P2

48

533,3

1,167

1,000

1,667

0,000

0,000

0,000

0,000

P4

 

428,7

0,108

0

-0,317

1

0

0

0

P5

 

366,7

0,183

0

-0,167

0

1

0

0

P6

 

717,3

-0,158

0

-0,383

0

0

1

0

P7

 

920,7

0,098

0

-0,217

0

0

0

1

 

 

25600

32

0

80

0

0

0

0

 

Сначала заполняем строку вектора, вновь введенного в базис, т.е. первую строку. Элементы этой строки находятся делением соответствующих элементов табл. 1 на разрешающий элемент (т.е. 0,6). При этом в столбце Сб записываем коэффициент С2= 48, стоящий в столбце вводимого в базис вектора Р2.

Затем заполняем элементы столбцов для векторов, входящих в новый базис. В этих столбцах на пересечении строк и столбцов одноименных векторов проставляем единицы, а все остальные элементы полагаем равными нулю.

Для определения остальных элементов табл. 2 применяем правило треугольника.

Для вычисления какого-нибудь из этих элементов находят три числа:

1) число, стоящее в исходной симплекс-таблице на месте искомого элемента новой симплекс-таблицы;

2) число, стоящее в исходной симплекс-таблице на пересечении строки, в которой находится искомый элемент новой симплекс-таблицы, и столбца, соответствующего вектору, вводимому в базис;

3) число, стоящее в новой симплекс-таблице на пересечении столбца, в котором стоит искомый элемент, и строки вновь вводимого в базис вектора.

Эти три числа образуют своеобразный треугольник, две вершины которого соответствуют числам, находящимся в исходной симплекс-таблице, а третья – числу, находящемуся в новой симплекс-таблице. Для определения искомого элемента новой симплекс-таблицы из первого числа вычитают произведение второго и третьего.

Например, элемент, находящийся на пересечении столбца Р0 и второй строки, равен:

530 - 0.19*533.3 = 428.7

Третий элемент столбца Р0 равен:

520 - 0.10*533.3 = 366.7

Аналогично находятся остальные элементы таблицы.

По окончании расчетов получаем новый опорный план:

X = (0; 533.3; 0.428.7; 717.3; 920.7).

При данном плане производства изготовляется 533,3 тортов второго вида, мука используется полностью, остаются неиспользованными: сахар – 428,7 кг, орехи – 366,7 кг,  упаковочный материал – 717,3 м2, время – 920,7 чел.-часов. Стоимость продукции составит:

533.3*48 = 25600 д.е.

Поскольку отрицательных элементов в симплекс-таблице нет, данный план является оптимальным. 

Категория: Задачи по математическим методам в экономике | Добавил: Mirka (14.09.2014)
Просмотров: 2543 | Теги: оптимизационная задача | Рейтинг: 3.0/1
Всего комментариев: 0
avatar