Лекции по "Развитию операционных систем"

Обозначим через план выпуска продукции вида П1, П2, …, Пj, …, Пn, которые обеспечивают предприятию максимум объема реализации при имеющихся ресурсах.

Получаем следующую математическую модель: найти план выпуска продукции видов П1, П2, …, Пj, …, Пn,, обеспечивающий максимум объема реализации в стоимостном выражении

                                                      (16.1.1.)

при ограничениях на лимитируемые ресурсы

                                                (16.1.2.)

и условии неотрицательности

                                                   (16.1.3.)

где – вектор цен, т.е. цена реализации единицы каждого вида продукции;

     число, указывающее, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида;

     – вектор ресурсов, т.е. количество каждого вида ресурса.

Аналогичная математическая модель составляется для задачи о выборе оптимальных технологий.

 

 

Задача о раскрое материалов.

 

Суть задачи об оптимальном раскрое состоит в разработке таких технологически допустимых планов раскроя, при которых получается необходимый комплект заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводится к минимуму. Рассмотрим простейшую модель раскроя по одному измерению. Более сложные постановки ведут к задачам целочисленного программирования.

Модель задачи раскроя по одному измерению длинномерных материалов (прутков, труб, профильного проката и др.) может быть сформулирована так. Пусть имеется N штук исходного материала, длина каждой штуки равна L. Нужны заготовки m видов, длины которых равны . Известна потребность в заготовках каждого вида, она равна . Изучение вопроса раскроя (построение технологической карты раскроя) показывает, что можно выделить n приемлемых вариантов раскроя исходного материала длиной L на заготовки длиной . Обозначим через количество заготовок i-го вида, получаемое при раскрое единицы исходного материала по j-му варианту, - отходы при раскрое единицы исходного материала по j-му варианту.

План задачи , где – количество единиц исходного материала, планируемое к раскрою по j-му варианту.

Функция цели – минимум отходов, получаемых при раскрое:

                                                      (16.1.4.)

при ограничениях на число единиц исходного материала

                                                              (16.1.5)

на удовлетворение ассортиментного спроса потребителей

                                                (16.1.6.)

и условии неотрицательности

                                                   (16.1.7.)

где - отходы при раскрое единицы исходного материала по j-му варианту;

     - количество заготовок i-го вида, получаемое при раскрое единицы исходного материала по j-му варианту;

     N – количество исходного материала, длина каждой из которых равна L;

     - потребность в заготовках каждого вида.

Похожие математические модели строятся для задачи о смесях, задачи о диете.

 

К задачам линейного программирования относится транспортная задача. Формулировку и математическую модель этой задачи мы рассмотрим отдельно несколько позже.

 

Рассмотрим пример задачи линейного программирования.

Пример 16.1.  При изготовлении изделий И1 и И2 используются токарные и фрезерные станки, а также сталь и цветные металлы. По технологическим нормам на производство единицы изделия И1 требуется 300 и 200 единиц соответственно токарного и фрезерного оборудования (в станко-часах) и 10 и 20 единиц стали и цветных металлов (в килограммах). Для производства единицы изделия И2 требуется 400, 100, 70 и 50 соответствующих единиц тех же ресурсов. Цех располагает 12400 и 6800 станко-часов оборудования, 640 и 840 кг материалов. Прибыль от реализации единицы изделия И1 – 6 тыс. ден. ед., И2 – 16 тыс. ден. ед. Требуется:

1)  свести исходные  данные в таблицу, удобную для  построения модели;

2)  составить математическую  модель задачи (показатель эффективности – прибыль).

 

Решение.  1)  Обозначим через x1 число изделий И1, через x2 – изделий И2, через Z – суммарную прибыль от реализации производственных изделий, тогда исходные данные удобно представить в виде таблицы.

 

 

 

 

Ресурсы	Затраты на единицу изделия		Объем ресурса	Вид ограничений
	И1	И2
Станки, станко-ч      токарные      фрезерные Сталь, кг Цветные маталлы, кг	300 200 10 20	400 100 70 50	12400 6800 640 840
Прибыль, тыс. ден. ед.	6	16
План выпуска, шт.	x1	x2

 

2)  Так как каждое  изделие И1 дает прибыль 6 тыс. ден. ед., а таких изделий изготовляется x1 ед., то все изделия И1 дадут прибыль 6x1; аналогично изделия И2 обеспечат прибыль 16x2. Суммарную прибыль можно записать в виде целевой функции, которая максимизирует прибыль

.

Токарного оборудования на изделие И1 требуется 300 станко-часов, на изделие И2 – 400 станко-ч. Тогда для изготовления x1 изделий И1 и x2 изделий И2 потребуется токарного оборудования (станко-ч). Так как общий фонд рабочего времени токарных станков не может превышать 12400 станко-ч, должно выполняться неравенство . Аналогично можно записать условия, налагаемые на фонд рабочего времени фрезерных станков: , и лимитирующие материалы: по стали , по цветным металлам .

Итак, искомый план задачи . Целевая функция

.

Система ограничений

Переменные x1 и x2 не могут быть выражены отрицательными числами, поэтому

,