Министерство образования республики беларусь белорусский государственный университет гуманитарный факультет Кафедра информационных технологий

ПРИЛОЖЕНИЕ 1 Примеры задач линейного программирования: Пример 1. Для изготовления трех видов изделий А, В и С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования указаны в табл. 1. В ней же указан общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида. Таблица 1 Тип оборудования Затраты времени (станко-часы)  на обработку одного изделия каждого вида Общий фонд рабочего времени оборудования (часы)     А В С Фрезерное 2 4 5 120 Токарное 1 8 6 280 Сварочное 7 4 5 240 Шлифовальное 4 6 7 360 Прибыль (руб.) 10 14 12   Требуется определить, сколько изделий и какого вида следует изготовить предприятию, чтобы прибыль от их реализации была максимальной. Составить математическую модель задачи. Решение. Предположим, что будет изготовлено x1 единиц изделий вида А, единиц – вида В и единиц – вида С. Тогда для производства такого количества изделий потребуется затратить станко-часов фрезерного оборудования. Так как общий фонд рабочего времени станков данного типа не может превышать 120, то должно выполняться неравенство Аналогичные рассуждения относительно возможного использования токарного, сварочного и шлифовального оборудования приведут к следующим неравенствам: При этом так как количество изготовляемых изделий не может быть отрицательным, то (1) Далее, если будет изготовлено x1 единиц изделий вида А, единиц изделий вида В и единиц изделий вида С, то прибыль от их реализации составит Таким образом, приходим к следующей математической задаче: дана система (2) четырех линейных неравенств с тремя неизвестными и линейная функция относительно этих же переменных . (3) Требуется среди всех неотрицательных решений системы неравенств (2) найти такое, при котором функция (3) принимает максимальное значение. Как это сделать, будет показано в дальнейшем. Линейная функция (3), максимум которой требуется определить, вместе с системой неравенств (2) и условием неотрицательности переменных (1) образуют математическую модельисходной задачи. Так как функция (3) линейная, а система (2) содержит только линейные неравенства, то задача (1) - (3) является задачей линейного программирования. Задача о выпуске продукции Фирма выпускает два вида древесно-стружечных плит - обычные и улучшенные. При этом производится две основные операции - прессование и отделка. Требуется указать, какое количество плит каждого типа можно изготовить в течение месяца так, чтобы обеспечить максимальную прибыль при следующих ограничениях на ресурсы (материал, время, затраты): Затраты Партия из 100 плит Имеющиеся ресурсы на месяц обычных улучшенных Материал (фунты) Время на прессование (часы) Время на отделку (часы) Средства (деньги) 20 4 4 30 40 6 4 50 4000 900 600 6000 Прибыль 80 100 max Перейдем к построению математической модели поставленной задачи. Введем следующие обозначения. Пусть Х - количество партий в 100 плит обычного вида, изготавливаемых в течение месяца; у - количество партий в 100 плит улучшенного качества, изготавливаемых в течение месяца. Тогда ожидаемую прибыль можно записать так: Требуется найти такие значения х и у, подчиненные условиям для которых Для того, чтобы найти в первой четверти плоскости хОу множество точек, координаты (х, у) которых удовлетворяют указанным выше неравенствам, необходимо сначала построить прямые (по точкам их пересечения с координатными осями) а затем, используя точку начала отсчета О(0, 0), определить соответствующие полуплоскости. Пересечением полученных полуплоскостей будет четырехугольник ОВМЕ. Наша целевая функция достигает наибольшего значения в одной из вершин четырехугольника. Нам необходимо найти координаты точкиМ- точки пересечения прямых EFи АВ, для этого надо решить систему уравнений Вычислить значения z в точках В(0, 100), Е(150, 0), М(100, 50): Из полученных значений выберем наибольшее и получим ответ: Транспортная задача Важный тип задач линейного программирования представляет задача о перевозках. Называется она так потому, что цель этой задачи заключается в минимизации полной стоимости перевозок известного количества товаров со складов к потребителю. Сбалансированная задача - задача о перевозках, в которой общий объем товаров, готовых к отправлению, в точности равен объему товаров, который готовы принять в пунктах назначения. Пример 1. Рассмотрим транспортную задачу, заданную таблицей   В Наличие 1 2 А 1 2 1 2 2 1 20 10 Запрос 16 14 30 Решение. Пусть - искомое число единиц товара, пересылаемого из пункта в пунк . Тогда данные таблицы можно представить в следующем виде: при условии, что Положим и выразим через t остальные переменные: из первого уравнения: , из второго уравнения: , из третьего уравнения: Тогда Из того, что все не отрицательны, получаем, что переменная t должна удовлетворять одновременно следующим четырем неравенствам: Тем самым, мы получили условие . Не трудно заметить, что  при t = 16. Ответ:   В Наличие 1 2 3 А 1 8 5 6 120 2 4 9 7 180 Запрос 70 140 90 300 Пример 2. Компания имеет два товарных склада и трех оптовых покупателей. Известно, что общий объем запасов на складах составляет 300 тыс. единиц продукции и совпадает с общим объемом заказов покупателей. Обозначим через количество товара, поставляемого со склада покупателю . Тогда соответствующая транспортная задача может быть сформулирована следующим образом. Минимизировать общую стоимость перевозок: при условии, что Получаем задачу линейного программирования, в которой основные ограничения вследствие того, что транспортная задача сбалансирована, является равенствами. Положим  и выразим через u и v остальные переменные. Имеем Учитывая, что все перевозки должны получить неотрицательные значения, мы приходим к задаче которую можно решить графическим методом. Выписанные неравенства определяют на плоскости (u, v) пятиугольник с вершинами (30, 0), (70, 0), (70, 50), (0, 120), (0, 30). Ответ:

