41728

Решение оптимизационных задач с помощью надстройки Excel «Поиск решения»

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

Информатика, кибернетика и программирование

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

Русский

2013-10-24

21.87 MB

210 чел.

Лабораторная работа № 2

«Решение оптимизационных задач с помощью надстройки Excel «Поиск решения»

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

  1.  По методической информации настоящего УП, наглядным материалам и учебной литературе ознакомиться с:

- свойства моделей;

- виды и назначения задач.

  1.  Кратко законспектировать в своем отчете изученную информацию.
  2.  Дополнить отчет ксерокопией рисунка 2.1.
  3.  Оформить отчет и представить его к проверке.
  4.  Подготовиться к защите отчета.

Методическая информация.

2.1. Свойства модели. Правила моделирования на основе электронных таблиц

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

  1.  была логически корректной;
  2.  представляла основные альтернативы для сравнения;
  3.  с ней было удобно проводить манипуляции, необходимые для анализа;
  4.  люди, не участвовавшие в создании модели, могли ее легко понять;
  5.  внешнее оформление модели было привлекательным.

Хотя многие «признаки» хорошей модели можно легко описать и зафиксировать, однако существую! определенные эстетические моменты, которыми можно овладеть только с помощью практики. Ниже перечислены основные правила, которыми следует руководствоваться, чтобы создать качественную модель на основе электронных таблиц:

  1.  необходимо четко обозначить все переменные;
  2.  следует четко обозначить входы модели, переменные решения и параметры;
  3.  надо указать критерии эффективности и выходные переменные;
  4.  не следует жестко привязывать значения параметров к формулам - параметры должны храниться в отдельных ячейках рабочего листа для удобства документирования и анализа;
  5.  если это возможно, надо отделять переменные, представляющие физические величины, от финансовых переменных;
  6.  следует использовать предоставляемые Ехсе1 возможности форматирования для выделения заголовков таблиц и ячеек.

Существует проблема, с которой сталкиваются те, кто стремится полностью документировать все параметры модели и в тоже время пытается сделать рабочий лист Excel, на котором представлена модель, компактным и свободным от излишних технических деталей. В Ехсе1есть две возможности, которые помогают разрешить это противоречие:

  1.  структурирование, позволяющее скрыть строки и столбцы, содержащие «технические» детали;
  2.  разделение окна рабочей книги на два или четыре подокна для выполнения подобной задачи.

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

Можно использовать подход, при котором исходная модель записывается в одном столбце, тогда в другие столбцы можно заносить копии модели, представляющие различные сценарии анализа «что - если». Это упрощает анализ чувствительности и графическое прели явление его результатов. Кроме того, появляется возможность исследовать диапазон входных параметров для поиска таких их значений, которые определяют если не оптимальные, то наиболее приятные значения критерия эффективности.

При расширении модели с целью включения в нее несколькихвременных периодов или нескольких продуктов следует учитывать два фактора.

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

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

Другим выходом из создавшегося положения является использование таблиц подстановки. Существует два типа этих таблиц.

  1.  Таблица подстановки с двумя входами позволяет варьировать две входные переменные и вычислять одну выходную переменную (как правило, критерий эффективности).
  2.  Таблица подстановки с одним входом позволяет изменять одну входную переменную и вычислять при этом любое число выходных переменных.

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

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

2.2. Оптимизационные модели

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

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

Существует несколько надстроек для программы Excel, предназначенных для оптимизации моделей при наличии ограничений. Примерами таких надстроек являются Solver(Поиск решения) и What'sBest. Excelсодержит сокращенную версию надстройки Поиск решения.

Есть два представления модели: символическая (математическая) модель линейного программирования (ЛП) и ее представление в электронной таблице, которую будем называть табличной моделью.

Электронная таблица хороню подходит для представления моделей ЛП, особенно при проведении анализа «что - если». Однако новичкам не следует формировать модель ЛП сразу в электронной таблице. Пока нет достаточного опыта, для создания «правильной» модели ЛП в Еxcelданный процесс лучше разбить на три этапа:

  1.  написание и проверка символической модели ЛП. Модель записывается на бумаге в математическом виде; это не займет много времени и поможет при отладке окончательного варианта табличной модели в Excel. Затем анализируются формулировки математической задачи с целью выявления возможных логических ошибок;
  2.  создание и отладка табличной модели ЛП. На основе символической модели ЛП создается ее представление в Excel. Затем производится проверка полученной табличной модели путем задания различных значений переменных решения с целью выявить возможные очевидные ошибки (например, для заведомо допустимых решений нарушаются ограничения, значения в ячейках левых частей или критерий эффективности оказывается лишенными смысла и т. д.);
  3.  попытка оптимизации модели с помощью надстройки Поиск решения. Если модель некорректно сформирована, результатом чаще всего будет сообщение об ошибке. Тогда нужно исправить модель, возможно, вернувшись к первому этапу.

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

При составлении математической модели в Excelследует придерживаться следующих рекомендаций:

  1.  каждая переменная решения располагается в отдельной ячейке, ячейки группируются по строкам или столбцам, каждому ограниченно отводится отдельная строка или столбец таблицы (чаще всего переменные решения расположены в столбцах, а ограничения в с троках);
  2.  переменные решения группируются в отдельный блок столбцов/строк;аналогично ограничения группируются в свой блок строк/столбцов;
  3.  все ячейки, содержащие переменные решения и целевую функцию, имеют заголовки в верхней части своего столбца, а все ограничения имеют заголовки в крайней слева ячейке своей строки;
  4.  коэффициенты целевой функции хранятся в отдельной строке, располагаясь непосредственно под или над соответствующими переменными решения: формула для вычислений целевой функции находится в соседней ячейке:
  5.  чтобы модель была понятней, ячейки с переменными решением целевой функцией выделяются рамкой по границе ячеек или заливкой ячеек;
  6.  коэффициент перед определенной переменной решения в каком-либо ограничении записывается в ячейку на пересечении столбца (строки), содержащего данную переменную решения, и строки(столбца), содержащей это ограничение;
  7.  в каждой строке ограничений за ячейками, содержащими коэффициенты данного ограничения, следует ячейка, в которую записано вычисленное значение функции ограничения (значение плюй частинеравенства), за ней следует ячейка, в которой стоит соответствующий знак неравенства, а затем ячейка, содержащая значение правой части неравенства. Дополнительно может включиться ячейка с формулой вычисления резерва, т. е. разности междузначениями левой и правой частей неравенства, вычисляемой таким образом, чтобы она была неотрицательной при соответствии ограничению;
  8.  ячейки, содержащие правые части ограничений, должны включать константы или формулы, в которые не входят переменные решения, - все формулы в правой части, прямо или косвенно связанные с переменными решения, должны быть перенесены в левую часть с помощью алгебраических преобразований данного неравенства;
  9.  не следует использовать в формулах модели ЛП функции ЕxcelЕСЛИ, ABS, MAX, MINи другие нелинейные функции. Такие функции могут использоваться в формулах рабочего листа, но только в том случае, если они не влияют (прямо или косвенно) на вычисление целевой функции;
  10.  условия неотрицательности переменных решения не обязательно включать в табличную модель. Как правило, они опускаются и указываются непосредственно в диалоговом окне средстваПоиск решения.

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

