| Назад |
| Содержание |
| Дальше |
Задача 1. Решение задачи симплексным методом линейного программирования.
( автор сайта: Климант Ю.В. )
Задача.
Для кондитерской фабрики требуется рассчитать оптимальный план выпуска карамели. Весь ассортимент карамели
разделен на три однородные группы, условно обозначенные A, B и C. Для производства карамели требуются
сахарный песок, патока, фруктовое пюре. Запасы этих видов сырья равны соответственно 700, 300 и 150 тонн.
Другие виды сырья, входящие в готовый продукт в небольших количествах, не учитываются. В качестве критерия
оптимальности плана принять максимум прибыли. Уровень прибыли на единицу каждого вида выпускаемой карамели
( в денежных единицах за 1 тонну): для A - 1000, для B - 1100, для C - 1200. Нормы расхода сырья на
производство единицы каждого вида карамели приведены в таблице.
| Сырье | Расход сырья на 1 тонну карамели |
| A | B | C |
| Сахарный песок | 0,7 | 0,7 | 0,7 |
| Патока | 0,3 | 0,3 | 0,2 |
| Фруктовое пюре | 0 | 0,2 | 0,3 |
Требуется:
1). Составить математическую модель задачи (показатель эффективности - прибыль).
2). Определить план выпуска карамели, обеспечивающий максимальную прибыль (решить задачу двумя способами:
графическим и симплексным методом).
Найти план производства карамели, максимизирующий прибыль.
Вначале решим задачу симплексным методом линейного программирования.
Математическая модель задачи имеет следующий вид:
F=1000x1 + 1100x2 + 1200x3 (max)
0,7x1 + 0,7x2 + 0,7x3 <= 700
0,3x1 + 0,3x2 + 0,2x3 <=300
0,0x1 + 0,2x2 + 0,3x3 <=150
x1 >= 0 ; x2 >= 0 ; x3 >= 0 ;
Приведем задачу линейного программирования к каноническому виду и решим ее симплексным методом. Для этого введем
дополнительные переменные
x4 >= 0 ; x5 >= 0 ; x6 >= 0 такие, что система неравенств превратится в систему
равенств.
0,7x1 + 0,7x2 + 0,7x3 + x4 <= 700
0,3x1 + 0,3x2 + 0,2x3 + x5 <=300
0,0x1 + 0,2x2 + 0,3x3 + x6 <=150,
где x1 >= 0 ; x2 >= 0 ; x3 >= 0 ; x4 >= 0 ; x5 >= 0 ; x6 >= 0.
Линейная форма F(x1, x2, x3) примет следующий вид:
F = 1000x1 + 1100x2 + 1200x3 + 0x4 + 0x5 + 0x6.
На основании полученных соотношений составим первую симплексную таблицу.
| i |
Базис |
С базиса |
A0 |
1000 |
1100 |
1200 |
0 |
0 |
0 |
| A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
| 1 |
A4 |
0 |
700 |
7/10 |
7/10 |
7/10 |
1 |
0 |
0 |
| 2 |
A5 |
0 |
300 |
3/10 |
3/10 |
1/5 |
0 |
1 |
0 |
| 3 |
A6 |
0 |
150 |
0 |
1/5 |
3/10 |
0 |
0 |
1 |
| m + 1 |
Zj - Cj |
0 |
-1000 |
-1100 |
-1200 |
0 |
0 |
0 |
Выберем в этой таблице наибольшую по абсолютной величине отрицательную оценку Zj - Cj в
(m + 1) строке.
Это оценка - 1200, стоящая в столбце A3.
Найдем минимальное отношение элементов столбца A0 к положительным элементам выбранного столбца A3.
Этот столбец называют разрешающим.
min { 700/0,7; 300/0,2; 150/0,3 } = { 1000, 1500, 500 } = 150/0,3 = 500.
Итак, мы видим, что минимальное отношение есть отношение 150 к 0,3, то есть 0,3 - это разрешающий элемент
( его называют иногда ключевым или генеральным элементом, а соответствующую ему строку - разрешающей строкой).
Выполним симплексное преобразование таблицы с выбранным разрешающим элементом. Получим следующую таблицу:
| i |
Базис |
С базиса |
A0 |
1000 |
1100 |
1200 |
0 |
0 |
0 |
| A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
| 1 |
A4 |
0 |
350 |
7/10 |
7/30 |
0 |
1 |
0 |
-7/3 |
| 2 |
A5 |
0 |
200 |
3/10 |
1/6 |
0 |
0 |
1 |
-2/3 |
| 3 |
A3 |
1200 |
500 |
0 |
2/3 |
1 |
0 |
0 |
10/3 |
| m + 1 |
Zj - Cj |
600000 |
-1000 |
-300 |
0 |
0 |
0 |
4000 |
При этом разрешающий элемент становится равным 1, а все остальные элементы разрешающего столбца - нулями.
Элементы разрешающей строки делятся на разрешающий элемент a33=0,3. Остальные элементы матрицы
(таблицы) пересчитываются согласно алгоритму симплексного метода по правилу:
Новое aij = Старое aij - ( ai0j * aij0 ) / ai0j0,
где
Старое aij - число до пересчета
ai0j - элемент из разрешающей строки i0 и столбца j.
aij0 - элемент из разрешающего столбца j0 и строки i.
ai0j0 - разрешающий элемент.
Новое aij - число после пересчета.
Как следует из второй симплексной таблицы, оптимальное решение еще не получено, так как в строке оценок
Zj - Cj еще имеются отрицательные элементы. Выберем снова максимальное по абсолютной
величине значение оценки. Это будет число -1000 из первого столбца таблицы. Примем первый столбец за разрешающий
столбец и будем находить минимальное отношение неотрицательных элементов столбца A0 к положительным элементам
нового разрешающего столбца. Делается это для уточнения разрешающего элемента и разрешающей строки.
min ( 350/0,7; 200/0,3; } = { 500; 2000/3 } = 350/0,7 = 500. Таким образом, элемент a11 является новым
разрешающим элементом второй симплексной таблицы. Выполним симплексное преобразование таблицы с найденным разрешающим
элементом. В результате получим следующую симплексную таблицу:
| i |
Базис |
С базиса |
A0 |
1000 |
1100 |
1200 |
0 |
0 |
0 |
| A1 |
A2 |
A3 |
A4 |
A5 |
A6 |
| 1 |
A1 |
1000 |
500 |
1 |
1/3 |
0 |
10/7 |
0 |
-10/3 |
| 2 |
A5 |
0 |
50 |
0 |
1/15 |
0 |
-3/7 |
1 |
1/3 |
| 3 |
A3 |
1200 |
500 |
0 |
2/3 |
1 |
0 |
0 |
10/3 |
| m + 1 |
Zj - Cj |
1100000 |
0 |
100/3 |
0 |
10000/7 |
0 |
2000/3 |
Строка оценок Zj - Cj последней симплексной таблицы больше не содержит отрицательных чисел. Это свидетельствует о том,
что нами получено оптимальное решение задачи линейного программирования на максимум прибыли. Найдено оптимальное
решение x1=500, x2=0, x3=500, оптимизирующее получение прибыли при производстве
карамели. Прибыль составляет 1100000 рублей.
Климант Юрий Викторович,,
учитель информатики Краснодарской Муниципальной общеобразовательной средней школы 35
и средней школы 48
Страничка подготовлена, проверена и отредактирована 7 марта 2007 года.
Главный администратор сайта:
Климант Юрий Викторович.
| Назад |
| Содержание |
| Дальше |
