- •Введение Математическое моделирование
- •Лабораторная работа №1 Графический (геометрический) способ определения оптимального плана
- •Лабораторная работа №2 Симплексный метод определения оптимального плана
- •Получение целочисленных решений при решении оптимизационных задач.
- •Лабораторная работа №3 Симплексный метод определения оптимального состава, оптимального плана использования и оптимального доукомплектования машинно-тракторного парка.
- •3.1 Модель оптимального состава машинно-тракторного парка (мтп)
- •3.2 Модель оптимального использования мтп
- •3.3 Модель оптимального доукомплектования мтп.
Получение целочисленных решений при решении оптимизационных задач.
Метод Гомори.
Значительная часть задач хозяйственной и коммерческой деятельности требует целочисленного решения, например, выпуск и распределение товаров, использование агрегатов при загрузке оборудования и т.д. Как быть, если симплекс-метод дает при оптимальном решении дробные значения основных переменных? В этом случае идет поиск наиболее близкого к оптимальному целочисленного решения. Применяются различные методики: 1) отсечения, 2) комбинированные, 3) приближенные. К числу первых относится известный метод Гомори.
Суть метода Гомори состоит в том, что сначала задача оптимизации решается непосредственно, без учета каким будет конечный результат. Если решение получено целочисленное, то задача решена, если нет, то вводится дополнительное ограничение, которое отвечает следующим критериям: 1)оно должно быть линейным, 2)должно отсекать найденный оптимальный нецелочисленный план, 3)не должно отсекать ни один целочисленный план. Такое дополнительное ограничение называется правильным отсечением. Для составления дополнительного ограничения выбирается элемент Xm с наибольшей дробной частью и составляется ограничение вида:
Qi – Qi1X1 – Qi2X2…- QimXm (11)
где Qi=bi – [bi], Qij=aij –[aij], при этом [bi] и [aij] целые числа, меньшие bi и aij, но наиболее близкие к ним. Неравенство (11) преобразуется в уравнение путем введения дополнительной неотрицательной переменной и включается в оптимальную симплексную таблицу. Полученная расширенная задача далее решается симплексным методом. Если в процессе решения в симплексной таблице появится уравнение с нецелым свободным членом bi и целыми коэффициентами aij, то данная задача не имеет целочисленного оптимального решения.
Пример №6.
Маркетинговые исследования указали на необходимость выпуска новой продукции, поэтому на предприятии решено установить новое технологическое оборудование на свободной площади 20кв.м. На приобретение оборудования двух видов выделено 6млн.руб. Комплект типа А стоимостью 1млн.руб. устанавливается на 5кв.м и позволяет увеличить доход предприятия на 8млн.руб. Комплект типа В занимает 2кв.м, стоит 1млн.руб. и обеспечивает доход в 5млн.руб. Определить, какое оборудование следует закупить, чтобы обеспечить максимальный доход предприятия?
Обозначив через Х1 и Х2 количество комплектов оборудования типа А и В, целевую функцию доходности выразим как Z(X) = 8X1+ 5X2. Найдем максимум целевой функции при ограничениях
5Х1+ 2Х2,
Х1+ Х2, где Х1, Х2 - целые числа.
Вводим новые базисные переменные Х3, Х4 и получаем нулевой опорный план:
5Х1+ 2Х2 + Х 3 =,
Х1+ Х2+ Х4 =6.
Х=(0, 0, 20, 6), который вносим в симплексную таблицу:
План |
Базис |
Ci/Cj |
Значения Xi |
X1 |
X2 |
X3 |
Х4 |
Qmin | ||||||||||
0
|
X3 |
0 |
20 |
5 |
2 |
1 |
0 |
20/5=4 | ||||||||||
Х4 |
0 |
6 |
1 |
1 |
0 |
1 |
6/1=6 | |||||||||||
Z(X) = 0 |
-8 |
-5 |
0 |
0 |
Индексная строка | |||||||||||||
1 |
→X1 |
8 |
4 |
1 |
0,4 |
0,2 |
0 |
4/0,4=10 | ||||||||||
Х4 |
0 |
2 |
0 |
0,6 |
-0,2 |
1 |
2/0,6=10/3 | |||||||||||
Z(X) = 8*4=32 |
0 |
- 1,8 |
1,6 |
0 |
Индексная строка | |||||||||||||
2 |
Х1 |
8 |
8/3 |
1 |
0 |
1/3 |
-2/3 |
- | ||||||||||
→X2 |
5 |
10/3 |
0 |
1 |
-1/3 |
5/3 |
- | |||||||||||
Z(X) =8*8/3+5*10/3=114/3 |
0 |
0 |
1 |
3 |
Индексная строка |
Оптимальный план Х=(8/3, 10/3, 0, 0) включает дробные значения основных переменных, поэтому по методу Гомори выбираем Х1 с наибольшей дробной частью 2/3 (у Х2 дробная часть 1/3) и составляем дополнительное ограничение:
Q1 – Q11X1 – Q12X2 – Q13X3 – Q14X4,
где Q1=b1 – [b1]= 8/3 -2=2/3, Q11=a11 –[a11]= 1-1=0, Q12=a12 –[a12]= 0-0=0,
Q13=a13 –[a13 ]=1/3 – 0=1/3, Q14=a14 –[a14]= -2/3 +1=1/3.
Дополнительное ограничение имеет вид: 2/3 – 0 – 0 -1/3Х3 – 1/3Х4 Вводим новую переменную Х5, и преобразуем полученное неравенство в уравнение: 2/3 – 1/3Х3 – 1/3Х4+ Х5=0,
коэффициенты которого введем дополнительной строкой в оптимальную симплексную таблицу и проведем дополнительную итерацию.
План |
Базис |
Ci/Cj |
Значения Xi |
X1 |
X2 |
X3 |
Х4 |
Qmin | ||||||||||||
0 |
X1 |
8 |
8/3 |
1 |
0 |
1/3 |
-2/3 |
8 | ||||||||||||
Х2 |
5 |
10/3 |
0 |
1 |
-1/3 |
5/3 |
10 | |||||||||||||
|
Х5 |
0 |
-2/3 |
0 |
0 |
-1/3 |
-1/3 |
2 | ||||||||||||
Z(X) = 114/3 |
0 |
0 |
1 |
3 |
Индексная строка | |||||||||||||||
1 |
X1 |
8 |
2 |
1 |
0 |
0 |
-1 |
| ||||||||||||
Х2 |
5 |
4 |
0 |
1 |
0 |
2 |
| |||||||||||||
→X3 |
0 |
2 |
0 |
0 |
1 |
1 |
| |||||||||||||
Z(X) = 2*8+4*5=36 |
0 |
0 |
0 |
2 |
Индексная строка |
Полученный целочисленный план является наиболее близким к плану с максимальным доходом. При этом остаток первого ресурса составляет 20-(2*5+4*2)=2кв. м, а деньги израсходованы полностью.
Варианты заданий к лабораторной работе №2.
Составить математическую модель производственной задачи и решить ее симплексным методом. Проанализировать полученные результаты и проверить их, используя программу «Симплекс-метод».
2.1. Для грузовых перевозок создается автоколонна. На покупку автомашин выделено 600 тыс.у.е. Можно заказать автомашины марок А,В и С, основные технические и производственные характеристики которых приведены в таблице:
Марка автомашины |
Материально-технические характеристики |
Производительность машины (т/км) | |||
Стоимость единицы (тыс.у.е.) |
Число водителей в смену |
Число рабочих смен в сутки | |||
А |
10 |
1 |
3 |
21 | |
В |
20 |
2 |
3 |
36 | |
С |
23 |
2 |
3 |
37,8 |
Количество автомашин в колонне не более 30, общее число водителей не более 144 , при этом каждая машина работает три смены, а водитель одну смену в сутки. Сколько автомашин марок А, В, С надо заказать, чтобы производительность колонны была максимальной?
2.2.Для изготовления обуви имеется три вида кожи в количествах: 500, 350 и 200 дм2 соответственно. Для пошива мужских ботинок требуется 2дм2 кожи первого вида и 2дм2 кожи второго вида, для пошива женских туфель – 2,1,1 дм2 кожи каждого вида. Доход от продажи пары мужской обуви составляет 40 руб., женской - 80 руб. Сколько пар ботинок и сапожек необходимо выпускать для получения максимальной прибыли?
2.3. Мебельный цех выпускает три вида изделий: шкафы ( А), буфеты (В) и диваны (С), расходы ресурсов (в тыс.руб.) на изготовление единицы каждого из них приведены в таблице:
Вид ресурса |
Материальные затраты на производство одного изделия | ||
Изделие А |
Изделие В |
Изделие С | |
Оборудование |
2 |
3 |
4 |
Сырье |
1 |
4 |
5 |
Электроэнергия |
3 |
4 |
2 |
Доход при реализации (тыс.руб.) |
8 |
7 |
6 |
Суточные запасы ресурсов составляют для оборудования 780 тыс. руб., для сырья – 850 тыс.руб., для электроэнергии 780 тыс.руб. Какой объем суточного производства изделий каждого вида обеспечит максимальную стоимость выпускаемой продукции ?
2.4. Показатели эффективности возделывания (в расчете на 1 га) трех культур: пшеницы, гречихи и картофеля, приведены в таблице:
Показатели |
Посевные культуры (1га) | ||
Пшеница |
Гречиха |
Картофель | |
Урожайность (ц) |
20 |
10 |
100 |
Затраты труда механизаторов (чел.-дней) |
0,5 |
1 |
5 |
Затраты конно-ручного труда (чел.-дней) |
0,5 |
0,5 |
20 |
Прибыль от реализации 1ц |
4 |
10 |
3 |
Основные производственные ресурсы хозяйства включают площадь пашни – 600га, затраты труда механизаторов – 500 чел.-дней, затраты конно-ручного труда – 900 чел.-дней. Найти оптимальное сочетание посевов пшеницы, гречихи и картофеля.
2.5.На двух участках различного плодородия высевают пшеницу и кукурузу. Площадь первого участка 100га, второго - 200га. Урожайность пшеницы на первом поле - 20ц/га, на втором поле 15 ц /га, у кукурузы 40 ц /га и 30ц /га соответственно. План по сбору пшеницы для хозяйства -1500ц, по кукурузе -4500ц. Найти оптимальный план посева, если доход от продажи 1ц пшеницы 6 долларов, а 1ц кукурузы - 4 доллара, а оба участка должны быть засеяны полностью.
2.6. Предприятие занимается выпуском пиццы. Нормы затрат на производство разных видов пиццы и стоимость приведены в Таблице. Запас продуктов на сутки составляет: грибов -20кг, колбасы -18кг, теста -25кг. Найти оптимальный объем выпуска разных видов пиццы, при котором доход предприятия максимален. При этом тесто, как скоропортящийся продукт, должно быть израсходовано полностью.
Продукты |
Нормы затрат на 100шт.,пиццы, кг | ||
ассорти |
грибная |
салями | |
Грибы |
6 |
7 |
4 |
Колбаса |
5 |
3 |
8 |
Тесто |
10 |
8 |
6 |
Доход, тыс. руб. с 100шт.пиццы |
9 |
6 |
5 |
2.7. Швейная фабрика выпускает женские и мужские костюмы. Расход тканей на изготовление костюмов, запасы сырья и доход от реализации единицы продукции каждого вида указан в таблице.
Виды ресурсов |
Нормы затрат на производство 1 ед. |
Запасы ресурсов | |
Женский костюм |
Мужской костюм | ||
Ткань, арт.1(м) |
1,0 |
3,0 |
300 |
Ткань,арт.2(м) |
1,0 |
1,0 |
150 |
Доход с 1 ед., тыс. руб. |
2 |
3 |
|
Согласно исследованиям маркетингового отдела количество выпускаемых женских костюмов должно быть как минимум на 20 шт. больше по сравнению с количеством мужских. Каков объем выпуска костюмов, при котором доход фабрики максимален?
2.8. Для изготовления изделий двух видов имеется 100кг металла. На изготовление одного изделия 1-го вида расходуется 2 кг металла, а изделия 2-го вида - 4кг. Отпускная стоимость одного изделия 1-го вида – 200 руб., а изделия 2-го вида – 300 руб., причем изделий 1-го вида требуется изготовить не менее 13, а 2 –го вида не более 40. Составить план выпуска продукции, при котором выручка будет наибольшей.
2.9. Цех производит два вида продукции на токарных и фрезерных станках, располагая ежедневными ресурсами в 900 и 300 человеко-часов, соответственно. Производство 1 тонны продукции первого и второго вида требует 150 и 300 человеко-часов работы на токарных станках, а также 100 и 50 человеко-часов работы на фрезерных станках. По условию заказчика продукция первого вида должна составлять не менее 1/3 от общей массы продукции. Доход от реализации 1 тонны продукции первого и второго вида составляет 12 и 19 тыс.руб. Найти оптимальный выпуск продукции, при котором доход цеха максимален.
2.10.По предписанию врача пациент, соблюдая диету, должен за сезон употребить необходимое количество питательных веществ, содержащихся в свежих фруктах, которое приведено в таблице:
Вещество |
Содержание питательных веществ в 1кг фруктов |
Норма потребления,г | |||
Клубника |
Яблоки |
Смородина | |||
Р1 |
3 |
2 |
1 |
30 | |
Р2 |
7 |
3 |
4 |
70 | |
Р3 |
0 |
0 |
5 |
40 |
Определить какое количество фруктов каждого вида необходимо купить за сезон, чтобы выполнить предписание врача с минимальными расходами, если цена за 1кг клубники 100руб., яблок – 50 руб., смородины – 80 руб.
2.11. На ферме по откорму бычков требуется составить кормовую смесь, одна тонна которой содержала бы белка не менее 35% от веса, жиров не менее 2,8%, а клетчатки не более 8% от веса. Содержание питательных веществ в различных компонентах смеси и их стоимость приведены в таблице:
Питательные вещества |
Содержание питательных веществ в % | ||
Люцерновая мука |
Соевый шпрот |
Рыбная мука | |
Белок |
17 |
25 |
56 |
Жиры |
2 |
5 |
7 |
Клетчатка |
25 |
3 |
1 |
Стоимость, тыс. руб. за 1т |
7 |
9 |
15 |
Каков самый дешевый вариант смеси?
2.12.Три марки тракторов следует распределить для выполнения боронования на поле 360га. Производительность техники и эксплуатационные затраты приведены в таблице:
Марки тракторов |
Марки тракторов | ||
ДТ 75М |
МТЗ 80 |
Т 40М | |
Производительность га/смена |
12 |
24 |
30 |
Эксплуатационные затраты (у.е.) |
20 |
35 |
60 |
Требуется выполнить работы с минимальными затратами при условии использования не более 14 машин.
2.13.(дополнительно). Клиент поручил брокеру разместить 1000000 рублей на фондовом рынке, сформировав портфель с ценными бумагами, чтобы получить максимальные годовые проценты с вложенного капитала. Выбор брокера ограничен акциями трех групп предприятий: финансовой А (доход 10% годовых), сырьевой В (8%) и электронной С промышленности (12%). При этом клиент для надежности поручил не менее 60% общей суммы вложить в акции групп А и В, а в акции С должно быть вложено меньше, чем в акции группы В?