2.3. Надстройка Поиск решения

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

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

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

Конечно, допускаются нелинейные формулы, даже содержащие переменные решения, если эти формулы не связаны с вычислением значения целевой функции - ни прямо, ни косвенно, ни через ограничения.

2. 3. 1. Общие положения

НастройкаПоиск решенияпредоставляет широкие возможности и позволяет решать не только уравнения, но и задачи оптимизации. Поиск наилучшего решения из множества возможных –типичная задача, решаемая методами линейного программирования. Задачи подобного класса возникают, например, при планировании перевозок, распределении производственных ресурсов, оптимизации структурыпроизводства и т.п. Такие задачи возникают и при проведении инженерных расчетов.

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

  1.  Поиск допустимого решения. Если не задавать целевую ячейку (вполе вводаУстановить целевую ячейкув диалоговом не Поиск решения), то средствоПоиск решения остановится, найдя допустимое решение задачи, т.е. набор значений для изменяемых ячеек, которые удовлетворяют всем ограничениям. Если всефункции ограничений линейные, то установка флажкаПоиск решения в диалоговом окнеПараметры поиска решения ускорит поиск допустимого решения.
  2.  Подбор параметров. Целевая ячейка не задается, указываются только ограничения в виде равенств, либо задается конкретное значение для целевой ячейки без определения каких-либо ограничений. В первом случае выполняется поиск тех значений изменяемых ячеек, которые удовлетворяют заданной системе ограничений, т.е. решается система уравнений, в которой неизвестными являются значения изменяемых ячеек. (Если некоторые ограничения заданы в виде неравенств,Поиск решения находит допустимое решение, определяемое заданной системой ограничений). Во втором случае (задано конкретное значение целевой функции без указания ограничений)Поиск решения работает подобно средству ExcelПодбор параметра, используя другой алгоритм поиска. Кроме того, в отличие от средстваПодбор параметра, Поиск решения может проводить подбор нескольких параметров, дающих заданное значение целевой функции.
  3.  Поиск безусловного оптимума- задача нахождения максимума или минимума целевой функции при отсутствии ограничений. Эта задача имеет смысл только в том случае, если целевая функция является нелинейной (по отношению к значениям изменяемых ячеек). В случае попытки поиска оптимума линейной целевой функции (без задания ограничений) будет выводиться сообщение о неограниченном решении. Если целевая функция имеет несколько максимумов или минимумов, тоПоиск решения находит один из них (локальный оптимум), который может не совпадать с глобальным оптимумом. Какой из локальных оптимумов будет найден, зависит от начальных значений изменяемых ячеек.
  4.  Поиск оптимума при наличии ограничений. Наиболее общей задачей является задача условной оптимизации, когда заданы ограничении и адрес ячейки целевой функции, которую необходимо максимизировать или минимизировать. Если целевая функция и все ограничения линейны, то это задача линейной оптимизации или линейного программирования. Решение этой задачи будет найдено быстрее, надежнее и с более подробной дополнительной информацией, если в диалоговом окнеПараметры поиска решенияустановлен флажокЛинейная модель. В противном случаеПоиск решенияиспользует метод приведенного градиента. Если целевая имеет несколько оптимумов, которые удовлетворяют ограничениям, тоПоиск решения найдет один из них (т.е. локальный оптимум), который может не быть глобальным. Какой из локальный оптимумов будет найден, зависит от начальных значений изменяемых ячеек.

2.3.2. Использование надстройки Поиск решения

НадстройкаПоиск решения состоитиз двух программных компонентов. Первая - это встроенная в Excelпрограмма, написанная на языке VisualBasic, которая транслирует представленную на рабочем листе информацию во внутреннее представление, используемое второй. Вторая программа находится в памяти компьютера в виде отдельного программного модуля; именно она выполняет оптимизацию и возвращает найденное решение первой программе, которая, в свою очередь, обновляет данные на рабочем листе. Эти две программы взаимодействуют при помощи внутреннего интерфейса прикладных программ. Когда выбирается команда Поиск решения, происходит обращение к первой программе надстройкиПоиск решения, которая подготавливает таблицу к оптимизации и вызывает вторую программу - оптимизатор.

Таким образом, использование надстройкиПоискрешениясостоит из следующих действий:

  1.  откройте Excelи выполните обычные операции по созданию табличной модели. Можно создать несколько сценариев анализа «что-если» дня проверки модели:
  2.  после отладки модели переходите к этапу оптимизации, выбравкомандуПоиск решения в менюСервис;
  3.  в открывшемся диалоговом окнеПоиск решения укажите данные,необходимые для процесса оптимизации;
  4.  после здания необходимых данных (в какой ячейке содержится формула оптимизируемой целевой функции, какие ячейки включают переменные решения и т.д.) щелкните на кнопкеВыполнить.
  5.  Поиск решения выполняет процесс оптимизации;
  6.  если в табличной модели нет ошибок,Поиск решениявыведет на экран диалоговое окноРезультаты поиска решения, где можно указать, обновить ли исходную модель (т. е. занести ли в ячейки значения оптимального решения) и создавать ли отчет (который впоследствии можно распечатать);

