1. Теоретическая часть1.1 Характеристика предприятия
Товарищество с ограниченнойответственностью ТОО «Реверс» как юридическое лицо былозарегистрировано 11 ноября 1999 года и является крупнейшим поставщикомкомпьютерной техники в Экибастузе.
Основная производственная икоммерческая деятельность компании:
производство и поставкакомпьютеров, серверов, комплектующих и периферийных устройств;
поставка копировальной техники;
реализация лицензионногопрограммного обеспечения;
реализация и обслуживаниекопировальной техники;
прокладка локальных сетей;
внедрение и поддержкаинформационных систем на базе программных продуктов «Фирмы 1С»;
разработка и поддержкавеб-сайтов;
техническое и сервисноеобслуживание предприятий города Экибастуза на договорной основе.
Благодаря тесному сотрудничествус производителями, в Техцентре Revers всегда низкие цены и широкий ассортименттовара. Имеется собственный авторизованный сервисный центр ТОО «Аверс-Сервис»специализирующийся на ремонте и обслуживании бытовой техники, электроники,кондиционеров.
В настоящий момент цельюкомпании является дальнейшее глубокое освоение частного сектора рынка изакрепление своих лидирующих позиций. Для выполнения этой цели руководствокомпании постоянно ищет новые методы работы с клиентами, улучшая сервисноеобслуживание.
Руководство компании делаетосновную ставку на снижение розничных цен, в сравнении с их уровнем у существующихна сегодняшний день конкурентов, а также на качество реализуемой продукции исервисное обслуживание.1.2 Экономическая постановка задачи
Техцентр «Реверс» в2009 году в октябре месяце объявил скидки на весь месяц по следующим отделам: Отделкопировальной техники и заправки картриджей (B1) Отдел продажи компьютернойтехники (B2) Отдел ремонта и обслуживание компьютерной техники (B3)
В Октябре месяце заявки в Техцентр«Реверс» сделали четыре организации: СОШ 24 (A1) СОШ 35 (A2) ЦТДЮ«Кайнар» (A3) Компьютерный клуб (A4).
Для СОШ 24 от техцентра «Реверс»в связи с акцией во всех отделах были сделаны скидки. В отделе копировальнойтехники и заправки картриджей скидка в 5%, в отделе продажи компьютернойтехники 10%, в отделе ремонта и обслуживания компьютерной техники 10%.
Для СОШ 35 от техцентра «Реверс»в связи с акцией во всех отделах были сделаны скидки. В отделе копировальнойтехники и заправки картриджей скидка в 5%, в отделе продажи компьютернойтехники как постоянному клиенту скидка 15%, в отделе ремонта и обслуживаниякомпьютерной техники в 12%,
Для ЦТДЮ «Кайнар» всвязи с акцией во всех отделах были сделаны скидки. В отделе копировальнойтехники и заправки картриджей скидка в 3%, в отделе продажи компьютернойтехники скидка в 5%, в отделе ремонта и обслуживания компьютерной техники 6%.
Для Компьютерного клуба «Бест»во всех отделах были сделаны скидки. В отделе копировальной техники и заправкикартриджей скидка в 2%, в отделе продажи компьютерной техники скидка в 5%, вотделе ремонта и обслуживания компьютерной техники 6%.
Составить план обслуживанияорганизаций с максимальной выгодой для техцентра, учитывая предоставленныескидки.
При обслуживании отделом продажиСОШ 24 должен быть не более 15 продаж, обслуживание отдела ремонта для СОШ 24должен быть не менее 15 вызовов.
Таблица 2.1 — Исходная таблицаai/ bj B1 B2 B3 B4 25 25 15 25 A1 40 10 15 5 5 A2 30 10 12 6 6 A3 30 5 5 3 2
Х11=151.3 Экономико-математическое моделирование
Содержанием любойэкономико-математической модели является выраженная в формально-математическихсоотношениях экономическая сущность условий задачи и поставленной цели. Вмодели экономическая величина представляется математическим соотношением, но невсегда математическое соотношение является экономическим. Описаниеэкономических условий математическими соотношениями — результат того, чтомодель устанавливает связи и зависимости между экономическими параметрами иливеличинами.
По содержанию различаютэкономико-математические и экономико-статистические модели. Различие между нимисостоит в характере функциональных зависимостей, связывающих их величины. Так,экономико-статистические модели связаны с показателями, сгруппированнымиразличными способами. Статистические модели устанавливают зависимость междупоказателями и определяющими их факторами в виде линейной и нелинейной функции.Экономико-математические модели включают в себя систему ограничений, целевуюфункцию.
Система ограничений состоит изотдельных математических уравнений или неравенств, называемых балансовымиуравнениями или неравенствами.
Целевая функция связывает междусобой различные величины модели. Как правило, в качестве цели выбираетсяэкономический показатель (прибыль, рентабельность, себестоимость, валоваяпродукция и т.д.). Поэтому целевую функцию иногда называют экономической,критериальной. Целевая функция — функция многих переменных величин и можетиметь свободный член.
Критерии оптимальности — экономический показатель, выражающийся при помощи целевой функции через другиеэкономические показатели. Одному и тому же критерию оптимальности могутсоответствовать несколько разных, но эквивалентных целевых функций. Модели содной и той же системой ограничений могут иметь различные критерии оптимальностии различные целевые функции.
Решением экономико-математическоймодели, или допустимым планом называется набор значений неизвестных, которыйудовлетворяет ее системе ограничений. Модель имеет множество решений, илимножество допустимых планов, и среди них нужно найти единственное,удовлетворяющее системе ограничений и целевой функции. Допустимый план,удовлетворяющий целевой функции, называется оптимальным. Среди допустимыхпланов, удовлетворяющих целевой функции, как правило, имеется единственныйплан, для которого целевая функция и критерий оптимальности имеют максимальноеили минимальное значение. Если модель задачи имеет множество оптимальныхпланов, то для каждого из них значение целевой функции одинаково.
Если экономико-математическаямодель задачи линейна, то оптимальный план достигается в крайней точке областиизменения переменных величин системы ограничений. В случае нелинейной моделиоптимальных планов и оптимальных значений целевой функции может быть несколько.Поэтому необходимо определять экстремальные планы и экстремальные значенияцелевой функции. План, для которого целевая функция модели имеет экстремальноезначение, называют экстремальным планом, или экстремальным решением.
Для нелинейных моделей иногдасуществуют экстремальные значения целевой функции, а для линейных моделейэкстремальных планов и экстремальных значений целевой функции быть не может.
Таким образом, для принятияоптимального решения любой экономической задачи необходимо построить ееэкономико-математическую модель, по структуре включающую в себе системуограничений, целевую функцию, критерий оптимальности и решение.
Методика построенияэкономико-математической модели состоит в том, чтобы экономическую сущностьзадачи представить математически, используя различные символы, переменные ипостоянные величины, индексы и другие обозначения. Все условия задачинеобходимо записать в виде уравнений или неравенств. Поэтому, в первую очередьнеобходимо определить систему переменных величин, которые могут для конкретнойзадачи обозначить искомый объем производства продукции на предприятии,количество перевозимого груза поставщиками конкретным потребителям.1.4 Математическая постановка задачи
Математическая модельтранспортной задачи в общем случае имеет вид
/> (1.1)
/> i=1,2,…,m, (1.2)
/> j=1,2,…,n, (1.3)
/> i=1,2,…,m; j=1,2,…,n. (1.4)
Целевая функция задачи (1.1) выражаеттребования обеспечить минимум суммарных затрат на перевозку всех грузов. Перваягруппа из т уравнений (1.2) описывает тот факт, что запасы всех т поставщиковвывозятся полностью. Вторая группа из n уравнений (1.3)выражает требования полностью удовлетворить запросы всех nпотребителей. Неравенства (1.4) являются условиями неотрицательности всехпеременных задачи.
Таким образом, математическаяформулировка транспортной задачи состоит в следующем: найти переменные задачи
/> i=1,2,…,m; j=1,2,…,n, (1.5)
удовлетворяющее системеограничений (1.2), (1.3), условиям неотрицательности (1.4) и обеспечивающееминимум целевой функции (1.1).
В рассмотренной моделитранспортной задачи предполагается, что суммарные запасы поставщиков равнысуммарным запросам потребителей, т.е.
/>.(1.6)
1.5 Транспортная задача с ограниченными возможностями транспортных средств
Под названием “транспортнаязадача” объединяется широкий круг задач с единой математической моделью. Данныезадачи относятся к задачам линейного программирования и могут быть решенысимплексным методом. Однако матрица системы ограничений транспортной задачинастолько своеобразна, что для ее решения разработаны специальные методы. Этиметоды, как и симплексный метод, позволяют найти начальное опорное решение, азатем, улучшая его, получить оптимальное решение.
В общей постановке транспортнойзадачи предполагается, что из любого пункта производства любой пунктпотребления может быть перевезено любое количество груза.
В целом ряде случаев оптимизациипланирования перевозок приходится учитывать ограниченные возможноститранспортных путей и средств. Поэтому математическую модель транспортной задачи:
/> (1.7)
/> i=1,2,…,m, (1.8)
/> j=1,2,…,n, (1.9)
/> (1.10)
должны быть введеныдополнительные ограничительные условия, учитывающие возможность транспортныхпутей и средств.
Если обозначиться транспортныевозможности между пунктами I и jчерез dij, то количество груза />, которое может бытьперевезено по этому направлению за планируемый период времени, не должнопревышать транспортных возможностей, т.е.
/> (1.11)
Тогда ограничения 1.10, 1.11 объединяются,и модель задачи усложняется двусторонними ограничениями на переменные
/> (1.12)
При этом общая транспортнаявозможность дорог, соединяющих I -йпункт производства со всеми n пунктами потребления,должна быть ровна или больше количества продукции, предназначенной к постановкеиз этого i-го пункта всем nпотребителя, т.е.
/> i=1,2,…,m, (1.13)
Общая же транспортнаявозможность дорог, соединяющих j-й пункт потребления совсеми m пунктами производства, должна быть равна илибольше количества продукции, которые надо поставить в этот j-йпункт от всех m поставщиков, т.е.
/> i=1,2,…,n, (1.14)
Существуют различные подходы крешению этой задачи. Рассмотрим наиболее простой из них.
Путей некоторых преобразованийусловий ее можно свести к типу обычной транспортной задачи. Для этого пунктпроизводства или потребления, для которых условия ограничены транспортныевозможности, разбивается на два условных пункта. При этом следует подчеркнутьнепременно один пункт.
Мощность условного поставщика А’i — принимается равныйустановленной возможности средств, соединяющих пункт и с потребителями j
A’i=dij(1.15)
а мощность условного поставщикаА’j — равнойразности между заданными в условии задачи мощностью поставщика в пункте I и возможностью средств между I-м и j-м пунктами, т.е.
a’’i=ai-dij. (1.16)
При этом затраты на поставкугрузов из пунктов I’ в пункт j-cijпринимаютсяравными действительным расходам cijприведенным в условии задачи. В оптимальном решениепеременные хij могут иметь любоенеотрицательное значение от нуля до a’i, т.е.
/> (1.17)
В отличие от них переменные хij в оптимальном решениинепременно должны быть равны нулю, поскольку мощность А’j характеризует количество в пункте и сверхустановленной средств, соединяющих пункты i и j, следовательно это часть груза должна быть направлена не j-му а любому другому потребителю. Для того, чтобы воптимальном решении обеспечить значение переменных хij равно нулю, затраты на поставку груза из пункта i’’ в пункт j принимаются равными М,т. е cij=М.
При минимизации целевой функции(1.7) и коэффициентах cij=М, в оптимальномрешении получим
/>
Отсюда следует, что
Xij= Xi’j+Xi’j = Xij(1.18)
Тогда, исходя из условий (1.15),(1.17), получим
/>
Таким образом, объем поставкигруза из пункта i в пункт j непревысит установленной способности транспортных средств, обеспечивающих этипункты.
Если для какой то пары пунктовпроизводства i потребления s транспортные возможности не ограничены, объем поставки грузаот поставщика Аi к потребителю Bsопределится как сумма значений пары соответствующих переменных:
/>
Дальнейший расчет будет выполненс помощью венгерского метода решении транспортного алгоритма.
1.6 Решение транспортной задачи с ограниченными возможностями транспортныхсредств венгерским методом
Предварительный этап. Поисходной матрице С выполняется построение матрицы С', а затем матрицы Co, по известнымправилам.
Выполняется построениеначального плана Xo. Построение плана выполняется, сверху-вниз по столбцамматрицы Co начиная с левого, для O матрицы Co, при этом учитывается пропускнаявозможность коммуникаций.
Разметка. На этапе разметкиотмечают символом "+" столбцы с нулевыми невязками и существенныенули матрицы С. Точкой отмечают существенные неполные нули, а двумя точками — полные.Несущественные нули остаются без разметки. С точки зрения коммуникации ониявляются неполными.
Поисковый этап. Целью поискаявляется отыскать неполный нуль (без разницы существенный или несущественный),расположенный в строке с полной невязкой. Алгоритм поиска по колонкам известен.
Отыскание нуля на этапе поиска Элемент,который стоит на пересечении выделенной строки и выделенного столбца называетсядважды выделенным.
Выбирается корректирующийэлемент h. Корректирующий элемент получаем как минимальный положительныйэлемент среди невыделенной части матрицы, либо как минимальный модуль двухвыделенных отрицательных элементов, если поисковый этап окончился неудачей вневыделенной части матрицы элементы неположительны, а все дважды выделенныеэлементы неотрицательны, то задача неразрешима при данных ограничениях напропускную способность. Прибавляется h к выделенным элементам и вычитается изневыделенных. Если дважды выделенный элемент становится равным нулю, то еговыделяют "*«Знак выделения над столбцом снимается.
Расчёт целевой функции.
2. Практическая часть2.1 Описание алгоритма реализации модели
Определившись с методами,которые мы будем использовать в решении задачи, приступим к непосредственномуполучению результата. Решение транспортной задачи начинается с нахожденияопорного плана. Для этого существуют различные способы. Например, способ “Методограничений”/ Условия транспортной задачи заданы транспортной таблицей (2.1).
Таблица 2.1 — Условиетранспортной задачиai/ bj B1 B2 B3 B4 25 25 15 25 A1 40 10 15 5 5 A2 30 10 12 6 6 A3 30 5 5 3 2
В данном случае Σai=100 = Σbj=100имеем дело с закрытой моделью транспортной задачи.
Вводим количество поставщиков ипотребителей, затем строим матрицу элементы которой отображают стоимостьперевозки. Если задача по условию не является сбалансированной, то для этогодобавляем фиктивный пункт производства и потребителя. В нашем случаи задачаявляется сбалансированной, для ее решения строим матрицу Хij — план перевозок. Элементыэтого типа характеризуют количество товаров, которое будет перемещаться от i-го поставщика к j-му потребителю. Выводимцелевую функцию (см рисунок 2.1)
Рисунок 2.1 — блок-схема подпрограммы проверки на условие баланса.
/>
Происходитначальное вычисление опорного плана.
Построение плана выполняетсясверху-вниз по столбцам матрицы Co начиная с левого, для O матрицы Co, при этомучитывается пропускная возможность коммуникаций.
На этапе разметки отмечаютсимволом „+“ столбцы с нулевыми невязками и существенные нули матрицыС. Точкой отмечают существенные неполные нули, а двумя точками — полные. Несущественныенули остаются без разметки. С точки зрения коммуникации они являются неполными.
Целью поиска является отыскатьнеполный нуль (без разницы существенный или несущественный), расположенный встроке с полной невязкой. Алгоритм поиска по колонкам известен.
Элемент который стоит напересечении выделенной строки и выделенного столбца называется дваждывыделенным.
Выбирается корректирующийэлемент h. Корректирующий элемент получаем как минимальный положительныйэлемент среди невыделенной части матрицы, либо как минимальный модуль двухвыделенных отрицательных элементов
Если поисковый этап окончилсянеудачей в невыделенной части матрицы элементы неположительны, а все дваждывыделенные элементы неотрицательны, то задача неразрешима при данныхограничениях на пропускную способность.
Прибавляется h к выделеннымэлементам и вычитается из невыделенных. Если дважды выделенный элементстановится равным нулю, то его выделяют „*“Знак выделения надстолбцом снимается.
/> />
Рисунок 2.2 — Общий алгоритм вычисленияопорного плана
Вычисление невязки.
На основании матрицы С0строится начальный план. Заполнение плана осуществляется по нулям матрицы С0,двигаясь по столбцам сверху вниз, слева направо.
После заполнения элемента планаобъемы производства и потребления корректируются. Коррекции предшествуетпостроение цепочки. Цепочка содержит обязательно нечетное число нулей и впринципе может состоять из одного нуля. Построение цепочки начинается споследнего найденного нуля со штрихом. Затем по столбу к нулю со звездочкой, ауже от него по строке к нулю со штрихом. Для коррекции плана выбираетсякорректирующий элемент />. Он выбирается из невязкистроки сначала, из невязки конца цепочки и элементов конца Х, соответствующихнулям со звездочкой, которые вошли в цепочку. Элемент /> прибавляется кэлементу Хij, если ему в цепочкусоответствовал элемент Сij =0',и отнимается от элемента Хij, если в цепочкеему соответствовал элемент Сij =0*.Для коррекции плана рассчитывается невязка по строкам и столбцам, а так жесуммарная невязка.
Рассчитываются невязки постолбцам и строкам.
Невязка по строке />, i=1,m, j=1,n (2.19)
Невязка по строке />, i=1,m, j=1,n (2.20)
Затем рассчитывается суммарнаяневязка плана
∆/> (2.21)/> />
Если суммарная невязка плана =0, то это говорит о получении оптимального решения. Если не равно 0, то переходим кэтапу разметки. Выводим L — общая стоимость перевозок (см рисунок 2.3).
Рисунок 2.3 — блок- схема подпрограммы вычисления невязки.
Описание программы.
Описание работыпрограммы:
пользовательвводит количество поставщиков и потребителей;
пользовательвводит все данные о поставщиках и потребителях;
пользовательвводит ограничения;
строит матрицу Сij, элементы которой отображают определенную скидку;
Все используемые впрограмме переменные и подпрограммы, кратко описаны в таблицах 2.1
Описание блок-схемы:
блок-схема проверка на условиебаланса представлена на рисунке 2.1;
блок — схема общего алгоритмавычисления опорного плана представлена на рисунке 2.2;
блок схема вычисления невязкипредставлено на рисунке 2.3
Таблица 2.1 -Используемыепеременные Имя Тип Описание Cont TZLPTableContext В каждой конкретной библиотеке будет свой тип контекста Значение функции Integer
Код возврата:
ResultError = — 1 — ошибка в алгоритме;
ResultFinish = 0 — успешное окончание расчетов;
ResultNoSolution = 1 — нет решения; SourceF TFunction Целевая функция Limitations TLimitations Ограничения MinMax TFunctionType
Функция на минимум или максимум.
ftMin — минимум;
ftMax — максимум. Len Integer Длина массива ограничений Factors TDynIntegerArray
Массив ограничений: последовательность из Len целых чисел (Integer) Значение функции
TIntegerMatrix матрица из целых чисел