|
|
Задача линейного программирования
Решаем задачи по линейному программированию. Быстро, качественно и недорого. Решение, по Вашему желанию, оформляется в Word. Задачи решают специалисты высокого уровня - кандидаты и доктора физико-математических наук. Гарантия качества и правильности.
Задачи присылайте по электронной почте:
E-MAIL: 
Ниже приведён пример решения задачи линейного программирования.
Завод ремонтирует тракторы двух типов: первого - мощностью 300 л.с. и второго – мощностью 200 л.с.. За месяц завод может отремонтировать не более 15о тракторов. За ремонт трактора 1 типа завод получает чистой прибыли 1 млн. рублей, а за ремонт 2 типа 2 млн. рублей. Составить месячный план ремонта тракторов, при котором завод получит не менее 240 млн рублей прибыли и суммарная мощность отремонтированных тракторов будет наибольшей, если надо отремонтировать не менее 50 тракторов 1 типа.
Решение
Обозначим через x1, x2 количество тракторов первого и второго типа. Тогда приходим к следующей задаче, которая решается как прямая задача линейного программирования симплекс-методом.
Определить максимальное значение целевой функции
F(X) = 300 x1 + 200 x2
при следующих условиях-ограничениях:
x1 + x2 < 150
x1 + 2 x2 > 240
x1>50
x2 >0
Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных (переход к канонической форме).
В 1-м неравенстве смысла ( < ) вводим базисную переменную x3 . В 2-м неравенстве смысла ( > ) вводим базисную переменную x4 со знаком минус. В 3-м неравенстве смысла ( > ) вводим базисную переменную x5 со знаком минус. В 4-м неравенстве смысла ( > ) вводим базисную переменную x6 со знаком минус.
1 x1 + 1 x2 + 1 x3 + 0 x4 + 0 x5 + 0 x6 = 150
1 x1 + 2 x2 + 0 x3-1 x4 + 0 x5 + 0 x6 = 240
1 x1 + 0 x2 + 0 x3 + 0 x4-1 x5 + 0 x6 = 50
0 x1 + 1 x2 + 0 x3 + 0 x4 + 0 x5-1 x6 = 0
Введем искусственные переменные x: в 2-м равенстве вводим переменную x7; в 3-м равенстве вводим переменную x8; в 4-м равенстве вводим переменную x9;
1 x1 + 1 x2 + 1 x3 + 0 x4 + 0 x5 + 0 x6 + 0 x7 + 0 x8 + 0 x9 = 150
1 x1 + 2 x2 + 0 x3-1 x4 + 0 x5 + 0 x6 + 1 x7 + 0 x8 + 0 x9 = 240
1 x1 + 0 x2 + 0 x3 + 0 x4-1 x5 + 0 x6 + 0 x7 + 1 x8 + 0 x9 = 50
0 x1 + 1 x2 + 0 x3 + 0 x4 + 0 x5-1 x6 + 0 x7 + 0 x8 + 1 x9 = 0
Для постановки задачи на максимум целевую функцию запишем так:
F(X) = - M x7 - M x8 - M x9 — > max
Полученный базис называется искусственным, а метод решения называется методом искусственного базиса. Причем искусственные переменные не имеют отношения к содержанию поставленной задачи, однако они позволяют построить стартовую точку, а процесс оптимизации вынуждает эти переменные принимать нулевые значения и обеспечить допустимость оптимального решения. Из уравнений выражаем искусственные переменные:
x7 = 240- x1-2 x2 + x4
x8 = 50- x1+ x5
x9 = 0- x2 + x6
которые подставим в целевую функцию:
F(X) = - M(240- x1-2 x2 + x4) - M(50- x1+ x5) - M(0- x2+ x6) — > max
или
F(X) = (2M) x1+(3M) x2 +(-M) x4+(-M) x5+(-M) x6+(-290M) — > max
Введем новую переменную
x0 = 2 x1 + 3 x2 .
Выразим базисные переменные <3, 7, 8, 9> через небазисные.
x0 = -290+2 x1+3 x2 - x4- x5- x6
x3 = 150- x1- x2
x7 = 240- x1-2 x2 + x4
x8 = 50- x1+ x5
x9 = 0- x2 + x6
Переходим к основному алгоритму симплекс-метода.
Поскольку задача решается на максимум, то переменную для включения в текущий план выбирают по максимальному положительному числу в уравнении для x0.
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
max(2,3,0,-1,-1,-1,0,0,0) = 3
x0 = -290+2 x1+3 x2 - x4- x5- x6
x3 = 150- x1- x2
x7 = 240- x1-2 x2 + x4
x8 = 50- x1+ x5
x9 = 0- x2 + x6
В качестве новой переменной выбираем x2.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai2 и из них выберем наименьшее:
min (150 : 1 , 240 : 2 , - , 0 : 1 ) = 0.
Вместо переменной x9 в план войдет переменная x2.
4. Пересчет всех уравнений.
Выразим переменную x2 через x9
x2 = 0+ x6- x9
и подставим во все выражения.
x0 = -290+2 x1+3(0+ x6- x9)- x4- x5- x6
x3 = 150- x1-(0+ x6- x9)
x7 = 240- x1-2(0+ x6- x9)+ x4
x8 = 50- x1+ x5
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -290+2 x1- x4- x5+2 x6-3 x9
x3 = 150- x1- x6+ x9
x7 = 240- x1+ x4-2 x6+2 x9
x8 = 50- x1+ x5
x2 = 0+ x6- x9
Полагая небазисные переменные x = (3, 7, 8, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-2, 0, 0, 1, 1, -2, 0, 0, 3), x0 = -290
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
max(2,0,0,-1,-1,2,0,0,-3) = 2
x0 = -290+2 x1- x4- x5+2 x6-3 x9
x3 = 150- x1- x6+ x9
x7 = 240- x1+ x4-2 x6+2 x9
x8 = 50- x1+ x5
x2 = 0+ x6- x9
В качестве новой переменной выбираем x6.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai6
и из них выберем наименьшее:
min (150 : 1 , 240 : 2 , - , - ) = 120
Вместо переменной x7 в план войдет переменная x6.
4. Пересчет всех уравнений.
Выразим переменную x6 через x7
x6 = 120- ½ x1+ ½x4- ½x7+ x9
и подставим во все выражения.
x0 = -290+2 x1- x4- x5+2(120- ½ x1+ ½ x4- ½ x7+ x9)-3 x9
x3 = 150- x1-(120- ½ x1+ ½ x4 - ½ x7+ x9)+ x9
x8 = 50- x1+ x5
x2 = 0+(120 - ½ x1+ ½ x4 - ½ x7+ x9)- x9
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = -50+ x1- x5- x7- x9
x3 = 30- ½ x1 - ½ x4 + ½ x7
x6 = 120 - ½ x1 + ½ x4 - ½ x7+ x9
x8 = 50 - x1+ x5
x2 = 120 - ½ x1 + ½ x4 - ½ x7
Полагая небазисные переменные x = (3, 6, 8, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (-1, 0, 0, 0, 1, 0, 1, 0, 1), x0 = -50
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
max(1,0,0,0,-1,0,-1,0,-1) = 1
x0 = -50+ x1- x5- x7- x9
x3 = 30 - ½ x1 - ½ x4 + ½ x7
x6 = 120 - ½ x1+ ½ x4 - ½ x7+ x9
x8 = 50- x1+ x5
x2 = 120 - ½ x1 + ½ x4 - ½ x7
В качестве новой переменной выбираем x1.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai1
и из них выберем наименьшее:
min (30 : ½, 120 : ½ , 50 : 1 , 120 : ½ ) = 50
Вместо переменной x8 в план войдет переменная x1.
4. Пересчет всех уравнений.
Выразим переменную x1 через x8
x1 = 50+ x5- x8
и подставим во все выражения.
x0 = -50+(50+ x5- x8)- x5- x7- x9
x3 = 30- ½(50+ x5- x8) - ½ x4 + ½ x7
x6 = 120 - ½ (50+ x5 - x8) + ½ x4 - ½ x7+ x9
x2 = 120 - ½(50+ x5- x8) + ½ x4 - ½ x7
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 0- x7- x8- x9
x3 = 5 - ½ x4 - ½ x5 + ½ x7 + ½ x8
x6 = 95 + ½ x4 - ½ x5 - ½ x7 + ½ x8+ x9
x1 = 50+ x5- x8
x2 = 95 + ½ x4 - ½ x5 - ½ x7 + ½ x8
Полагая небазисные переменные x = (3, 6, 1, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 0, 0, 0, 0, 1, 1, 1), x0 = 0
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
x0 = 0- x7- x8- x9
x3 = 5 - ½ x4 - ½ x5 + ½ x7 + ½ x8
x6 = 95 + ½ x4 - ½ x5 - ½ x7 + ½ x8+ x9
x1 = 50+ x5- x8
x2 = 95 + ½ x4 - ½ x5 - ½ x7 + ½ x8
На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.
x3 = 5 - ½ x4 - ½ x5
x6 = 95 + ½ x4 - ½ x5
x1 = 50+ x5
x2 = 95 + ½ x4 - ½ x5
Выразим базисные переменные:
x1 = 50+ x5
x2 = 95 + ½ x4 - ½ x5
которые подставим в целевую функцию:
F(X) = 300(50+ x5) + 200(95 + ½ x4 - ½ x5)
или
F(X) = 34000+100 x4+200 x5
Получаем новую систему переменных.
x0 = 34000+100 x4+200 x5
x3 = 5 - ½ x4 - ½ x5
x6 = 95 + ½ x4 - ½ x5
x1 = 50+ x5
x2 = 95 + ½ x4 - ½ x5
1. Проверка критерия оптимальности.
В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален.
2. Определение новой базисной переменной.
max(0,0,0,100,200,0) = 200
x0 = 34000+100 x4+200 x5
x3 = 5 - ½ x4 - ½ x5
x6 = 95 + ½ x4 - ½ x5
x1 = 50+ x5
x2 = 95 + ½ x4 - ½ x5
В качестве новой переменной выбираем x4.
3. Определение новой свободной переменной.
Вычислим значения Di по всем уравнениям для этой переменной: bi / ai5
и из них выберем наименьшее:
min (5 : ½ , 95 : ½ , - , 95 : ½ ) = 10
Вместо переменной x3 в план войдет переменная x5.
4. Пересчет всех уравнений.
Выразим переменную x5 через x3
x5 = 10-2 x3- x4
и подставим во все выражения.
x0 = 34000+100 x4+200(10-2 x3- x4)
x6 = 95 + ½ x4 - ½ (10-2 x3- x4)
x1 = 50+(10-2 x3- x4)
x2 = 95 + ½ x4 - ½ (10-2 x3- x4)
После приведения всех подобных, получаем новую систему, эквивалентную прежней:
x0 = 36000-400 x3-100 x4
x5 = 10-2 x3- x4
x6 = 90+ x3+ x4
x1 = 60-2 x3- x4
x2 = 90+ x3+ x4
Полагая небазисные переменные x = (5, 6, 1, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:
x = (0, 0, 400, 100, 0, 0), x0 = 36000
Выражение для x0 не содержит положительных элементов. Найден оптимальный план.
Окончательный вариант системы уравнений:
x0 = 36000-400 x3-100 x4
x5 = 10-2 x3- x4
x6 = 90+ x3+ x4
x1 = 60-2 x3- x4
x2 = 90+ x3+ x4
Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым.
Оптимальный план можно записать так:
x1 = 60,
x2 = 90,
F(X) = 300•60 + 200•90 = 36000.
Задача линейного программирования решена.
|
|
|