Рис.2.1.Этапы работы с надстройкойПоиск решения

7) после этого можно продолжить выполнение анализа «что – если», чтобы провести анализ чувствительности оптимального решения.

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

  1.  Терминология средства Поиск решения

Применение специальной терминологии вызвано тем, что средство Поиск решения воспринимает только ячейки электронной таблицы, а не символическое представление моделей ЛП. С другой стороны, эти отличия часто номинальные. Соответствие между терминами, используемыми в моделях ЛПи средстве Поиск решенияпоказано в табл. 2.1.

Существует еще одно обстоятельство, о котором необходимо помнить при работе с моделями ЛП. Часто отрицательные решения не имеют смысла, когда на переменные решения налагается ограничение отрицательности. Поскольку эти ограничения очевидны, их не перечисляют в табличной модели ЛП. Однако при использовании средства Поиск решения условия неотрицательностипеременных решения необходимо указывать - их пропуск является распространенной ошибкой.

2.3.4 Рекомендации по поиску решения задач ЛП

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

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

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

В таких случаях нужно изменить масштаб измерения очень больших или очень маленьких чисел модели. В приведенном выше примере можно изменить денежные единицы, и выражать прибыль в миллионах долларов, а не в долларах. Это не приведет к потере общности и позволит сделать числа модели достаточно небольшими: теперь самое маленькое значение (0,5) отличается от самого большого (10) всего на 3 порядка.

Плохое масштабирование моделей является второй по значимости причиной возникновения проблем при оптимизации моделей ЛИ (первая пропуск ограничений неотрицательности).

Совет. Начиная с версии Excel97, помочь в разрешении проблем масштабирования может опция Автоматическое масштабирование в диалоговом окне Параметры поиска решения, однако это не гарантирует успешного устранения всех проблем.

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

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

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

На основе вышесказанного можно сформулировать следующие правилахорошего стиля моделирования:

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

ячейки правых частей неравенств в табличной модели должны содержать константы, а не формулы.

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

2.4. Линейная оптимизационная задача

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

2.4.1.Планирование производства шин

Первым типомзадач, относящихся к типу линейных оптимизационных, являются задачи планирования производства.

Рассмотрим такую задачу. Небольшая фабрика выпускает два типа шин для легковых автомобилей «ВАЗ»: зимний (W) и летний (S) варианты.

Продукция обоих видов поступает в оптовую продажу. Для производства шин используются два исходных продукта А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 тонн, соответственно. Расходы продуктов А и В на 1 тыс. шт. шин соответствующего типа приведены в табл. 2.2.

Изучение рынка сбыта показало, что суточный спрос на шипыSникогда не превышает спроса на шины типа Wболее чем на 1 тыс. шт. в сутки. Установлено, что спрос на шины типа Sникогда не превышает 2 тыс. шт. в сутки. Какое количество шин каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Таблица 2.2

Исходные данные задачи о планировании производства шин

Исходный продукт

Расход исходных продуктов на тыс. шт. в год

Максимально возможный запас, т

тип S

тип W

А

В

1

2

2

1

6

8

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

  1.  Для определения каких величин строится модель (т. е. каковы переменные модели)?
  2.  В чем состоит цель, для достижения которой из множества всех допустимых значений переменных выбираются оптимальные?
  3.  Каким ограничениям должны удовлетворять неизвестные?

В рассматриваемой задаче ответами на поставленные вопросы

будут:

  1.  Необходимо спланировать объем производства шин так, чтобы прибыль была максимальной. Поэтому переменными являются:

Xw- суточный объем производства шин типа Wи xs- суточный объем производства шин типа S.

Суммарная суточная прибыль от производства xwшин типа Wи xs шин типа Sравна z= 3xw+ 2xs.

  1.  Целью фабрики является определение среди всех допустимых значений xsи xwтаких, которые максимизируют суммарную прибыль, т. е. целевую функциюz.
    1.  Перейдем к ограничениям, которые налагаются на xsи xw. Объем производства шин не может быть отрицательным, следовательно:

xs, xw≥0.

Расход исходного продукта для производства обоих видов шин не может превосходить максимально возможный запас данного исходного продукта, следовательно:

xs + 2xw≤6

2xs +xw≤8.

Кроме того, ограничения на величину спроса на шины таковы:

xs- xw≤1

xs≤2

Таким образом, математическая модель данной задачи имеет следующий вид:

Z=3xw+ 2xsmax

при следующих ограничениях:

xs,xw> 0.

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

Ниже приводится решение данной задачи с помощью команды Сервис, Поиск решения(Tools, Solver).

Средство поиска решений является одной из надстроек Excel. Если в менюСервис(Tools) отсутствует командаПоиск решения(Solver), то для ее установки необходимо выполнить командуСервис, Настройки, Поиск решения (Tools, Add-ins, Solver).

Ячейки A3 и ВЗ отведены под значения переменныхxsи xw (рис. 2.2).

В ячейку С4 введена функция цели

=2*A3+3*B3

и ячейки А7:А10 введены левые части ограничений =АЗ+2*ВЗ

=2*АЗ+ВЗ

=ВЗ-АЗ

=ВЗ,

а в ячейки В7:В10 - правые части и ограничений.

После завершения ввода исходной информации следует выбрать командуСервис, Поиск решения(Tools, Solver) и заполнить открывшееся диалоговое окноПоиск решения(Solver), как показано на рис. 2.3.

Рис. 2.3. Диалоговое окно Поиск решения задачи о планировании производства шин

После нажатия кнопкиВыполнить(Solve) открывается окно Результаты поиска решения(SolverResults), которое сообщает, что решение найдено (рис. 2.4).

Результаты расчета рассматриваемой задачи (оптимальный планпроизводства и соответствующая ему прибыль) представлены на рис. 2.5. Как видно из рисунка оптимальным является производство 2 тыс. шт. шин Sи 2 тыс. шт. шин Wв сутки. Этот объем производства принесет фабрике 10000 тыс. руб.прибыли.

Рис. 2.4. Диалоговое окно Результаты поиска решения

Рис. 2.5Результатырасчета с помощью средства поиска решений для

задачипланирования производства шин

2.4.2.Элементы диалогового окна Поиск решения

