Рацион питания животных на ферме состоит из двух видов кормов 1 и 2
Задача:
Рацион для питания
животных на ферме состоит из двух видов кормов 1 и 2.
Один килограмм корма 1
стоит 80 р. и содержит 1 ед. жиров, 3 ед. белков,
1 ед. углеводов, 2 ед.
нитратов. Один килограмм корма 2 стоит 10 р. и
содержит 3 ед. жиров, 1 ед.
белков, 8 ед. углеводов, 4 ед. нитратов.
Составить наиболее дешевый рацион
питания при условии, что:
Жиров …..……. не менее 6 ед.
Белков …..…….
не менее 9 ед.
Углеводов ..…. не менее 8 ед.
Математическая модель задачи:
Целевая функция:
S min = 80*x1+10*x2
Система
ограничений:
x1+3*x2>=6
3*x1+x2>=9
x1+8*x2>=8
2*x1+4*x2<=16
x1,x2 >=0; – условие неотрицательности переменных.
Решение задачи с использованием метода симплекс-таблиц.
Математическая модель задачи:
Целевая функция:
S min = 80*x1+10*x2
Система ограничений:
x1+3*x2>=6
3*x1+x2>=9
x1+8*x2>=8
2*x1+4*x2<=16
x1,x2, >=0; – условие неотрицательности переменных.
Система неравенств приведена к каноническому виду:
Целевая функция:
S min = 80*x1+10*x2+0*x3+0*x4+0*x5+0*x6
Система ограничений:
-1*x1-3*x2+x3=-6
-3*x1-1*x2+x4=-9
-1*x1-8*x2+x5=-8
2*x1+4*x2+x6=16
Векторный анализ системы ограничений:
Расширенная целевая функция:
S min = 80*x1+10*x2+0*x3+0*x4+0*x5+0*x6
Вектора:
| P0 | P1(x1) | P2(x2) | P3(x3) | P4(x4) | P5(x5) | P6(x6) |
|---|---|---|---|---|---|---|
| -6 | -1 | -3 | 1 | 0 | 0 | 0 |
| -9 | -3 | -1 | 0 | 1 | 0 | 0 |
| -8 | -1 | -8 | 0 | 0 | 1 | 0 |
| 16 | 2 | 4 | 0 | 0 | 0 | 1 |
Базис:
Базисный вектор №1: P3(x3)
Базисный вектор №2:
P4(x4)
Базисный вектор №3: P5(x5)
Базисный вектор №4: P6(x6)
Расширенная целевая функция:
S min = 80*x1+10*x2+0*x3+0*x4+0*x5+0*x6
Заполним первую таблицу:
Таблица №1
| № | Base | CBase | P0 | 80 | 10 | ||||
|---|---|---|---|---|---|---|---|---|---|
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| 1 | P3 | -6 | -1 | -3 | 1 | ||||
| 2 | P4 | -9 | -3 | -1 | 1 | ||||
| 3 | P5 | -8 | -1 | -8 | 1 | ||||
| 4 | P6 | 16 | 2 | 4 | 1 | ||||
| S min = | -80 | -10 | |||||||
Невозможно выбрать столбец замещения, так как
нет положительных dj!
Выберем столбец таким образом. Чтобы избавиться от
недопустимого решения, т.е. от отрицательных значений в столбце свободных членов
(Р0).
Замещаемый базисный вектор: P3 (1-я строка)
Новый базисный вектор:
P1 (1-й столбец)
Заменяем базисный вектор P3 на P1.
Таблица №2
| № | Base | CBase | P0 | 80 | 10 | ||||
|---|---|---|---|---|---|---|---|---|---|
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| 1 | P1 | 80 | 6 | 1 | 3 | -1 | |||
| 2 | P4 | 9 | 8 | -3 | 1 | ||||
| 3 | P5 | -2 | -5 | -1 | 1 | ||||
| 4 | P6 | 4 | -2 | 2 | 1 | ||||
| S min = | 480 | 230 | -80 | ||||||
Замещаемый базисный вектор: P5 (3-я строка)
Новый базисный вектор: P2 (2-й столбец)
Заменяем базисный вектор P5 на
P2.
Таблица №3
| № | Base | CBase | P0 | 80 | 10 | ||||
|---|---|---|---|---|---|---|---|---|---|
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| 1 | P1 | 80 | 4,8 | 1 | -1,6 | 0,6 | |||
| 2 | P4 | 5,8 | -4,6 | 1 | 1,6 | ||||
| 3 | P2 | 10 | 0,4 | 1 | 0,2 | -0,2 | |||
| 4 | P6 | 4,8 | 2,4 | -0,4 | 1 | ||||
| S min = | 388 | -126 | 46 | ||||||
Замещаемый базисный вектор: P4 (2-я строка)
Новый базисный вектор: P5 (5-й столбец)
Заменяем базисный вектор P4 на
P5.
Таблица №4
| № | Base | CBase | P0 | 80 | 10 | ||||
|---|---|---|---|---|---|---|---|---|---|
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| 1 | P1 | 80 | 2,625 | 1 | 0,125 | -0,375 | |||
| 2 | P5 | 3,625 | -2,875 | 0,625 | 1 | ||||
| 3 | P2 | 10 | 1,125 | 1 | -0,375 | 0,125 | |||
| 4 | P6 | 6,25 | 1,25 | 0,25 | 1 | ||||
| S min = | 221,25 | 6,25 | -28,75 | ||||||
Замещаемый базисный вектор: P6 (4-я строка)
Новый базисный вектор: P3 (3-й столбец)
Заменяем базисный вектор P6 на
P3.
Таблица №5
| № | Base | CBase | P0 | 80 | 10 | ||||
|---|---|---|---|---|---|---|---|---|---|
| P1 | P2 | P3 | P4 | P5 | P6 | ||||
| 1 | P1 | 80 | 2 | 1 | -0,4 | -0,1 | |||
| 2 | P5 | 18 | 1,2 | 1 | 2,3 | ||||
| 3 | P2 | 10 | 3 | 1 | 0,2 | 0,3 | |||
| 4 | P3 | 5 | 1 | 0,2 | 0,8 | ||||
| S min = | 190 | -30 | -5 | ||||||
Невозможно выбрать столбец замещения, так
как нет положительных dj!
Получено оптимальное решение!
Из таблицы получим значения переменных целевой функции:
| x1 | x2 | x3 | x4 | x5 | x6 |
|---|---|---|---|---|---|
| 2 | 3 | 5 | 18 |
Целевая функция:
S min = 80*2+10*3
И
в результате:
S min = 190;
Задача решена.
Источник
[Список тем]
[Вступление к этой теме] страницы темы:
[1]
[2]
Получение математической модели.
Математическая модель задачи линейного программирования включает:
- обозначение переменных
- условие неотрицательности переменных
- систему ограничений
- целевую функцию
Желательно уяснить какого вида задача перед Вами и
сколько переменных необходимо ввести.
Для формализации
задачи, заданной словестным описанием, надо обозначить
переменными xj
(или xij)
соответствующие величины, как правило те, о которых спрашивается в
задаче, и записать с помощью этих переменных систему ограничений и
целевую функцию.
В задачах 4 -7 составим
экономико-математические модели.
4. Для производства двух видов изделий
А и В
предприятие использует три вида сырья.
Другие условия задачи приведены в таблице.
| Вид сырья | Нормы расхода сырья на одно изделие, кг | Общее количество сырья, кг | |
| А | В | ||
| I | 12 | 4 | 300 |
| II | 4 | 4 | 120 |
| III | 3 | 12 | 252 |
| Прибыль от реализации одного изделия, ден.ед. | 30 | 40 | |
Составить такой план выпуска
продукции, при котором прибыль
предприятия от реализации
продукции будет максимальной при
условии, что изделий В надо
выпустить не менее, чем изделий A.
Решение.
В задаче спрашивается о плане выпуска продукции, значит
переменными следует обозначить
количества изделий типа А – х1
и типа В – х2.
Система ограничений по
количеству каждого вида сырья:
12х1+4х2 <= 300
4х1+4х2 <= 120
3х1+12х2 <= 252
х1<= х2 дополнительное
ограничение на количество изделий
х1, х2 >= 0 –
нельзя выпустить отрицательное количество изделий
Целевая функция
задачи: F = 30х1+40х2 ==> max
5. Рацион для питания
животных на ферме состоит из двух
видов кормов I и II. Один килограмм
корма I стоит 80 ден. ед. и содержит: 1
ед. жиров, 3 ед. белков, 1 ед.
углеводов, 2 ед. нитратов. Один
килограмм корма II стоит 10 ден. ед. и
содержит 3 ед. жиров, 1 ед. белков, 8 ед.
углеводов, 4 ед. нитратов.
Составить наиболее дешевый рацион
питания, обеспечивающий жиров не
менее 6 ед., белков не менее 9 ед.,
углеводов не менее 8 ед., нитратов не
более 16 ед.
Решение.
В задаче спрашивается об оптимальной смеси, значит
переменными следует обозначить количества корма I и II вида в смеси
х1 и х2 соответственно.
Система ограничений по
количеству питательных веществ:
х1+3х2 >= 6
3х1+х2 >= 9
х1+8х2 >= 8
2х1+4х2 <= 16
Целевая функция
задачи: Z = 80х1+10х2 ==> min
6. На двух
автоматических линиях выпускают
аппараты трех типов. Другие условия
задачи приведены в таблице.
| Тип аппарата | Производительность работы линий, шт. в сутки | Затраты на работу линий, ден. ед. в сутки | План, шт. | ||
| 1 | 2 | 1 | 2 | ||
| А | 4 | 3 | 400 | 300 | 50 |
| В | 6 | 5 | 100 | 200 | 40 |
| С | 8 | 2 | 300 | 400 | 50 |
Составить такой план загрузки
станков, чтобы затраты были
минимальными, а задание выполнено
не более чем за 10 суток.
Решение.
В задаче спрашивается о плане загрузки станков, значит
переменными следует обозначить время работы каждой линии над
выпуском каждого типа аппарата.
Всего переменных будет 6:
x1A- время работы первой
линии над выпуском автоматов типа А
x2A- время работы второй
линии над выпуском автоматов типа А
x1B- время работы первой
линии над выпуском автоматов типа B
x2B- время работы второй
линии над выпуском автоматов типа B
x1C- время работы первой
линии над выпуском автоматов типа С
x2C- время работы второй
линии над выпуском автоматов типа С
Ограничение по времени: каждая
линия работает не более 10 сут.
x1A + x1B+ x1С<= 10
x2A + x2B+ x2С<= 10
Ограничение по плановому заданию:
4x1A + 3×2А = 50
6x1B + 5x2B = 40
8x1C + 2×2С = 50
Целевая функция
задачи суммарные затраты:
Z = 400x1A+ 300×2А + 100x1B+
200x2B + 300x1C+ 400×2С ==> min
7. Необходимо распилить 20 бревен
длиной по 6м каждое на бруски по 2м
и 3м; при этом должно получиться
равное количество брусков каждого
размера.
Составить такой план распила, при
котором будет получено
максимальное число комплектов и
все бревна будут распилены (в один
комплект входит по одному бруску
каждого размера).
Решение.
В задаче спрашивается об оптимальном распиле т.е. сколько
бревен каким способом надо распилить.
Способов распила 3:
2 по 3м будет распилено x1бревен;
3 по 2м будет распилено x2бревен;
3м и 2м будет распилено x3бревен.
Ограничения:
x1 + x2 + x3
= 20 – распилены все бревна.
2×1 + x3 = 3×2 + x3
– в каждый комплект входит одинаковое число брусков каждого
вида т.е. их должно быть одинаковое количество.
F = 2х1 + х3 ==> max – количество комплектов должно
быть максимальным.
[Список тем]
[Вступление к этой теме] страницы темы:
[1]
[2]
[В начало страницы]
Источник
Вариант № 2.
Задача № 1. Решить графическим методом типовую задачу оптимизации.
Совхоз для кормления животных использует два вида корма. В дневном рационе животного должно содержаться не менее 6 единиц питательного вещества и не менее 12 единиц питательного вещества . Какое количество корма надо расходовать ежедневно на одного животного, чтобы затраты были минимальными? Использовать данные таблицы:
Построить экономико-математическую модель задачи, дать необходимые комментарии к ее элементам и получить решение графическим методом. Что произойдет, если решать задачу на максимум и почему?
Решение:
1. Введем переменные:
– количество корма 1;
– количество корма 2.
2. Зададим целевую функцию. Задача на минимизацию затрат. Запишем уравнение, описывающее затраты
3. Ограничения:
Найдем решение сформированной задачи, используя ее геометрическую интерпретацию. Сначала определим область допустимых решений. Для этого в неравенствах системы ограничений знаки неравенств заменим на знаки точных равенств, и найдем соответствующие прямые:
Выразим через
Для построения прямой достаточно двух точек, найдем их координаты:
Эти прямые изображены на рисунке 1. Условие неотрицательности показывает, что искомая область располагается в первой четверти.
Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять какую-нибудь точку, принадлежащую одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой принадлежит эта точка, в противном случае – другая полуплоскость.
Рисунок 1. Графический метод решения
На рисунке 1, область допустимых решений не ограничена и отмечена штрихом. Координаты любой точки, принадлежащей этой области, удовлетворяют данной системе неравенств и условию неотрицательности переменных. Поэтому сформулированная задача будет решена, если мы сможем найти точку, принадлежащую области допустимых решений, в которой целевая функция принимает минимальное значение. Чтобы найти указанную точку, построим вектор и линию уровня, которая перпендикулярна этому вектору.
Так как задача на минимум, то линию уровня будем двигать по направлению вектора. Первая точка касания и будет оптимальным решением. Координаты этой точки и определяют оптимальные количества кормов и , при которых ежедневные затраты на кормление одного животного являются минимальными.
В данном примере это точка пересечения прямых I и Следовательно, ее координаты удовлетворяют уравнениям этих прямых
Следовательно, если совхоз для кормления животных будет использовать 2 кг корма 1 и 2 кг корма 2, то минимальные затраты составят
Если данную задачу решать на максимум, то линия уровня будет сдвигаться вправо до бесконечности (так область решений не ограничена). Таким образом, конечного решения не будет.
Задача № 2. Предложить оптимальное управленческое решение в следующих типовых хозяйственных ситуациях.
В обработку поступили две партии досок для изготовления комплектов из трех деталей (треугольные каркасы настилов на стройплощадку), причем первая партия содержит 52 доски длиной по 6,5 м каждая, вторая содержит 200 досок длиной по 4 м каждая. Каждый комплект состоит из двух деталей по 2 м каждая и одной детали в 1,25 м.
Ставится задача поиска рационального варианта раскроя поступившего в обработку материала.
Решение:
Критерием оптимальности в данной задаче будет максимум выпуска комплектной продукции. Построим возможные способы раскроя исходного материала:
Введем необходимые обозначения: – число досок из партии , которое следует раскроить способом. Рассмотрим соотношения:
Обозначим через – минимальное из этих соотношений (это и будет количество комплектной продукции). Следовательно, экономико-математическая модель примет вид:
– Целые неотрицательные. Для удобства записи заменим двухиндексные переменные на одноиндексные переменные так как это показано в таблице раскроя Тогда ЭММ задачи примет вид:
При ограничениях:
Реализуя приведенную модель в любом пакете прикладных программ, получим решение:
Оптимальные значения остальных переменных равны нулю. Следовательно, в данной хозяйственной ситуации максимальное количество наборов, равное 215 шт. можно изготовить и реализовать, если:
– раскроить каждую из 15 досок длиной 6,5 м на 2 детали по 2 м и 2 детали по 1,25 м;
– раскроить каждую из 37 досок длиной 6,5 м на 5 деталей по 1,25 м;
– раскроить каждую из 200 досок длиной 4 м на 2 детали по 2 м. В этом случае будет получена максимальная выручка.
Задача № 3. Провести моделирование и решить специальную задачу линейного программирования.
Компания, занимающаяся ремонтом автомобильных дорог, в следующем месяце будет проводить ремонтные работы на пяти участках автодорог. Песок на участки ремонтных работ может доставляться из трех карьеров, месячные объемы предложений по карьерам известны. Из планов производства ремонтных работ известны месячные объемы потребностей по участкам работ. Имеются экономические оценки транспортных затрат (в у. е.) на перевозку 1тонны песка с карьеров на ремонтные участки.
Числовые данные для решения содержатся ниже в Матрице планирования. Требуется:
1) Предложить план перевозок песка на участки ремонта автодорог, который обеспечивает минимальные совокупные транспортные издержки.
2) Что произойдет с оптимальным планом, если изменятся условия перевозок: а) появится запрет на перевозки от первого карьера до второго участка работ?; б) по этой коммуникации будет ограничен объем перевозок 3 тоннами?
Матрица планирования:
Решение:
Суммарные объемы предложений по карьерам равны суммарным объемам потребностей по участкам работ, т. е. выполняется условие общего баланса Следовательно, данная задача закрытого типа.
Построим начальный базисный план Методом минимальной стоимости. Назначение перевозок начинаем с клетки (1,5), имеющей минимальную стоимость перевозки (1). В клетку (1,5) записываем наименьшее из значений и и исключаем из дальнейшего рассмотрения пятый участок. Корректируем предложение первого карьера на величину
Следующая поставка осуществляется от второго карьера третьему участку. В клетку (2,3) назначаем перевозку исключаем из дальнейшего рассмотрения третий участок. Корректируем предложение второго карьера С оставшейся матрицей поступаем аналогично предыдущему:
План перевозок, построенный методом минимальной стоимости:
Построенный начальный план перевозок является вырожденным, так как число назначенных перевозок меньше В одну из свободных клеток поставим ноль. Определим полную стоимость перевозок по найденному опорному плану:
Определим оптимальность полученного плана. С помощью Метода потенциалов вычислим потенциалы строк и столбцов по стоимости перевозок в загруженных клетках. Если известен , то если известен , то Положим, например, Тогда будут вычислены и остальные потенциалы строк и столбцов.
Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Начиная с клетки разметим вершины контура попеременно знаками плюс «+», минус «-», обходя замкнутый контур в любом направлении. Из клеток, помеченных знаком «-», выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 100 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».
Определим полную стоимость перевозок по новому плану
Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:
Полученный план не оптимален. Среди оценок имеется отрицательное значение. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план: на 0 увеличим перевозки в клетках, помеченных знаком «+», и уменьшим в клетках, помеченных знаком «-».
Определим полную стоимость перевозок по новому плану
Вычислим потенциалы и величины превышения стоимости для незагруженных клеток:
Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален.
Выясним, что произойдет с оптимальным планом, если появится запрет на перевозки от первого карьера до второго участка работ. В этом случае, будем считать, что транспортные затраты на перевозку от первого карьера до второго участка работ бесконечно большая . Составим начальный план методом минимальной стоимости в столбце.
Построенный начальный план перевозок является невырожденным, так как число назначенных перевозок равно Определим полную стоимость перевозок по найденному опорному плану:
Определим оптимальность полученного плана с помощью Метода потенциалов.
Для незагруженных клеток вычислим величины превышения стоимости
Характеристики свободных клеток не отрицательны, следовательно, текущий план оптимален. Таким образом, при запрете на перевозку с первого карьера на второй участок, транспортные расходы вырастут на
Выясним, что произойдет с оптимальным планом, если перевозка от первого карьера до второго участка работ будет ограничена объемом 3 тонны. Составим начальный план произвольным образом, учитывая данное ограничение.
Построенный начальный план перевозок является невырожденным, так как число базисных клеток (без ограничений на перевозку) равно Определим полную стоимость перевозок по найденному опорному плану:
Определим оптимальность полученного плана с помощью Метода потенциалов.
Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеются отрицательные значения. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план.
Определим полную стоимость перевозок по найденному опорному плану:
Для незагруженных клеток вычислим величины превышения стоимости
Полученный план не оптимален. Среди оценок имеются отрицательные значения. Потенциальной является клетка . От клетки строим замкнутый контур: Выбираем наименьшее значение объема перевозки Сформируем новый улучшенный план.
Определим полную стоимость перевозок по найденному опорному плану:
Для незагруженных клеток вычислим величины превышения стоимости
Характеристики свободных клеток не отрицательны (кроме клетки с ограничением), следовательно, текущий план оптимален. Таким образом, при ограничении на перевозку с первого карьера на второй участок тремя тоннами, транспортные расходы вырастут на
Задача № 4. Рассчитать характеристики системы массового обслуживания. Поток требований является простейшим (пуассоновским), а продолжительность обслуживания распределена по экспоненциальному закону.
На строительном участке в инструментальной мастерской работают 3 мастера. Если рабочий заходит в мастерскую, когда все мастера заняты обслуживанием ранее обратившихся работников, то он не уходит из мастерской и ожидает обслуживания. Статистика показала, что среднее число рабочих, обращающихся в мастерскую в течение часа, равно 4, среднее время, которое затрачивает мастер на заточку или ремонт инструмента, равно 10 мин. Рассчитайте основные характеристики работы данной мастерской как СМО с ожиданием.
Решение:
Имеем
Тогда интенсивность обслуживания равна
Интенсивность нагрузки равна
Поскольку
Очередь не растет безгранично и имеет смысл говорить о предельном стационарном режиме работы СМО. Находим вероятности состояний:
Число занятых каналов найдем, разделив абсолютную пропускную способность СМО на интенсивность обслуживания
Вероятность отсутствия очереди будет:
Среднее число рабочих в очереди:
Среднее число рабочих в мастерской:
Среднее время ожидания в очереди:
Среднее время пребывания рабочего в мастерской:
Источник