Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Задачи с булевыми переменнымиСодержание книги
Похожие статьи вашей тематики
Поиск на нашем сайте
Частным случаем задач с целочисленными переменными являются задачи, в результате решения которых искомые переменные xj могут принимать только одно из двух значений: 0 или 1. Такие переменные в честь предложившего их английского математика Джорджа Буля называют булевыми. Помимо задания требования целочисленности (см. подразд. 1.3) при вводе условия задач с булевыми переменными необходимо: • для наглядности восприятия ввести в экранную форму слово "булевы" в качестве характеристики переменных; • в окне "Поиск решения" добавить граничные условия, имеющие смысл ограничения значений переменных по их единичной верхней границе (рис. 1.19). Рисунок 1.19. Добавление условия единичной верхней границы значений переменных некоторой задачи с булевыми переменными Работа № 2 ДВУХИНДЕКСНЫЕ ЗАДАЧИ ЛП (ТРАНСПОРТНАЯ ЗАДАЧА). Цель: научиться методам решения двухиндексных задач линейного программирования на ЭВМ, рассмотреть основные типы задач – транспортная задача, задача о назначении. Двухиндексные задачи ЛП вводятся и решаются в Excel аналогично одноиндексным задачам, рассмотренным работе 1. Рассмотрим решение двухиндексной задачи, суть которой заключается в оптимальной организации транспортных перевозок штучного товара со складов в магазины. ПРИМЕР 2.1. Из трех складов, имеющих некоторый продукт в количествах 50т, 60т, 70т, необходимо его доставить в три магазина в количествах 40т, 85т, 55т. Стоимости перевозки 1т продукта из склада i в магазин j заданы в виде матрицы С={cij} размерностью 3x3. Спланировать перевозки так, чтобы их общая стоимость была минимальной. 2 1 5 С = 3 4 3 4 6 6 Ввод исходной информации Готовим таблицу в Еxcel как показано на рис.2.1.
Рисунок 2.1. Исходные данные транспортной задачи Ячейки В3:D5 (выделены синим цветом) предназначены для переменных, в ячейках G3:G5 содержатся ограничения по мощностям (наличие товара на складе), ячейки В8:D8 содержат ограничения по спросу, в ячейках В11:D13 находятся коэффициенты матрицы С={cij}. Формулы для задания целевой функции, ограничений и граничных условий двухиндексной задачи представлены в табл. 2.
Формулы для экранной формы транспортной задачи Таблица 2
Дальнейшие действия (аналогично проведенным в работе 1) производятся в окне "Поиск решения", которое вызывается из меню "Сервис". Окно "Поиск решения" после ввода всех необходимых данных транспортной задачи представлено на рис.2.2. Рисунок 2.2. Окно "Поиск решения" транспортной задачи Результирующая табличная форма с заданием целевой функции, ограничений и граничных условий двухиндексной задачи и ее решение представлены на рис. 2.3. Рисунок 2.3. Экранная форма двухиндексной задачи (курсор в целевой ячейке Е13) В рассмотренном примере суммарное наличие товара на всех складах совпадает с общей потребностью, поэтому в "Поиске решения" (рис.2.2) мы использовали знак равенства B6:D6=B8:D8 (удовлетворить потребности) и E3:E5=G3:G5 (вывести весь товар) – такая транспортная задача называется закрытой. В случае избытка товара второе условие необходимо записывать со знаком ≤, тогда в результате решения у каких-то поставщиков останутся излишки товара. В случае дефицита товара первое условие необходимо записывать со знаком ≤, тогда в результате решения какие-то потребители окажутся частично неудовлетворенны (открытые задачи). ПРИМЕР 2.2. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона дали заказ на поставку соответственно 300, 600, 650 и 500 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в таблице:
Задание 2.1. Необходимо составить такой план перевозки (количество щебенки, перевозимой с каждого карьера на каждый строительный объект), чтобы суммарные затраты на перевозку были минимальными. Значение неизвестного параметра а взять равным номеру варианта. Рассмотрим еще один вид задач, сводящихся к ЗЛП – задачу о назначениях. ПРИМЕР 2.3. Цеху металлообработки нужно выполнить срочный заказ на производство деталей. Каждая деталь обрабатывается на 4-х станках С1, С2, С3 и С4. На каждом станке может работать любой из четырех рабочих Р1, Р2, Р3, Р4, однако, каждый из них имеет на каждом станке различный процент брака. Из документации ОТК имеются данные о проценте брака каждого рабочего на каждом станке:
Задание 2.2. Необходимо так распределить рабочих по станкам, чтобы суммарный процент брака (который равен сумме процентов брака всех 4-х рабочих) был минимален. Чему равен этот процент? Значение неизвестного параметра а взять равным номеру варианта. Обозначим за xij, i =1,2,3,4; j =1,2,3,4 - переменные, которые принимают значения 1, если i -й рабочий работает на j -м станке. Если данное условие не выполняется, то xij = 0. Целевая функция есть: 2,3 x 11+(1,9+ а /20) x 12+2,2 x 13+2,7 x 14+(1,8+ а /20) x 21+2,2 x 22+2 x 23+(1,8+ а /20) x 24+ +2,5 x 31+2 x 32+ 2,2 x 33+ 3 x 34+ 2 x 41+ 2,4 x 42+ (2,4– а /20) x 43+ 2,8 x 44→ min. Вводим ограничения. Каждый рабочий может работать только на одном станке, то есть x 11+ x 12+ x 13+ x 14=1; x 21+ x 22+ x 23+ x 24=1; x 31+ x 32+ x 33+ x 34=1; x 41+ x 42+ x 43+ x 44=1. Кроме этого, каждый станок обслуживает только один рабочий: x 11+ x 21+ x 31+ x 41=1; x 12+ x 22+ x 32+ x 42=1; x 13+ x 23+ x 33+ x 43=1; x 14+ x 24+ x 34+ x 44=1. Кроме того, все переменные должны быть целыми и неотрицательными: xij ≥0, xij – целые. (используйте 1.5). Работа № 3
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2016-04-19; просмотров: 436; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.42.205 (0.007 с.) |