Этапы решения задачи ЛП геометрическим методом:
1. Построить граничные прямые,соответствующие данным ограничениям-неравенствам из системы (3.2).
2. Найти полуплоскости, определяемые каждым из ограничений системы (3.2).
3. Найти многоугольник решений.
4. Построить вектор 
.
5. Построить прямую 
, проходящую через многоугольник решений.
6. Передвинуть прямую 
в направлении вектора 
.
7. Определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.
Пример 3.1. Для изготовления двух видов изделий I и II используются три вида сырья. На производство единицы изделия I требуется затратить сырья первого вида 13 кг, сырья второго вида – 32 кг, сырья третьего вида – 58 кг. На производство единицы изделия II требуется затратить сырья первого вида 24 кг, сырья второго вида – 32 кг, сырья третьего вида – 29 кг. Производство обеспечено сырьем первого вида в количестве 312 кг, сырьем второго вида – 480 кг, сырьем третьего вида – 696 кг. Прибыль от реализации единицы готового изделия I вида составляет 4 усл. ед, а изделия II вида – 3 усл. ед.
Требуется составить план производства изделий I и II, обеспечивающий максимальную прибыль от их реализации, если заранее планируется изготовление не менее 10 единиц изделий I и II.
Решение: Для удобства оформим данные задачи в таблице.
| Вид сырья | Кол-во затрачиваемого сырья (кг) на единицу изделия | Общее кол-во сырья (кг) | |
| I | II | ||
| 1 | 13 | 24 | 312 |
| 2 | 32 | 32 | 480 |
| 3 | 58 | 29 | 696 |
| Прибыль (усл. ед) | 4 | 3 | |
|
|
|
Составим математическую модель задачи.
1. Введем переменные задачи:
х1 – количество изделий вида I, планируемых к выпуску;
x2 – количество изделий вида II, планируемых к выпуску.
2. Составим систему ограничений:
3. Зададим целевую функцию:
F(X) = 4x1 + 3x2 → max
Построим область допустимых решений задачи.
Для этого в прямоугольной декартовой системе координат построим прямую l1: 13x1+24x2=312, соответствующую ограничению (1). Для этого найдем координаты двух точек, принадлежащих данной прямой. Полагаем x1=0, тогда x2 = 13, возьмем x2 = 0, получаем x1=24. Получили координаты точек В (24, 0) и С (0, 13).
Определим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1). Для этого подставим, например, координаты точки О (0; 0), не лежащей на прямой l1, в данное ограничение:
13·0 + 24·0 ≤ 312. Получаем 0 ≤ 312, следовательно точка О лежит в полуплоскости решений. Укажем данную полуплоскость штриховкой (рис.1).
рис. 1
Аналогично строим прямую l2: 32x1+32x2 = 480, соответствующую ограничению (2) , находим полуплоскость решений. Отметим штриховкой общую часть полуплоскостей решений (рис. 2).
|
|
|
рис. 2
Строим прямую l3: 58x1 + 29x2 = 696, соответствующую ограничению (3), находим полуплоскость решений. Штриховкой обозначим общую часть полуплоскостей решений (рис. 3).
рис. 3
Построим прямую l4: x1+x2 = 10. Определим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (4). Для этого подставим, например, координаты точки О (0; 0), не лежащей на прямой l4, в данное ограничение.
Получаем 0 ≥ 10, следовательно точка О не принадлежит полуплоскости решений. Штрихуем ту часть плоскости относительно прямой, где не лежит точка О.
Далее находим общую часть полуплоскостей решений, учитывая при этом условия неотрицательности переменных. Полученную область допустимых решений отметим штриховкой (рис. 4).
рис. 4
Построим нормаль линий уровня 
и одну из линий, например 4x1 + 3x2 = 0.
Так как решается задача на нахождение максимума целевой функции, то линию уровня перемещаем в направлении нормали до последней точки многоугольника решений MCEGF (рис. 5).
рис. 5
Видим, что последней точкой данного прямоугольника будет точка G. В данной точке значение функции будет наибольшим.
|
|
|
Для нахождения координат точки G = l2 ∩ l3 необходимо решить систему уравнений 
Получим G(9, 6).
Находим F(G) = 4·9 + 3·6 = 54.
Ответ: Для получения максимальной прибыли 54 усл. ед, необходимо производить 9 изделий вида I и 6 изделий вида II.
Пример 3.2. Фирма по производству строительных материалов ООО «Вазелло» выпускает два вида стройматериалов: жидкое стекло и пенопласт. Трудозатраты на производство 1 т. стекла – 20 ч, пенопласта – 10 ч. В кооперативе работают 10 рабочих по 40 ч. в неделю. Оборудование позволяет производить не более 15 т. стекла и 30 т. пенопласта в неделю. Прибыль от реализации 1 т. жидкого стекла 50 тыс. руб.; 1 т. пенопласта – 40 тыс. руб. Сколько стройматериалов каждого вида следует выпускать кооперативу для получения максимальной прибыли?
Решение: Составим математическую модель задачи.
1. Введем переменные задачи:
х1 – объем производства жидкого стекла в неделю;
x2 – объем производства пенопласта в неделю.
2. Составим систему ограничений:
3. Зададим целевую функцию:
F(X) = 50x1 + 40x2 → max
Построим прямые 
соответствующие данным неравенствам.
Получаем область допустимых решений - пятиугольник AFGED (рис. 6).
|
|
|
рис. 6
Построим вектор 
. Затем линию уровня перемещаем в направлении нормали до последней точки многоугольника решений.
В нашем случае, касание линии уровня, перед выходом из области допустимых решений, произойдет в точке G = l1 ∩ l3. В данной точке значение функции будет наибольшим.
Найдем координаты точки G. Решив систему 
находим x1=5, x2=30, F(X) = 1450.
Ответ: производство 5 т. жидкого стекла и 30 т. пенопласта в неделю, обеспечивает ООО «Вазелло» максимальную прибыль, равную 1450000 рублей.
Пример 3.3. (о составлении рациона).
Фармацевтическая фирма «Ozark» ежедневно производит 800 фунтов некой пищевой добавки – смеси кукурузной и соевой муки, состав которой представлен в следующей таблице.
| Мука | Белок | Клетчатка | Стоимость (в долл. за фунт) |
| (в фунтах на фунт муки) | |||
| кукурузная | 0,09 | 0,02 | 0,30 |
| соевая | 0,60 | 0,06 | 0,90 |
Диетологи требуют, чтобы в пищевой добавке было не менее 30% белка и не более 5% клетчатки. Фирма «Ozark» хочет определить рецептуру смеси минимальной стоимости с учетом требований диетологов.
Решение. Составим математическую модель задачи.
1. Введем переменные задачи:
х1 – количество (в фунтах) кукурузной муки, используемой в производстве пищевой добавки;
x2 – количество (в фунтах) кукурузной муки, используемой в производстве пищевой добавки.
2. Составим систему ограничений.
Ограничение 
описывает то условие, что фирма должна выпускать не менее 800 фунтов в день.
Рассмотрим ограничение, связанное с количеством белка в пищевой добавке. Нам известно, что общее количество белка ( 
фунтов) должно составлять не менее 30% от общего объема смеси ( 
). Отсюда получаем следующее неравенство: 
.
Аналогично строится ограничение для клетчатки:
.
Окончательно система ограничений примет следующий вид:
3. Зададим целевую функцию:
F(X) = 0,3x1 + 0,9x2 → min.
Построим прямые
соответствующие данным неравенствам.
Получаем следующую область допустимых решений (рис. 7).
рис. 7
Для удобства построения построим вектор, коллинеарный вектору 
.
Затем линию уровня перемещаем в противоположном направлении нормали. В нашем случае, касание прямой, перед выходом из области допустимых решений, произойдет в точке С = l1 ∩ l2 . В данной точке значение функции будет наименьшим (рис 8).
рис. 8
Найдем координаты точки С.
Решив систему 
находим
.
Ответ: при 407,6 фунтах кукурузной муки и 329,4 фунтах соевой муки минимальная стоимость производимой ежедневно пищевой добавки составляет 437,6 долл.
Дата добавления: 2021-11-30; просмотров: 32; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!