Рассмотрим  более подробно элементы диалогового окнаПоиск решения (Solver) (рис. 2.3).

В полеУстановить целевую ячейку(SetTargetCell) диалогового окнаПоиск решения (Solver)вводится ссылка на ячейку сфункцией, длякоторой будет находиться максимум, минимум или заданное значение. В задаче о производстве шин в полеУстановить целевую ячейку(SetTargetCell)вводится $С$4 (рис. 2.3).

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

В полеИзменяя ячейки(ByChangingCells) указываются ячейки, которые должны изменяться в процессе поиска решения задачи, т.е. ячейки, отведенные под переменные задачи. В данном случае в полеИзменяя ячейки(ByChangingCells) следует ввести диапазон $A$3:$B$3.

Ограничения, налагаемые на переменные задачи, отображаются в поле Ограничения(SubjecttotheConstraints) (рис. 2.3). Средство поиска решений допускает ограничения в виде равенств,неравенств, а также позволяет ввести требование целочисленности переменных. Ограничения добавляются по одному. Для ввода ограничений следует нажать кнопкуДобавить(Add) в диалоговом окне Поиск решения(Solver) (рис. 2.3) и в открывшемся диалоговом окнеДобавление ограничения(AddConstraint) (рис. 2.6) заполнить поля.

2.4.2.1. Добавление ограничения

В полеСсылка на ячейку(CellReference) вводят левую часть ограничения - $А$3:$В$3, а в полеОграничение(Constraints) - правую часть, в нашем примере это значение равно 0. С помощью раскрывающегося списка вводится тип соотношения между левой и правой частями ограничения. В рассмотренном примере это ≥. Таким образом задается требование неотрицательности переменных. Чтобы завершить ввод ограничения следует нажать кнопкуДобавить(Add) в диалоговом окнеДобавление ограничения(AddConstraint) (рис. 2.6).

Рис. 2.6. Диалоговое окно Добавление ограничения

Вторая группа ограничений, налагаемых на переменные, вводится аналогично. Нажатие кнопки ОК завершает ввод ограничений.

Обратите внимание на то, что ограничения удобнее задавать в виде диапазонов, как это сделано в рассмотренном примере.

Для того чтобы проверить, какие параметры заданы для поиска решений, следует нажать кнопку Параметры(Options) в диалоговом окнеПоиск решения(Solver) (см. рис. 2.3).

2.4.2.2. Элементы окна Параметры поиска решения

  1.  ПолеМаксимальное время(MaxTime) служит для ограничения времени, отпускаемого на поиск решения задачи.
  2.  ПолеПредельное число итераций(Iteration) служит для ограничения числа промежуточных вычислений.
  3.  ПоляОтносительная погрешность(Precision) иДопустимоеотклонение(Tolerance) служат для задания точности, с которой ищется решение. Рекомендуется после нахождения решении с величинами данных параметров, заданными по умолчанию, повторить вычисления с большей точностью и меньшим допустимым отклонением и сравнить с первоначальным решением Использование подобной проверки особенно рекомендуется для задач с требованием целочисленности переменных.
  4.  ФлажокЛинейная модель(AssumeLinearmodel) служит для потки решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи. В случае нелинейной задачиэтот флажок должен быть сброшен, в случае линейной задачи, т. к. в противном случае возможно получение неверного результата.
  5.  ФлажокПоказывать результаты итераций(ShowIterationResults) служит для приостановки поиска решения и просмотра результатов отдельных итераций.
  6.  ФлажокАвтоматическое масштабирование(UseAutomaticSсаling) служит для включения автоматической нормализации входных и выходных значений, качественно различающихся повеличине, например, при максимизации прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.
  7.  ГруппаОценка(Estimates) служит для выбора метода экстраполяции.
  8.  ГруппаПроизводные(Derivatives) служит для выбора метода численного дифференцирования.
  9.  ГруппаМетод(Search) служит для выбора алгоритма оптимизации.

Для того чтобы вывести отчет о результатах решения задачи, следует выбрать в диалоговом окне Результаты поиска решении (SolverResults) (см. рис. 2.4) требуемый тип отчета: Результаты. Устойчивость. Пределы(Answer, Sensitivity, Limit).

2.4.3. Определение состава сплавов

Второй тип линейных оптимизационных задач представляют задачи о смесях.

Рассмотрим такую задачу. Пусть для получения сплавов А и В используются четыре металла I, II, III и IV, требования к содержанию которых в сплавах А и В приведены в табл. 2.3.

Характеристики и запасы руд, используемых для производства металлов I, II, IIIи IV, указаны в табл. 2.4.

Таблица 2.3

Требования к содержанию металлов в задаче определения состава

Сплав

Требования к содержанию металла

А

Не более 80% металла I

Не более 30% металла II

В

От 40 до 60", металла II

Не менее 30% металла III

Не более 70% металла IV

Таблица 2.4

Характеристики и запасы руд в задаче об определении состава сплавов

Руда

Максимальный запас,т

Состав, %

Цена,   S

II

1II

I III

IIV

Другие компоненты

1

1000

220

110

330

330

10

30

2

2000

110

220

330

330

10

40

3

3000

55

25

770

220

0

50

Пусть цепа 1 т сплава А равна 200 долларов, а 1 т сплава В - 210 долларов. Необходимо максимизировать прибыль от продажи сплавов А и В.

Обозначим через х, x2A, x3A, х и х1В,х, х, х количество I, II, IIIи IV металлов, используемых для получения сплавов А и В, соответственно. Количество использованной i-й руды обозначим yi,i[1; 3].

Тогда математическая модель данной задачи имеет вид:

при ограничениях:

Отведем под переменные хiА , хiВ i[1, 4] диапазон ячеек С3:D6, а под переменные yi, i[1; 3] диапазон ячеек F3:F5.

В ячейку G9 введем функцию цели:

В диапазон ячеек С8:С17 введем левые части ограничений, причем преобразуем их к виду, когда все переменные находятся слева, а все знаки неравенств – слева или равно.

В диапазон ячеек НЗ:Н5 введем количество имеющихся запасов руд. Выберем командуСервис, Поиск решения (Tools, Solver) и заполним диалоговое окноПоиск решения (Solver), как показано на рис. 2.9.