Похожие:

	Республики Беларусь Белорусский государственный университет Юридический факультет Принятие решения по акту проверки и порядок его обжалования в Республике Беларусь 3		Республики Беларусь Белорусский Государственный Университет Интересный факт из истории создания Java-технологии, или удар по «пакету Windows» 29
	Республики Беларусь Учреждение образования «Белорусский государственный... Составители: В. А. Овсянкин, кандидат педагогических наук, доцент, Г. Н. Сущенко, старший преподаватель		Министерство образования и науки РФ новосибирский государственный... Когда появляется изображение цепи ордена Андрея Первоз­ванного на российском гербе
	Республики Беларусь Белорусский государственный университет Управляющие... Если необходимо обеспечить выполнение цикла хотя бы один раз, то удобно использовать оператор цикла с постусловием: 20		Дмитрий Олегович Роль информационных технологий в обеспечении деятельности... Роль информационных технологий в обеспечении деятельности банковской системы Республики Беларусь на примере сэд «Канцлер»
	Совершенствование правового регулирования таможенных процедур переработки... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный...		Государственный образовательный стандарт высшего профессионального... На основании статьи 35 Закона Республики Беларусь от 20 июля 2007 года "Об обращении с отходами" Министерство природных ресурсов...
	Классификация и кодирование информации; системы классификации; методы кодирования Министерство образования республики беларусь учреждение оразования «мозырский государственный педагогический университет имени И....		Республики Беларусь Учреждение образования «Белорусский государственный... Контрольная работа предназначена для самостоятельного выполнения студентами с целью проверки качества освоения ими теоретического...
	Пояснительная записка программа интернатуры по оториноларингологии... Заведующая кафедрой болезней уха, горла, носа учреждения образования «Белорусский государственный медицинский университет», кандидат...		Республики Беларусь Учреждение образования «Белорусский государственный... Дневник здоровья предназначен для определения физического состояния студентов бгпу, записи заданий преподавателя для самостоятельных...
	«московский психолого-социальный университет» факультет информационных технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий очной и заочной формы...		Министерство образования и науки российской федерации правительство... Правила определяют основные требования технической эксплуатации железной дороги
	Применение технологий olap и Data Mining для поддержки принятия стратегических решений в вузе Дагестанский государственный университет, факультет информатики и информационных технологий, Махачкала, Россия		Учебно-методический комплекс по модулю «астрономия» (б кв ) Факультет... ...