Краткие теоретические положения

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

«Тульский государственный университет»

Кафедра электронных вычислительных машин

Моделирование

ЛАБОРАТОРНАЯ РАБОТА № 1

Использование простейших линейных математических моделей в задачах распределения ресурсов

Методические указания

для студентов направления 230100

«Информатика и вычислительная техника»

специальности 230101 «Вычислительные машины,

комплексы, системы и сети»

Тула 2011

ЛАбораторная работа 1

использование простейших линейных математических моделей в задачах распределения ресурсов

Цель работы:знакомство с основными принципами использования простейших линейных математических моделей в задачах распределения ресурсов.

Краткие теоретические положения

Математическое программирование ("планирование")– это раздел математики, занимающийся разработкой методов отыскания экстремальных значений функции, на аргументы которой наложены ограничения. Методы математического программирования используются в экономических, организационных, военных и др. системах для решения так называемых распределительных задач. Распределительные задачи (РЗ) возникают в случае, когда имеющихся в наличии ресурсов не хватает для выполнения каждой из намеченных работ эффективным образом и необходимо наилучшим образом распределить ресурсы по работам в соответствии с выбранным критерием оптимальности.

Для применения количественных методов исследования в любой области всегда требуется построить некоторую математическую модель явления. При построении математической модели явление (а, значит, и операция) каким-то образом упрощается. Из множества факторов, влияющих на явление, выделяется сравнительно небольшое количество важнейших. Полученная схема описывается с помощью того или иного математического аппарата.

В результате устанавливаются количественные связи между условиями операции, параметрами решения и исходом операции, то есть показателем эффективности. Чем удачнее построена математическая модель, чем лучше она отражает характерные черты явления, тем успешнее будет проводимое исследование.

Рассмотрим простейший пример: предположим, что в результате реализации некоторого технологического процесса изготавливается изделие, состоящее из двух различных деталей. Для изготовления этих деталей имеются станки трех типов, каждый из которых способен изготавливать различное количество деталей первого и второго типа. Параметры станков представим таблицей:

Тип станка	Число станков	Производительность	Естественное распределение	Оптимальное распределение
		1-ая деталь	2-ая деталь	1-ая деталь	2-ая деталь	1-ая деталь	2-ая деталь
I
II							–
III						–

Очевидное «естественное распределение» состоит в том, что на каждой группе станков производится наибольшее возможное число комплектов деталей. Станки первого типа могут произвести в единицу времени 20 комплектов (например, первый и второй станок производят по десять первых деталей, а второй – двадцать вторых). Больше комплектов за единицу времени станки первого типа произвести не могут. Аналогично, для станков второго типа первый станок производит только первые детали (20 штук), второй – только вторые детали (30 штук), а третий – 4/5 времени производит первые детали (4/5*20=16 шт.) и 1/5 – вторые детали (1/5*30=6 шт.), и т.д. При подобной организации технологического процесса за единицу времени все станки способны произвести 20+36+21 = 77 изделий.

Однако, возможен и другой способ организации. В частности, можно на станках второго типа изготавливать только первые детали (3*20 = 60 первых деталей), на станках третьего типа – только вторые детали (1*80 = 80 деталей), а для станков первого типа указать, что первые два станка все время изготавливают только первые детали (10*2 = 20 первых деталей), а третий станок 3/5 времени изготавливает первые детали (10*3/5 = 6 деталей) и в часть оставшегося времени (менее 2/5) изготавливает вторые детали (20*2/5 = 8 > 6 потребных). Таким образом, на том же оборудовании за то же самое время оказывается возможным изготовить 86 изделий, что на 9 изделий (~11.6%) больше, чем при естественной организации производства.

Попробуем формально описать приведенную выше задачу:

допустим, что каждый из семи станков работает непрерывно, и часть рабочего времени занят изготовлением первых деталей, а остальное время – вторых. Если обозначить через часть времени, которую i-ый станок изготавливает первые детали, то вторые детали он будет изготавливать в течение времени. В этом случае можно сформулировать функцию, определяющую качество работы системы (так называемая целевая функция):

.

В данном случае эта функция описывает количество первых деталей, которые в совокупности изготавливают все семь станков за единицу времени. Очевидно, что чем большее количество деталей будет произведено, тем лучше работает вся система.

Однако максимизация данной функции должна осуществляться с учетом ряда ограничений. Во-первых, существуют естественные ограничения на величины : они не могут быть отрицательными по определению (как будет показано далее, требование неотрицательности является общим для всех задач математического программирования), и они не должны превышать единицу, т.е. (это ограничение связано с тем, что в данном случае по условию задачи характеризуют долю времени, которая, очевидно, не может превышать единицу).

Во-вторых, существует еще одно, менее очевидное ограничение. Оно связано с тем, что система должна производить комплектные изделия, то есть необходимо обеспечить, чтобы число первых деталей было равно числу вторых деталей. Это ограничение формально можно представить равенством:

.

Или, раскрыв скобки и приведя подобные слагаемые:

.

Таким образом, формальное описание задачи свелось к определению целевой функции и системы ограничений.

Линейное программирование (ЛП) является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач ЛП следующие:

1) показатель оптимальности L(X) представляет собой линейную функцию от элементов решения ;

2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.