Результаты работы средства поиска решений представлены на рис. 2.8.

Рис. 2.8.Результат расчета в задаче определении состава сплавов

Рис. 2.9.Диалоговое окно Поиск решения в задаче определения состава сплавов

2.4.4. Планирование штатного расписания

Задача составления расписания является еще одним типом задач линеинои оптимизации.

Рассмотрим такую задачу. Пусть автотранспортному предприятию требуется определить, сколько водителей следует принят на работу в течение шести месяцев при условии, что любой из нихдолжен пройти предварительную стажировку. Потребности в количестве чловек - часов времени вождения транспортного средства для водителей  известны: в январе - 8000, в феврале - 9000, в марте – 8000, и апреле - 10000, в мае-9000 и в июне-12000.

Подготовка водителя к выполнению своих обязанностей занимает один месяц. Следовательно, прием на работу должен, по крайней мере на один месяц опережать выполнение водителем плановых рейсов. Кроме того, каждый водитель должен в течение месяца, отведенного на его подготовку, пройти 100-часовую стажировку непосредственно во время рейсов. Таким образом, за счет каждого обучаемомго водителя в течение месяца освобождается 100 человек - часов времени, отведенного для уже обученных водителей.

Каждый полностью обученный водитель в течение месяца может иметь наработку до 150 часов. ПАТП в начале января 60 опытных водителей. При этом ни одного из них не снимают с работы. Установленно  также, что приблизительно 10% обучаемых водитлей по окончании обучения увольняются по каким-либо обстоятельствам. Опытный водитель обходится ПАТП в $800, а обучаеый - в $400 в месяц. Необходимо спланировать штат ПАТП таким образом, чтобы минимизировать издержки за отчетные шесть месяцев.

Для данной задачи также можно разработать математическую модель, но проанализируем ее в развернутой форме. Отведем диапазон ячеек В3:В8 под число новых водителей, принимаемых на работу с января по июнь (рис. 2.10).

В ячейкуВ2 введем число водителей, работающих в декабре.В диапазоне ячеек D3:D8 вычислим число водителей, постоянно работающих в текущем месяце, введя в ячейки D3 и D4 формулы:

=B2

=D3+0,9*B3

и протаскивая последнюю из них на диапзон D5:D8.

В диапазоне Е3:Е8 вычислим пробг по месяцам, введя в ячейку Е3 формлу:

=D3*$G$12+B3*$F$12

и протаскивая ее на диапазон Е4:Е8, где в ячейки F12 и G12 введены длпустимый пробег обучаемого и работающего водителей. В диапазоне F3:F8 вычислим затраты по месяцам, введя в ячейку F3 формулу:

=D3*$E$12+B3*$D$12

и протаскивая ее на диапазон F3:F8, где в ячейки D12 и К12 введены затраты на обучение и работу водителя. Вычислим суммарные затраты за планируемый период в ячейке F9 по формуле: =CУMM(F3:F8)

Выберем командуСервис, Поиск решения (Tools, Solver). Заполним открывшееся диалоговое окноПоиск решения (Solver), как показано на рис. 2.11.

Рис. 2.10.Исходные данные задачи о планировании штатного расписания

Рис. 2.11.Диалоговое окно Поиск решения задачи о планировании штатного расписания.

Результаты расчета оптимального штата водителей приведены на рис. 2.12.

Согласно этим расчетам, фирма в последний месяц планового периода должна взять на обучение 17 новых водителей.

Рис. 2.12.Результаты расчета с помощью средства поиска решений в задаче о планировании штатного расписания

Предположим, что автотранспортное предприятие по какой-то причине решило не брать в июне на обучение новых водителей. Тогда в поле Ограничения диалогового окна Поиск решениянадо добавить В8=0. Оптимальное решение при таком дополнительном ограничении представлено на рис 2.13, из которого видно, что оно приведет к временному повышению текущих затрат.

Рис. 2.13. Решение задачи о планировании штатного расписании в том случае, если набор водителей в июне не производится

2.5 Транспортная задача

2.5.1 Сбалансированная модель транспортной задачи

Задача планирования перевозок или транспортная задача также может быть решена с использованием средства поиска решений.

Предположим, что фирма имеет 4 фабрики и 5 центров распределения ее товаров. Фабрики фирмы располагаются в Казани, Самаре, Саратове и Уфе с производственными возможностями 200, 150, 225 и 175 единиц продукции ежедневно, соответственно. Центры распределения товаров фирмы располагаются в Москве, Уфе, Санкт-Петербурге, Чебоксарах и Ульяновске с потребностями в 100, 200, 50, 250 и 150 единиц продукции ежедневно, соответственно. Хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в $0,75 в день, а ш траф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен $2,5 в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения приведена в табл. 2.5.

Необходимо так спланировать перевозки, чтобы суммарные транспортные расходы были минимальны.

Таблица 2.5. Транспортные расходы

1

2

3

4

5

6

Город

Москва

Уфа

Санкт -Петербург

Чебоксары

Ульяновск

1

Казань

1.50

2.00

1.75

2.25

2.25

2

Самара

2.50

2.00

1.75

1.00

1.50

3

Саратов

2.00

1.50

1.50

1.75

1.75

4

Уфа

2.00

0.50

1.75

1.75

1.75

Поскольку данная модель сбалансирована (суммарный объемпроизведенной продукции равен суммарному объему потребностей в ней), то в этой модели не надо учитывать издержки, связанные как со складированием, так и с недопоставками продукции. В противном случае в модель нужно было бы ввести:

  1.  в случае перепроизводства - фиктивный пункт распределения, стоимость перевозок единицы продукции в который полагается равной стоимости складирования, а объемы перевозок - объемам складирования излишков продукции на фабриках;
  2.  в случае дефицита - фиктивную фабрику, стоимость перевозок единицы продукции с которой полагается равной стоимости штрафов за недопоставку продукции, а объемы перевозок - объемам недопоставок продукции в пункты распределения.

Для решения данной задачи построим ее математическую модель. Неизвестными в данной задаче являются объемы перевозок. Пустьхij - объем перевозок с i-й фабрики вj-й центр распределения. Функция цели - это суммарные транспортные расходы, т. е.

