⇢ Какой это метод решения задач линейного программирования?
Найти оптимальное сочетание посевов пшеницы и сахарной свеклы, обеспечивающий максимум прибыли. Под эти культуры хозяйство выделило ресурсы 1000 га пашни, 18000 чел. - дней труда, 3000 ц минеральных удобрений. В таблице 2.1 представлены исходные показатели.
Исходные показатели
ПоказателиПшеницаСахарная свекла
Труд, чел. -дней
Минеральное удобрение, ц
Прибыль, тыс. руб. 7
2
15040
9
300
Решение.
Переменные:
Х1 – площадь под пшеницу, га;
Х2 – площадь под сахарную свеклу, га.
Ограничения:
1. По площади пашни, га
X1 +Х2 ≤ 1000,
2. По затратам труда, чел. -дней
7Х1 +40Х2 ≤ 18000;
3. По использованию минеральных удобрений, ц
2Х1 +9Х2 ≤ 3000;
Z (мах прибыли, руб. ) =150Х1 +300Х2 → max.
Решение задачи
Предварительный шаг. Приведем к каноническому виду:
7х1 +40х2 +х3 =18000,
2х1 +9х2 +х4 =3000,
х1 +х2+х5 =1000.
Х1, Х2 0,
Z =150х1 +300х2+ 0х3 +0х4 +0х5 → max.
Интерация 1.
Шаг1. Выписываем исходное допустимое базисное решение и соответствующее ему значение целевой функции.
х3, х4, х5 – базисные переменные.
х1 х2 х3 х4 х5
Х = 0 0 18000 3000 1000
Z = 150•0+300•0+0•18000+0•300+0•1000 = 0.
Шаг2. Проверяем оптимальность полученного решения. Если решение не оптимально, то переходим к шагу 3. В противном случае записываем ответ.
Пусть ∆ х1 =1, тогда ∆ х3 =-7, ∆ х4 =-2, ∆ Х5 =-1
∆Z=150•1+300•0+0•(-7)+0•(-2)+0•(-1)=150. Так как ∆Z 0, то переменную х1 целесообразно ввести в базис.
Шаг3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.
х3 0 х3 =18000 - 7х1, 18000 - 7х1 0, х1 257,1,
х4 0 х4 =300 - 2х1, 300-2х1 0, х1 1500,
х5 0 х5 =100 – х1, 100 – х1 0, х1 100.
Решением системы неравенств является третье неравенство, поэтому из базиса выводим переменную х5.
Шаг 4. Пересчитываем систему уравнений задачи с учетом нового состава базисных переменных.
3 уравнение х1 +х2+х5 =1000,
1 уравнение _7х1 +40х2 +х3 =18000
7х1 +7х2+7х5 =7000
33х2 +х3 - 7х5 =11000,
2 уравнение _2х1 +9х2 +х4 =3000
2х1 +2х2+2х5 =2000
7х2+х4 - 2х5 = 1000.
В результате имеем следующую систему уравнений:
33х2 +х3 - 7х5 = 11000,
7х2+х4 - 2х5 = 1000,
х1 +х2+х5 =1000.
Итерация 2.
Шаг1. Выписываем исходное допустимое базисное решение.
х3, х4, х1 – базисные переменные.
х1 х2 х3 х4 х5
Х = 1000 0 11000 1000 0
Z=150•1000+300•0+0•11000+0•1000+0•0=150000
Шаг2. Проверяем оптимальность полученного решения.
Пусть ∆ х2 =1, тогда ∆ х3 =-33, ∆ х4 = -7, ∆ Х5 = -1
∆Z=150•(-1)+300•1+0•(-33)+0•(-7)+0•0=150. Так как ∆Z 0, то переменную х2 целесообразно ввести в базис.
Шаг 3. Определяем, какая из прежних базисных переменных должна быть выведена из базиса.
х3 0 х3 =11000 - 33х2, 11000 – 33х2 0, х2 333,3,
х4 0 х4 =1000 - 7х2, 1000 -7х2 0, х2 142,9,
х1 0 х1 =1000 – х2, 1000 – х2 0, х2 1000.
Переменную х4 выводим из базиса.
Шаг4. Пересчитываем систему уравнений задачи с учетом нового состава базисных переменных.
2 уравнение 7х2+х4 - 2х5 = 1000,
х2+1/7х4 – 2/7х5 = 1000/7,
3 уравнение _х1 +х2+х5 =1000
х2+1/7х4 – 2/7х5 = 1000/7
х1- 1/7х4 +9/7х5 = 857,4,
1 уравнение _33х2 +х3 - 7х5 = 11000
33х2+33/7х4 – 66/7х5 = 33000/7
х3 – 67,15х4 + 2,42х5 = 6285,7.
В результате имеем следующую систему уравнений:
х3 – 67,15х4 + 2,42х5 = 1571,5,
х2+1/7х4 – 2/7х5 = 1000/7,
х1- 1/7х4 +9/7х5 = 6285,7.
Итерация 3.
Шаг1. Выписываем исходное допустимое базисное решение.
х3, х2, х1 – базисные переменные.
(далее есть продолжение)