Использование линейного программирования для решения задач оптимизации
Курсовой проект - Экономика
Другие курсовые по предмету Экономика
?орое уравнения описывают количество сырья, которое необходимо вывезти с первого и второго складов, а третье и четвёртое - сколько нужно завести сырья на первый и второй заводы. К данной системе уравнений нужно добавить систему неравенств:
хi ? 0, где i = 1, . ., 4, (2)
которая означает, что сырьё обратно с заводов на склады не вывозится. Тогда общая стоимость перевозок с учётом приведённых в таблице расценок выразится формулой :
f = 7х1 + 9 х2 + 10 х3 + 8х 4. (3)
Таким образом, мы пришли к типичной задаче линейного программирования : найти оптимальные значения проектных параметров хi (i = 1, . ., 4), удовлетворяющим условиям (2), (3) и минимизирующим стоимость перевозок (3).
Из анализа системы уравнений (1) следует, что только первые два уравнения являются независимыми, а последние можно получить из них. Поэтому фактически имеем систему :
х1 + х2 = 60;
х3 + х4 = 80; (4)
х3 = 50 - х1;
х4 = 90 - х2.
Поскольку в соответствии с (2) все проектные параметры должны быть неотрицательны, то с учётом (4) получим следующую систему неравенств:
х1 ? 0, х2 ? 0, 50 - х1 ? 0, 90 - х2 ? 0.
Эти неравенства можно записать в более компактном виде :
0 ? х1 ? 50, 0 ? х2 ? 90. (5)
Данная система неравенств описывает все допустимые решения рассматриваемой задачи. Среди всех допустимых значений свободных параметров х1 и х2 нужно найти оптимальные, минимизирующие целевую функцию f. Формула (3) для неё с учётом соотношений (4) принимает вид
f = 7х1 + 9 х2 + 10(50 - х1) + 8(90 - х2);
f = -3х1 + х2 + 1220.
Отсюда следует, что стоимость перевозок уменьшается с увеличением значений х1; поэтому нужно взять его наибольшее допустимое значение. В соответствии с (5) х1= 50, тогда получим, что х2 = 60 - х1 = 10. Тогда оптимальные значения остальных параметров можно найти по формулам (4):
х3 = 50 - х1 =50 - 50 = 0, х4 = 90 - х2 = 90 - 10 = 80.
В этом случае минимальная общая стоимость перевозок равна :
f = 7*50 + 9*10 + 10*0 + 8*80 = 350 + 90 + 0 + 640 = 1080.
То есть, минимальная общая стоимость перевозок f = 1080.
Покажем на рисунке схему доставки сырья на заводы. (Числа указывают количество сырья в тоннах).
2.2 Решение производственной задачи
Для производства двух видов изделий А и В предприятие использует три вида сырья. Другие условия задачи приведены в таблице.
Вид сырьяНормы расхода сырья на одно изделие, кг A BОбщее количество сырья, кгI2 4300II4 4120III1 2 252Прибыль от реализации одного изделия, ден. ед. 30 40
Составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной при условии, что изделие В надо выпустить не менее, чем изделия А.
Решение.
Обозначим через х1 и х2 количество единиц продукции соответственно А и В, запланированных к производству. Для их изготовления потребуется (12 х1 +4 х2) единиц ресурса I, (4х1 +4х2) единиц ресурса II, (3х1 +12х2) единиц ресурса III. Так кА потребление ресурсов I, II, III не должно превышать их запасов, то связь между потреблением ресурсов и их запасами выразится системой неравенств:
12х1 +4х2 ? 300; 3х1 + х2 ? 75;
4х1 +4х2 ? 120; или х1 + х2 ? 30; (6)
3х1 +12х2 ? 252. х1 +4х2 ? 84.
По смыслу задачи переменные х1 ? 0, х2 ? 0. (7)
Суммарная прибыль А составит 30х1 от реализации продукции А и 40х 2 от реализации продукции В, то есть : F = 30х1 +40х 2 (8)
Далее будем решать задачу двумя методами:
1способ - симплексный метод
С помощью дополнительных неотрицательных переменных перейдём к системе уравнений. В данном случае все дополнительные переменные вводятся со знаком + , так как все неравенства имеют вид ? .
Получим систему ограничений в виде :
31 +х2 + х3 ? 75;
х1 +х2 + х4 ? 30; (9)
х1 + 4х2 + х5 ? 84.
Для нахождения первоначального базисного решения разобьём переменные на две группы - основные и не основные. Так как определитель, составленный из коэффициентов при дополнительных переменных х3, х4, х5 отличен от нуля, то эти переменные можно взять в качестве основных на первом шаге решения задачи.
I шаг.
Основные переменные: х3, х4, х5.
Не основные переменные: х1, х2. .
Выразим основные переменные через не основные :
х3 = 75 - 3х1 - х2 ;
х4 = 30 х1 - х2; (10)
х5 = 84 - х1 - 4х2.
Положив основные переменные равными нулю, то есть х1 = 0, х2 = 0, получим базисное решение Х1 = (0, 0, 75, 30, 84), которое является допустимым. Поскольку это решение допустимо, то нельзя отбросить возможность того, что оно оптимально. Выразим линейную функцию через не основные переменные:
F = 30х1 + 40х2 .
При решении Х1 значение функции равно F(Х1). Легко понять, что функцию F можно увеличить за счёт увеличения любой из не основных переменных, входящих в выражение F с положительным коэффициентом. Это можно осуществить, перейдя к новому базисному решению, в котором эта переменная будет не основной, то есть принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдёт в не основные. В данном примере для увеличения F можно переводить в основные любую переменную, так как и х1 и х2 входят в выражение для F со знаком +. Для определённости будем выбирать переменную, имеющую больший коэффициент, то есть х2. Система (10) накладывает ограничения на рост переменной х2 . Поскольку необходимо сохранять допустимость решений, то есть все переменн