гдеcij- стоимость перевозки единицы продукции с i-й фабрики в j-й центр распределения.

Неизвестные в данной задаче должны удовлетворять следующим ограничениям:

  1.  объемы перевозок не могут быть отрицательными;
  2.  так как модель сбалансирована, то вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть полностью удовлетворены.

В результате имеем следующую модель:

гдеai- объем производства на i-й фабрике,bj- спрос вj-м центре распределения.

Для решения этой задачи с помощью средства поиска решений необходимо ввести данные, как показано на рис. 2.14

Рис. 2.14.Исходные данные транспортной задачи

В ячейки А1:Е4 введены стоимости перевозок. Ячейки А6:Е9 отведены под значения неизвестных (объемы перевозок). В ячейки G6:G9 введены объемы производства на фабриках, а в ячейкиA11:Е11 введена потребность в продукции в пунктах распределения. В ячейку F10 введена целевая функция:

=СУММПРОИЗВ(А1:Е4;А6:Е9).

В ячейки А10:Е10 введены формулы, определяющие объем продукции, ввозимой в центры распределения:

=СУММ(А6:А9)

=СУММ(В6:В9)

=СУММ(С6:С9)

=СУММ(D6:D9)

=СУММ(Е6:Е9).

 В ячейки F6:F9 введены формулы, вычисляющие объем продукции, вывозимой с фабрик:

=СУММ(А6:Е6)

=СУММ(А7:Е7)

=СУММ(А8:Е8)

=СУММ(А9:Е9).

После ввода исходной информации следует выбрать команду Сервис, Поиск решения(Tools, Solver) и заполнить открывшееся диалоговое окно Поиск решения(Solver), как показано на рис. 2.15.

Рис. 2.15.Диалоговое окно Поиск решения для транспортной задачи

Не забудьте в диалоговом окне Параметры поиска решения (SolverOptions) (рис. 2.7) установить флажок Линейная модель (AssumeLinearModel).

Посленажатия кнопки Выполнить (Solve) средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы (рис. 2.16).

Рис. 2.16.Оптимальное решение транспортной задачи

2.5.2. Транспортная задача с фиксированными доплатами

Рассмотрим пример нелинейной задачи, которая после введения вспомогательных переменных становится линейной. Пусть, как обычно в транспортной задаче, имеетсяmпунктов производства некоторого товара с объемом производства а, в i-м пункте и n пунктов его потребления с объемом потребленияbj, вj-м пункте. Требуется найти величины xij - объемы перевозок из пунктаi в пунктj, удовлетворяющие естественным транспортным ограничениям:

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

Легко видеть, что частично целочисленная задача эквивалентна исходной задаче.

Рассмотрим пример решения частично целочисленной задачи. Пусть имеется два пункта производства с объемами производства по 200 единиц товара и три пункта потребления с объемами потребления 100, 200 и 100 единиц.

Затраты на перевозку единицы груза сij находятся в ячейках А1:С2, а плата за аренду транспортных средств dij- в ячейках F1:G2. Значения объемов производства введем в ячейки D1:D2. Значения объемов потребления введем в ячейки А1:СЗ. Под объемы перевозок xij отведем ячейки А5:С6, а под дополнительные целочисленные переменные уij - ячейки F5:G6. Под функцию цели отведем ячейку D7, в которую введем формулу:

=СУММПРOИЗВ(А1:С2;А5:С6)+СУММПРОИЗВ(El:G2;Е5:G6)

В ячейки А7:С7 введем формулы: =СУММ(А5:А6)

=СУММ(В5:В6)

=СУММ(С5:С6),

а в ячейки D5:D6 - формулы, которые представляют собой левые части формул транспортных ограничений:

=СУММ(А5:С5)

=СУММ(А6:С6).

Рис. 2.21Диалоговое окно Поиск решения для транспортной задачи с фиксированными доплатами

В диапазон ячеек А9:С10 введем формулу , которая представляет собой левую часть ограничений (2) при М=200.

Заполним диалоговое окно Поиск решения как показано на рис. 2.21.

После нажатия на кнопку Выполнить средство поиска решений найдет оптимальное решение (рис.2.22)

Рис. 2.22Решение транспортной задачи с фиксированными доплатами

2.5.3. Планирование транспортных перевозок

Рассмотрим еще один пример решения задачи планирования транспортных перевозок.

Пусть с трех складов требуется развести грузы в объемах 50, 30 и 40 тонн потребителям в 2 пункта доставки в объеме 40 и 80 тонн (таблица 2.6). Известна цена перевозки единицы груза с каждого склада в каждый пункт доставки (столбцы С и Е).

Задача заключается в следующем: определить такие объемы перевозок со складов в пункты доставки, чтобы стоимость транспортировки была минимальной. В таблице 2.6. искомые значения уже вычислены и обведены жирной рамкой. Видим, что суммарная стоимость перевозок составляет 1300 руб.

Рассмотрим, как были получены эти значения. Прежде всего, в ячейку С8 заносим целевую функцию. Здесь это стоимость всех «элементарных» перевозок, вычисляемая как сумма произведений цены на объем груза:

C8=C3*D3+E3*F3+C4*D4+E4*F4+C5*D5+E5*F5.

Таблица 2.6

Для решения снова используем инструмент Поиск решения, где введем следующие параметры:

  1.  установить целевую ячейку С8 равной минимальному значению;
  2.  изменяя ячейки  D3:D5;F3:F5;
  3.  ограничения:

B3=D3+F3 - стоимость вывоза с 1-го склада

B4=D4+F4 - стоимость вывоза со 2-го склада,

B5=D5+F5 - стоимость вывоза с 3-го склада,

D6=D3+D4+D5 - стоимость доставки в 1-й пункт,

F6=F3+F4+F5 - стоимость доставки в 2-й пункт,

E3:E5>=, - условие неотрицательности стоимости.

СЗ:С5>=0 - условие неотрицательности стоимости.

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

D3:О5=целое и F3:Р5=целое.

Результаты в этом случае будут таковы: в первый пункт доставки направляются грузы в объеме 7т, 30т, 3т с каждого из трех складов соответственно, во второй - 43т, 0т, 37т. Значение целевой функции, как и прежде, будет равным 1300 руб.

2.6. Задача о назначениях

Еще одной из типичных задач линейного программирования является задача о назначениях.

Рассмотрим пример решения такой задачи. Пусть четверо рабочих могут выполнять четыре вида работ. Стоимости сij выполнения i-м рабочим j-й работы приведены в ячейках диапазона A1:D4 (рис. 2.17).

Рис. 2.17.Стоимости работ в задаче о назначениях

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

 Рис. 2.18.Левые части ограничений в задаче о назначениях

Затем выберем команду Сервис, Поиск решения(Tools, Solver) и заполним открывшееся диалоговое окно Поиск решения (Solver), как показано на рис. 2.19.

Рис. 2.19.Диалоговое окно Поиск решения в задаче о назначениях

Не забудьте в диалоговом окне Параметры поиска решения (Solver) установить флажок Линейная модель (AssumeLinearModel).

Рис. 2.20.Оптимальный план работ в задаче о назначениях

После нажатия кнопки Выполнить(Solve) средство поиска решений найдет оптимальное решение (рис. 2.20).

Заметим, что флажок Формулы диалогового окна Параметры(Options), открываемого командой Сервис, Параметры(Tools, Options), обеспечивает отображение формул в ячейках, если они там находятся (рис. 2.18).

2.7. Пояснения к выполнению лабораторной работы

Пояснения к выполнению лабораторной работы даются на примере решения транспортной задачи. Решение задачи о назначениях и линейной оптимизационной задачи выполняются по аналогичной схеме.

2.7.1. Общая постановка задачи

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

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

Цели работы:

  1.  Научиться составлять наилучший (оптимальный) план перевозок от поставщиков к потребителям с учетом ограниченных ресурсов поставщиков и известной потребности потребителей.
  2.  Освоить методику и технологию оптимизации планов в табличном процессоре Excelс помощью надстройки Поиск решения(Solver).

  1.  Выделение проблемной системы

В проблемную систему включаем следующие объекты и показатели:

  1.  перечень потребителей и объемы их потребностей;
  2.  перечень возможных поставщиков и их возможности по объемам поставок;
  3.  затраты на поставку единицы груза от каждого поставщика к каждому потребителю, критерий - общие плановые затраты на доставку всех грузов от всех поставщиков ко всем потребителям.

  1.  Постановка задачи

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

Необходимо определить объемы перевозок между каждым заводом и складом в соответствии с потребностями складов и производственными мощностями заводов, при которых транспортные расходы минимальны.

2.7.4. Табличная модель

Обычно план перевозок составляется в виде таблицы. Структура документа составляется либо на бумаге, либо сразу в электронной таблице. Пример приведен в таблице 2.7.

В верхней строке электронной таблицы Excеlданы имена столбцов А, В, С... В первом столбце - номера строк. В столбце А - названия заводов-поставщиков. В строке 7 - названия потребителей.

Искомые показатели окружены сплошной жирной рамкой. Общие плановые затраты на перевозку в ячейке В20 надо минимизировать. Искомая плановая матрица объемов перевозки грузов от каждого поставщика к каждому потребителю расположена в диапазоне C8:G10.

Таблица 2.7. Исходные данные для расчетов

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

В строках 13:18 представлены исходные данные для расчетов. Они окружены пунктирными рамками. В диапазон В16:В18 вводятся мощности заводов-поставщиков. В матрицу С16:G18 надо ввести стоимость перевозки единицы груза от каждого поставщика к каждому потребителю.  В строку 14 надо ввести плановые потребности складов.

В строке 20 вычисляются стоимость перевозок для каждого склада и общие затраты по транспортировке.

2.7.5. Формулы таблицы

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

Таблица 2.8. Представление формул и чисел исходных данных

Суммируются все поставки от каждого завода в диапазоне В8:В10, чтобы проконтролировать, что они не превысят мощность заводов в диапазоне В16:В18. Также суммируются объемы поставок потребителям от всех заводов в строке 12, чтобы проконтролировать, что они не менее заказов потребителей в строке 14.

В строке 20 матрицу плана объемов перевозок умножается на матрицу стоимости перевозок и суммируем затраты в целевой ячейке В20.

2.7.6. Порядок выполнения работы

Вначале следует выполнить оптимальное планирование вручную. Затем выполняется компьютерная оптимизация и составлениематематической модели.

  1.  Задание № 1. Ручной поиск оптимального плана

На первом этапе предлагается составить оптимальный план перевозок вручную. Меняя данные в плане перевозок (диапазон С8:С10), следует добиться минимальной стоимости перевозок в ячейке В20, и при этом наблюдать, чтобы план поставок в ячейках В8:В10 не превышал мощности заводов в ячейках В16:В18. Поставки каждому складу не должны быть менее их потребностей.

Для решения можно использовать специфические алгоритмы решения транспортных задач, например, метод потенциалов или венгерский метод.

2.7.6.2. Задание № 2. Компьютерный поиск оптимального плана

На втором этапе предлагается составить оптимальный план с помощью надстройки Поиск решения.

Вызвать команду меню Сервис Поиск решения. Появляется диалоговое окно оптимизатора (рис. 2.21).

2.7.6.2.1. Настройка модели (математическая постановка задачи)

Рис. 2.21Диалоговое окно Поиск решения с координатно- математической моделью транспортной задачи

В диалоговое окно Поиск решения, в поле целевой ячейки вводим се адрес В20. В поле Изменения ячейки вводим адреса матрицы искомого плана перевозок C8:G10. В поля Ограничения вводим три строки неравенств значений диапазонов: поставки от заводов не должны превышать мощности заводов, поставки потребителям не должны быть меньше потребностей, значения плана не могут быть отрицательными

Свод параметров модели дан в таблице 2.9.

После настройки модели и установки параметров алгоритма нажимаем кнопку Выполнить окна Поиск решения. Через секунду оптимальное решение готово.

2.7.6.2.2. Анализ результатов и решения специалиста по организации перевозок

В таблице 2.7. дано оптимальное решение, найденное программойПоиск решения. Получен план перевозок с наименьшими затратами. Удовлетворены все ограничения. По Уралу и Украине использованы мощности заводов полностью, по Белоруссии недоиспользованы. При долгосрочных связях специалист по организации перевозок может предложить на будущее увеличить мощности заводов на Урале и Украине и уменьшить их в Белоруссии. Затраты на транспортировку уменьшатся.

Таблица 2.9. Cводпараметров модели

2.7.6.3. Заданием №3.На основе плановой таблицы составить математическую модель для алгоритма оптимизации

Введем обозначения:

n-количество поставщиков:

m- количество потребителей:

i - номер строки, поставщика, 1…n;

j - номер столбца, потребителя, 1…m;

Xij - искомое плановое количество перевозки от i-го поставщика к j-му потребителю;

Si - план поставок от i-го поставщика всем потребителям, сумма по строке;

Сi - план поставок j-му потребителю от всех поставщиков, сумма по столбцу;

Рij - цена (price) франко-склад единицы груза от i-го поставщика к j-му потребителю:

Вi - ограниченная (boundary = граница) мощность i-го поставщика;

Dj- ограниченный спрос (demand) j-го потребителя.

В общем виде экономико-математическая модель постановки задачи будет выделять следующим образом:

минимизировать затраты на перевозку грузов:

Для решения подобных задач разработаны варианты симплекс метода, метод потенциалов, венгерский метод и др.

2. 7. 7. Оформление отчета.

7.7.1. Отчет должен содержать:

  1.  Определение проблемы.
  2.  Плановую таблицу с результатом оптимального плана.
  3.  Анализ оптимального плана и решения менеджера.
  4.  Написать формулы модели для оптимизации транспортной

задачи.

  1.  Предложения по модификации, расширению модели и организации лабораторных работ.

Контрольные вопросы.

  1.  Какие виды задач существуют?
  2.  Почему актуальна проблема оптимального плана перевозок?
  3.  В чем принцип оптимизационной модели?
  4.  Перечислить объекты проблемной системы.
  5.  Пояснить структуру плановой таблицы.
  6.  Перечислить исходные данные, переменные и результирующие показатели модели.
  7.  Дать краткую технологию решения транспортной задачи с помощью надстройки Excel Поиск решения.


 

А также другие работы, которые могут Вас заинтересовать

84087. Понятие формы государства и факторы влияющие на ее образование 21.32 KB
  Форма государства это единство трех её основных элементов: формы правления формы государственного устройства политический режим некоторые ученые предлагаю присовокупить политическую динамику. Однако он не даёт синтезированного представления о форме государства в целом. Форма государства это такая структура которая включает не только организационные элементы но и связи между ними а также элементы функциональные методы деятельности.
84088. Форма правления понятие и виды 23.65 KB
  Монархия форма правления при которой в системе высших органов власти имеется монарх. Абсолютные монархии характеризуются полнотой власти монарха в этом случае в руках монарха сосредоточена вся полпота власти. Конституционные ограниченные монархии характеризуются тем что власть монарха ограничена Конституцией на основании которой в государстве действуют два института высшей власти: монарх и парламент которые делят между собой полномочия.
84089. Монархическая форма правления её признаки и виды 22.49 KB
  Форма правления представляет собой структуру высших органов государственной власти порядок их образование и распределение компетенции между ними. Форма государственного правления дает возможность уяснить: как создаются высшие органы государства и какого их строение; как строятся взаимоотношения между высшими и другими государственными органами; как строятся взаимоотношения между верховной государственной властью и населением страны; в какой мере организация высших органов rocва позволяет обеспечивать права и свободы гражданина. По...
84090. Республиканская форма правления признаки и виды 22.12 KB
  Установлена республиканская форма правления. Эта республиканская форма правления отличается от монархии которой присуще наследование статуса главы государства. Если рассматривать форму правления с чисто формальных позиций то можно сказать что она не оказывает определяющего влияния на характер государственного строя.
84091. Смешанные формы правления в современном мире 24.83 KB
  Так было во время и после буржуазных революций в Европе и Америке: молодая прогрессивная буржуазия возглавлявшая широкие слои населения добилась ограничения власти монарха ликвидации абсолютизма установления дуалистической или парламентарной монархии а иногда и республики например в США. В ходе этого исторического развития были и своеобразные зигзаги: республика при фашизме во главе с фюрером дуче каудильо мало чем по существу отличалась от монархии хотя юридически форма была иной а республики в социалистических странах странах...
84092. Форма правления: понятие и виды 16.75 KB
  Форма правления представляет собой структуру высших органов государственной власти порядок их образование и распределение компетенции между ними. Форма государственного правления дает возможность уяснить: как создаются высшие органы государства и какого их строение; как строятся взаимоотношения между высшими и другими государственными органами; как строятся взаимоотношения между верховной государственной властью и населением страны; в какой мере организация высших органов государства позволяет обеспечивать права и свободы...
84093. Унитарное государство признаки и виды 20.55 KB
  Унитарное государство характеризуется следующими признаками: унитарное устройство предполагает единые общие для всей страны высшие исполнительные представительные и судебные органы которые осуществляют верховное руководство соответствующими органами; на территории унитарного государства действует одна конституция единая система законодательства одно гражданство; составные части унитарного государства области департаменты округа провинции графства государственным суверенитетом не обладают; унитарное государство на территории...
84094. Федерация: понятие и признаки, виды 23.76 KB
  Существуют следующие формы государственного устройства: 1 Унитарное государство 2 Федеративное государство 3 Конфедеративное на данный момент не существует в природе 4 Региональное государство Федеративное государство представляет собой добровольное объединение ранее самостоятельных государственных образований в одно союзное государство государство состоящее из государств членов или государственных образований субъектов федерации. На данный момент в мире насчитывается 24ре федерации. Федерации бывают: а Договорные и...
84095. Форма государственного устройства: понятие и виды 21.73 KB
  Территория федерации состоит из территорий ее отдельных субъектов: штатов кантов земель республик и т. Субъекты федерации имеют право принятия собственной конституции имеют свои высшие исполнительные законодательные и судебные органы 4. В большинстве федерации существует союзное гражданство и гражданство федеральных единиц. При федеральном государственном устройстве в парламенте имеется палата представляющая интересы членов федерации.