тематики изучающий теорию и методы решения задач об экстремумах линейных функций на множествах задаваемых с
Работа добавлена на сайт samzan.net:
Основные положения
Линейное программирование
Линейное программирование − раздел математики, изучающий теорию и методы решения задач об экстремумах линейных функций на множествах задаваемых системами линейных неравенств. Задачи линейного программирования (Л.П.) являются математическими моделями задач экономического содержания.
Все модели Л.П. имеют два общих основных свойства.
Первое − это наличие ограничений. Они сужают множество допустимых решений. Например, менеджер по инвестициям имеет в своем распоряжении определенный капитал. Инвестиционные решения ограничены суммой данного капитала и распоряжениями таких правительственных органов, как Комиссия по ценным бумагам и биржам. Ограничения в реальных управленческих моделях выражаются в числовом виде, но в своей основе имеют физическую, экономическую или даже политическую природу.
Второе свойство заключается в том, что в каждой модели Л.П. существует единственный показатель эффективности, который необходимо максимизировать или минимизировать. (Так, в предыдущем примере менеджер по инвестициям, будет стремиться максимизировать свою прибыль от портфельных инвестиций.)
В моделях оптимизации показатель эффективности, который следует оптимизировать, называется целевой функцией. В экономике целевая функция, требующая максимизации, как правило это, прибыль, эффективность, производительность, а минимизации обычно требуют такие показатели, как затраты или время.
Все функции ограничений, а также целевая функция являются линейными функциями. График линейной функции двух переменных представляет собой прямую линию. В общем случае линейная функция − это такая функция, в которую каждая переменная вместе со своим коэффициентом входит в виде отдельного члена (т.е. переменные не умножаются, не делятся друг на друга, не возводятся в степень (отличную от 1), нет логарифмических, экспоненциальных и тригонометрических выражений и т.п.)
Для решения такого ряда задач необходимо построить математическую модель Л.П., а затем представить ее в виде электронных таблиц Excel. Созданная на первом этапе математическая модель позволяет увидеть всю модель целиком, что облегчает понимание табличной модели. В математической модели Л.П. ограничения записываются в виде системы неравенств. (В некоторых случаях необходимо ввести ограничения в виде равенств).
Если требуются дополнительные ограничения на сами переменные в виде неотрицательности решения, то
, , , …, .
Линейная целевая функция имеет математическое выражение исходя из условия задачи, и стремится к максимуму или к минимуму.
Решением задачи Л.П. является отыскание такого набора переменных , из области допустимых значений системы ограничений, при которых целевая функция достигает своего максимального (минимального) значения. Математически такие задачи решаются графическим методом (при двух переменных) и табличным симплекс-методом.
Информационные технологии позволяют повысить оперативность решения с помощью надстройки Поиск решения.
Примерами экономических задач, как задач линейного программирования являются: производственная задача, анализ безубыточности, задачи финансового планирования, управление портфелем активов, оптимизация рекламной компании, задача об оптимальном назначении, транспортная задача, модель замены оборудования и т.п.
Целочисленное линейное программирование
В данном разделе рассматриваются модели, которые строятся и оптимизируются как обычные модели линейного программирования за исключением того усложняющего обстоятельства, что некоторые или все переменные модели должны принимать целые значения. Метод Целочисленного линейного программирования (Ц.Л.П.) приводит к получению так называемого округленного решения. Использование таких решений допустимо в тех ситуациях, где округление, по сути, не имеет особого значения.
Двоичные переменные (принимающие значение 0 или 1) играют исключительно важную роль в прикладных моделях Ц.Л.П.. Такая модель используется в задачах, где управленческое решение строится не на количественных значениях переменных, а при ответе на вопрос: «да» или «нет». Да − проект принимается (х=1), в противном случае отвергается (х=0) (необходимо производить тот или иной товар или нет, обязательно назначить того или иного сотрудника на рассматриваемую должность или нет и т. п.)
Нелинейное программирование
Среди реальных задач строго линейные задачи скорее являются исключением, чем правилом. В общем случае к нелинейности моделей могут привести любые физические, биологические, экономические и логические взаимосвязи и их комбинации. Однако, хотя нелинейные явления широко распространены, нелинейные модели существенно сложнее оптимизировать, чем линейные.
Оптимизация задач линейного, целочисленного и нелинейного программирования.
Поиск решения − это надстройка, входящая в поставку Excel, предназначенная для оптимизации моделей.
Поиск решения при оптимизации линейного программирования использует симплекс- метод.
В программе Excel в меню Сервис применяя команду Поиск решения, откроется диалоговое окно где устанавливается адрес целевой ячейка, диапазон переменных.
Загрузка надстройки Поиск решения Excel:
- Нажмите кнопку Microsoft Office , а затем щелкните Параметры Excel.
- Выберите команду Надстройки, а затем в окне Управление выберите пункт Надстройки Excel.
- Нажмите кнопку Перейти.
- В окне Доступные надстройки установите флажок Поиск решения и нажмите кнопку ОК.
Алгоритм применения надстройки Поиск решения Excel:
- На вкладке Данные – в группе Анализ - Поиск решения отобразится диалоговое окно поиск решения:
В диалоговом окне Поиск решения есть три основных параметра:
• Установить целевую ячейку
• Изменяя ячейки
• Ограничения
Сначала нужно заполнить поле Установить целевую ячейку. Во всех задачах для средства Поиск решения оптимизируется результат в одной из ячеек рабочего листа. Целевая ячейка связана с другими ячейками этого рабочего листа с помощью формул. Средство Поиск решения использует формулы, которые дают результат в целевой ячейке, для проверки возможных решений. Можно выбрать поиск наименьшего или наибольшего значения для целевой ячейки или же установить конкретное значение.
Второй важный параметр средства Поиск решения — это параметр Изменяя ячейки. Изменяемые ячейки — это те ячейки, значения в которых будут изменяться для того, чтобы оптимизировать результат в целевой ячейке. Для поиска решения можно указать до 200 изменяемых ячеек. К изменяемым ячейкам предъявляется два основных требования. Они не должны содержать формул, и изменение их значений должно отражаться на изменении результата в целевой ячейке. Другими словами, целевая ячейка зависима от изменяемых ячеек.
Третий параметр, который нужно вводить, для Поиска решения – это Ограничения.
Кнопка Параметры открывает диалоговое окно Параметры поиска решения, где по умолчанию стоит определенный набор команд.
По умолчанию значение допустимого отклонения стоит 5%. Это значит, что процедура оптимизации продолжается только до тех пор, пока значение целевой функции будет отличаться от оптимального не более чем на 5%. Более высокие значения допустимого отклонения ускоряют работу средства Поиск решения при оптимизации моделей, однако существует риск, что найденное значение будет значительно отличаться от истинного оптимума соответствующей задачи. Устанавливая значение допустимого отклонения, например, равным 0 %, мы заставляем Поиск решения находить истинный оптимум задачи за счет, возможно, более длительного времени решения.
Для улучшения работы средства Поиска решения настройка диалогового окна Параметры поиска решения часто применяется при решении задач нелинейного программирования.
Значение в поле Сходимость используется для завершения процесса поиска решения, когда изменение целевой функции происходит очень медленно. Если установить меньшее значение сходимости, чем предусмотрено по умолчанию (0,0001), программа продолжит процесс оптимизации даже при малых изменениях целевой функции.
Если установить в области Оценки переключатель квадратичная, Поиск решения будет применять для вычисления различных оценок более точную квадратичную аппроксимацию, а не линейную (по умолчанию). Кроме того, установка в области Разности переключателя центральные вместо переключателя прямые приведет к тому, что Поиск решения для вычисления частных производных будет применять более точную аппроксимацию, используя большее количество точек.
Обе эти установки улучшают вычисляемые числовые оценки функций нелинейной модели, однако могут увеличить время решения, поскольку на каждой итерации следует производить дополнительные вычисления.
В диалоговом окне Параметры поиска решения можно также задать метод поиска решения. Метод сопряженных градиентов в процессе оптимизации использует меньше памяти, но требует большего количества вычислений, при заданном уровне точности, чем заданный по умолчанию метод Ньютона.
Значение в поле Относительна погрешность, определяет, на сколько точно должно совпадать вычисленное значение левой части ограничения со значением правой части, чтобы данное ограничение было выполнено.
Команда Выполнить запускает решение задачи. Поиск решения просит уточнить: сохранить ли найденное решение или нет.
Рекомендации по поиску решения задач.
При задании в диалоговом окне Поиска решения правых частей ограничений всегда следует указывать ссылки на ячейки в табличной модели.
Ячейки в правых частях неравенств в табличной модели должны содержать константы, а не формулы.
Примеры решения задач
Задача № 1
Производственная задача
Постановка задачи.
Предприятие производит продукцию n (5) видов при этом используя сырье m (3) типов. Расход каждого типа сырья на производство изделий представлен таблицей:
Таблица 2.1.
Производство обеспечено сырьем каждого типа в количестве (4300) у.е., (3450) у.е. и (4360) у.е. Рыночная цена единицы составляет (12) д.е., (15) д.е., (14) д.е., (16) д.е., (15) д.е..
Составить план производства изделий, обеспечивающий максимальную выручку от их реализации.
Экономико-математическая модель.
Исходя из условия, делается вывод о том, что эта задача является задачей линейного программирования.
Обозначим за неизвестные переменные (i =1….5) объем производства соответствующих изделий.
Значения таблицы 3.1. представляют собой матрицу с коэффициентами (). Где i – номер строки, j – номер столбца (например, ).
В общем виде система ограничений имеет вид:
С учетом значений задачи получаем.
Дополнительные ограничения:
, , , , .
Необходимо найти оптимальный план выпуска продукций (т.е. ), который обеспечит максимальную выручку. Пусть f – выручка от реализации продукций. Тогда
В общем виде целевая функция примет вид:
,
где – рыночные цены соответствующих изделий (i =1….5);
– объем производства соответствующих изделий.
Исходя из условий задачи:
Для некоторых производственных задач целесообразно найти оптимальный план производства, содержащий целые значения. Поэтому в дополнительные ограничения следует добавить: (i =1….5).
Табличная модель.
Модель производственной задачи состоит из трех таблиц: таблицы ограничений и расхода сырья, таблицы плана выпуска (искомых переменных), таблицы прибыли. До оптимизации ячейки переменных [В11:В15] заполняются произвольным набором значений (не противоречащим ограничениям). Таким образом, задается первое приближение. Кроме того это необходимо, чтобы увидеть расчет всех ячеек, заполненных формулами.
Замечание: Важно строго следить за форматированием ячеек. Ячейки, содержащие значения и расчетные формулы должны быть отформатированы числовым (при необходимости финансовым) форматом.
Массив Расход сырья [H5:H7] рассчитывается путем умножения матрицы Вид сырья на матрицу План выпуска. Для этого необходимо выделить ячейки расход сырья, применить функцию МУМНОЖ, выделить перемножаемые массивы и одновременно нажать три клавиши: Shift, Ctrl, Enter.
Матрица Остаток рассчитывается, как [Запас сырья]−[Расход сырья]. Ячейка Е10 содержит значение целевой функции, рассчитанной как сумма произведений значений цены на план выпуска соответствующего вида продукции.
Более наглядно заполнение ячеек табличной формы задачи представлено на рисунке 2.2.
Примечание. При вводе формул используйте Мастер функций и кнопку Автосумма на Панели инструментов.
Следующим шагом необходимо скопировать значение целевой функции в любую пустую ячейку,
Замечаем, что оптимум значительно больше предыдущего значения целевой функции. Разность составляет: 18750- 7200=11550
Вывод:
Оптимальный план производства, при данных условиях, состоит в том, что продукцию 1-ого и 5-ого видов необходимо производить в объеме 750 и 650 ед. соответственно, а продукции 2- ого – 4- ого видов не выпускать в производство. При этом обеспечивается максимальная выручка в размере 18750 д.е.
Задача № 2
Оптимальная организация рекламной компании
Постановка задачи.
Предприятие рекламирует свою деятельность использованием четырех источников массовой информации: телевидения, радио, газет и расклейки объявлений. Анализ рекламной деятельности в прошлом показал, что вложенные в рекламы средства приводят к увеличению прибыли на 10, 5, 7 и 4 руб. соответственно в расчете на 1 руб., затраченный на рекламу. На рекламу выделено 50000 руб., причем руководство намерено тратить на телевидение не более 50% выделенной суммы, на радио − не более 20%, на газеты − не более 35%, на расклейку объявлений − не более 30%. Как следует предприятию организовать рекламную компанию, чтобы получить максимальную прибыль?
Экономико-математическая модель.
– средства, направленные на телевидение;
– средства, направленные на радио;
– средства, направленные на газеты;
– средства, направленные на расклейку объявлений.
Целевая функция:
Ограничения:
Табличная модель.
Ячейки [В2:В5] до оптимизации целесообразно заполнить произвольными объемами денежных средств, но с учетом того, что сумма реальных затрат, не превышает выделенные средства.
Вывод:
Для получения максимальной прибыли, предприятие, проводя рекламную компанию, должно вложить 25000 р. в рекламу на телевидении, 7500 р. – в рекламу на радио, 17500 р.– в рекламу в газетах и не вкладывать средства в рекламу в объявлениях. При этом максимальная прибыль составит 410000 руб.
Задача № 3
Задача об оптимальном назначении
Постановка задачи.
Сотрудники: Иванов, Петров, Семенов, Михайлов, Васильев, Сидоров работают на предприятии. Производительность труда сотрудников на каждой операции (с № 1 по № 6) представлена в таблице:
Таблица 2.2.
Распределить по должностям всех сотрудников так, чтобы суммарная производительность была максимальной.
Экономико-математическая модель. Данная задача является типичной моделью линейного целочисленного программирования (Ц.Л.П.), так как включает в себя двойственные ограничения на переменные (1- сотрудник назначается на должность, 0- сотрудник не назначается на должность).
– сотрудник 1.(Иванов) назначается на должность № 1;
– сотрудник 1.(Иванов) назначается на должность № 2;
– сотрудник 1.(Иванов) назначается на должность № 6;
– сотрудник 2.(Петров) назначается на должность № 1;
– сотрудник 2.(Петров) назначается на должность № 2;
– сотрудник 6.(Сидоров) назначается на должность № 1;
– сотрудник 6.(Сидоров) назначается на должность № 6.
Имеем матрицу переменных:
Целевая функция выражает суммарную производительность и имеет вид:
Ограничения:
- Матрица переменных принимает двоичное значение:
- сотрудник назначается на должность;
- сотрудник не назначается на должность.
Табличная модель.
Целевая функция находится в строке I2 Общая производительность и определяется, как сумма произведений массива Матрица производительности на массив Матрица распределения по должностям. Матрица распределения по должностям заполняется значениями 0 или 1. До оптимизации необходимо произвольно произвести назначение сотрудников.
В матрице распределения по должностям есть столбец Сумма по строкам и строка Сумма по столбцам. В дальнейшем, при оптимизации эти массивы будут участвовать в ограничении: каждая ячейка (H13:H18) и (B19:G19) равняется 1. Это необходимо для того, чтобы выполнялось условие, что на одну должность назначается только один сотрудник.
Вывод:
С учетом производительности труда всех работников по каждой операции, менеджеру необходимо назначить: Иванова на должность № 5, Петрова на должность №3, Семенова на должность №4, Михайлова на должность №6, Васильева на должность №2, Сидорова на должность №1. При этом коллектив добьется максимальной производительности – 46,6.
Задача № 4
Задача о распределении торговых агентов
Постановка задачи.
Торговая фирма продает товары в 5 (n) различных регионах, покупательская способность жителей которых оценивается в тыс. руб. соответственно (j=1, 2,…n).
Таблица 2.3.
Для реализации товаров фирма располагает 5(n) торговыми агентами, каждый из которых направляется в один из городов.
Профессиональный уровень агентов различен; доля реализуемых i-ым торговым агентом покупательных способностей составляет (i=1,2,… n).
Таблица 2.4.
Необходимо так распределить торговых агентов по регионам, чтобы получить максимальную выручку от продажи товаров.
Экономико-математическая модель.
Имеем матрицу переменных:
,
где – отправление i-ого торгового агента в j-ый регион (i, j=1…5(n))
Выражение определяет возможные продажи i-ого торгового агента в j-ом регионе.
Целевая функция описывает суммарный объем продаж.
Вывод:
На основе данных о профессионализме торговых представителей и анализе продаж в регионах с целью достижения максимального суммарного объема продаж оптимальным распределением считается следующее: Иванов реализует товар в Иловле, Петров – во Фролово, Сидоров – в Котельниково, Михайлов – в Михайловке, Демьянов – в Алексеевке. При этом достигается максимальный объем продаж в размере 1460 д.е.
Задача № 5
Транспортная задача
Транспортные задачи выделяются отдельным классом задач Л.П., к которым сводятся многие проблемы оптимизации грузопотоков и работы различных видов транспорта, а также другие вопросы организации и планирования производства.
Постановка задачи.
Задача № 1. Закрытая транспортная задача.
Имеются 3 (m) поставщика и 5 (n) потребителей. Мощность (запасы) поставщиков и спрос (потребность) потребителей, а также затраты на перевозку для каждой пары «поставщик-потребитель» сведены в таблице поставок.
Таблица 2.5.
Задача ставится таким образом: найти объемы перевозок для каждой пары «поставщик-потребитель» так, чтобы:
мощности всех поставщиков были реализованы;
спрос всех потребителей был удовлетворен;
суммарные затраты на перевозку были бы минимальные.
Существуют сбалансированные и несбалансированные транспортные задачи. Сбалансированные – суммарные мощности (запасы) поставщиков изначально равны суммарным спросам потребителей. В противном случае они называются несбалансированными. Вид транспортной задачи необходимо определить на самом первом шаге решения.
Данный пример является сбалансированной задачей. Так как суммы Потребностей и Запасов равны 700.
Несбалансированные модели необходимо свести к сбалансированным путем добавления «фиктивного» поставщика (или потребителя) с недостающим значением мощности (или спроса) и нулевыми тарифами на перевозку единицы груза. Однако, если системы ограничений имеют вид систем неравенств, то к сбалансированной модели сводить не имеет смысла.
В курсе высшей математики раздела «Прикладная математика» большое значение уделялось решению транспортных задач. Это решение базируется на создании опорного плана, где оптимальным методом его построения считается метод наименьших тарифов. Метод наименьших тарифов состоит в последовательном отыскании, на каждом шаге построения, минимального значения коэффициента затрат на перевозку единицы груза. Однако для задания первого приближения достаточно использовать более оперативный метод – метод северо-западного угла.
Экономико-математическая модель.
Искомый объем перевозки от i-ого поставщика к j-ому потребителю обозначим через . Тогда определяются ограничения для условия реализации всех мощностей:
Ограничения для удовлетворения спросов всех потребителей:
Замечание: Транспортная модель имеет специфическую форму. Все коэффициенты при переменных в ограничениях равны 1.
Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует ввести дополнительное ограничение: .
Суммарные затраты на перевозку выражаются через коэффициенты затрат и поставки и определяют целевую функцию.
Табличная модель. Массив [В4:F6] – матрица переменных. Ячейка [В19] содержит целевую функцию, определяемую, как СУММПРОИЗВ [В4:F6] на Матрицу тарифов [В15:F17].
Замечание: В таблицах 3.6. и 3.7. схематично представлена процедура сведения несбалансированной (открытой транспортной задачи) модели к сбалансированной (закрытой транспортной задачи).
Задача № 2. Открытая транспортная задача.
Таблица 2.6.
∑=700
∑=650
700-650=50
Задача № 3. Открытая транспортная задача.
Таблица 2.7.
700-680=20
∑=680
∑=700
Решение задачи № 1.
Вывод:
Минимальные суммарные затраты на перевозку груза в размере 8200 д.е. достигаются путем распределения поставок, представленных в ячейках [B4:F6]. Так, например, поставщик А2 должен поставить груз к потребителю В1 в объеме 80 ед. груза, к потребителю В2 в объеме 50 ед. груза и к потребителю В5 в объеме 120 ед. груза. К потребителям В3 и В4 ехать не надо.
Задача № 6
Распределение бюджета
Многие компании ежегодно принимают решения о капиталовложениях. В простейшей форме решение о выделении средств заключается в выборе нескольких из n вариантов капиталовложений, цель состоит в максимизации прибыли при наличии ограничений на количество средств, которые можно вкладывать.
Постановка задачи.
Совету директоров предстоит выбрать несколько вариантов из 4 (n) предложенных. Каждый проект требует выделения средств по годам. Известна также стоимость чистой прибыли от каждого проекта. Совет директоров ранее принял решение о соответствующих выделениях средств на каждый год. Значения представлены в таблице 2.8.
Таблица 2.8.
Экономико-математическая модель.
В данной модели целевая функция – это суммарная чистая прибыль, а ограничения указывают на то, что в каждом году используются средства не больше, чем имеется в наличии в каждом году.
Такая задача является двоичной моделью целочисленного линейного программирования, так как переменные дают ответ лишь на то, что принимается тот или иной проект или нет.
Пусть , если проект i принимается, и в противном случае. Следовательно, – двоичное.
Тогда целевая функция примет вид.
Это суммарная чистая прибыль.
При ограничениях
Табличная модель.
Вывод:
Согласно решению, представленному на рис. 3.24., руководству компании следует принять первые три проекта, тогда как четвертый проект отвергнуть. При этом суммарная прибыль составит 1900 тыс. руб. и будет максимальной.
Задача №7
Анализ безубыточности при наличии ограничений
Постановка задачи.
Предприятие производит 3 вида продукции: А1, А2, А3.
Соответствующие данные о затратах и доходах на ближайший плановый период представлены в таблице.
Таблица 2.9.
На Диаграмме 1. представлено определение точки безубыточности (критического объема производства) для продукции А1.
Диаграмма 1.
Как следует из графика, если компания будет производить только А1, то для того, чтобы добиться безубыточности, ей потребуется выпустить не менее 1000 ед. А1. Однако перед компанией стоит более сложная задача. Во-первых, на следующий плановый период руководство компании уже заключило контракт на производство 700 ед. А1. Во-вторых, еще один клиент заказал 400 ед. А2, и руководство заинтересовано в выполнении данного заказа. В-третьих, анализ рынка, проведенный отделом маркетинга компании, свидетельствует, что следует произвести не более 300 ед. А3. Руководство компании хочет выяснить, сколько единиц продукции надо продать, чтобы добиться безубыточности.
Экономико-математическая модель.
Начнем с общих положений: точка безубыточности характеризуется тем, что суммарный доход равняется суммарным затратам. Руководство заинтересовано в том, чтобы минимизировать расходы. Поскольку фиксированные затраты придется нести в любом случае, целью можно считать минимизацию суммарных переменных затрат.
Определим переменные решения следующим образом.
S– количество произведенных единиц А1,
R– количество произведенных единиц А2,
B– количество произведенных единиц А3.
Тогда уравнение точки безубыточности примет вид:
,
или
.
Целевая функция (суммарные переменные затраты) имеет вид
Ограничения:
Табличная модель.
Вывод:
Чтобы достичь безубыточности, исходя из условия задачи, необходимо производить 700 ед. продукции вида А1, 3718 ед. продукции вида А2 и не целесообразно производить продукцию А3, при этом минимальные суммарные переменные затраты составляют 16884,62 тыс. руб.
Задача № 8
Задача о составлении расписания
Постановка задачи.
Управляющий персоналом университета должен составить расписание охраны территории университета, удовлетворяющее требованиям, представленным в таблице 2.10.
Таблица 2.10.
|
Время |
Минимальное число офицеров охраны |
|
0.00 – 4.00 |
5 |
|
4.00 – 8.00 |
7 |
|
8.00 – 12.00 |
15 |
|
12.00 – 16.00 |
7 |
|
16.00 – 20.00 |
12 |
|
20.00 – 24.00 |
9 |
Офицеры дежурят посменно, продолжительность смены 8 ч. На каждый день установлено 6 смен. Время начала и конца каждой смены показано в таблице 3.11.Управляющий персоналом хочет определить, сколько офицеров назначить в каждую смену, чтобы минимизировать их количество и при этом удовлетворить требования к организации охраны.
Таблица 2.11.
|
Смена |
Время начала |
Время окончания |
|
1 |
0.00 |
8.00 |
|
2 |
4.00 |
12.00 |
|
3 |
8.00 |
16.00 |
|
4 |
12.00 |
20.00 |
|
5 |
16.00 |
24.00 |
|
6 |
20.00 |
4.00 |
Экономико-математическая модель.
Обозначим за – число офицеров, дежурящих в смену 1;
– число офицеров, дежурящих в смену 2;
– число офицеров, дежурящих в смену 3;
– число офицеров, дежурящих в смену 6.
Целевая функция представляет суммарное количество офицеров и имеет вид
Ограничения:
Заметим, что офицеры, дежурящие в первую смену, находятся на посту в течение первых двух временных интервалов и т.п.
Данная задача является еще одним примером, в котором переменные решения должны принимать целочисленные значения.
целое.
Табличная модель.
С учетом первого приближения (10, 10, 12, 12, 12, 10, 10) составим табличное представление модели.
Вывод:
Оптимизация показала, что минимальное количество дежурных составляет 32 человека. При этом 5 человек работают в первую смену, 11 человек во вторую, 4 человека в третью, 3 человека в четвертую и 9 человек в пяту смену. Шестой смены нет.
Задача № 9
Задача о пополнении оборудования
Постановка задачи.
Предприятие вначале пятилетнего периода выделило 4,5 млн. руб. для комплексного оборудования, стоимость единицы которого составляет 1,5 млн. руб. Единица оборудования за год приносит предприятию 0,6 млн. руб. прибыли. Необходимо разработать такую программу пополнения оборудования, чтобы суммарная прибыль от его внедрения в течение планового периода была максимальной.
Экономико-математическая модель.
Пусть – доля прибыли, идущая на закупку оборудования в i - том году. Вначале пятого года оборудование не закупается.
Ограничения:
,
– суммарная прибыль, оставшаяся у предприятия в результате использования приобретенного оборудования.
Заметим, что как в системе ограничений, так и в целевой функции зависимость от переменных представлена линейно.
Формула целевой функции несколько громоздка, однако в табличной модели она разбита на части.
Табличная модель.
Зададим первое приближение: например, в конце первого года 40% прибыли отложим на закупку оборудования, в конце второго – 30%, в конце третьего – 20% прибыли, в конце четвертого года – 10%. С учетом первого приближения получим.
Вывод:
Оптимизация показала, что для достижения максимальной прибыли за пятилетний период в объеме 10,58 млн. руб. необходимо в первый и второй годы направлять всю прибыль на приобретение оборудования. В четвертый и пятый годы закупать оборудование нецелесообразно.
Задача № 10
Задача составления смеси
Постановка задачи.
Банка корма для собак весом 16 унций должна содержать как минимум следующие количества питательных веществ: белков– 3 унции, углеводов– 5 унций и жиров – 4 унции. Нужно смешать четыре вида каш в различных пропорциях, чтобы получить наиболее дешевую банку собачьего корма, удовлетворяющую требованиям по содержанию питательных веществ. Содержание питательных веществ и цена каждой каши в расчете на 16 унций приведены в таблице.
Таблица 2.12.
|
Содержание питательных веществ и цена |
||||
|
Каша |
Содержание белков, унции |
Содержание углеводов, унции |
Содержание жиров, унции |
Цена, долл. |
|
1 |
3 |
7 |
5 |
4 |
|
2 |
5 |
4 |
6 |
6 |
|
3 |
2 |
2 |
6 |
3 |
|
4 |
3 |
8 |
2 |
2 |
Экономико-математическая модель.
Модель линейного программирования для задач по составлению корма для собак имеет следующий вид.
F– стоимость банки.
,
где – количество i – ой каши в 16-унциевой банке собачьего корма, i=1,2,3,4.
Ограничения:
Табличная модель.
Во вкладке Параметры следует указать на линейность и неотрицательность решения.
Вывод:
Самая дешевая допустимая смесь – 3$ при наличии 16,7.% каши № 2, 33, 3% каши № 3, 50% каши № 4. Кашу № 1 не добавляется в банку.
2. 000 уе Уставный капитал сформирован 800
3. технические и трудовые ресурсы производства сельскохозяйственной продукции
4. искусство ведения домашнего хозяйства совокупность общественных наук изучающих производство распред
5. Внутреннее энергообеспечение Предприятие полностью обеспечивает себя энергией из собственных энергорес
6. Стоимость строительства ТЭС любого типа может быть найдена на основе удельных капитальных вложений и мощно
7. Вас пиерийские Музы дающие песнями славу Я призываю воспойте родителя вашего Зевса Слава ль ко
8. Так як наука про економіку стала розвиватися великими темпами з недавніх пір
9. на тему Анализ дебиторской задолжности- цель задачи информационная обеспеченность Выполнена сту
10. го лица Повествование 1st Person Повествование чересстрочной переплетаются смешиваются с диалога характе
11. тематики. Он включает в себя вопервых собственно духовные начала человеческого бытия с их антиномиями отчу
12. Формат печатного издания
13. записка до проекту постанови правління Фонду соціального страхування від нещасних випадків на виробництві
14. Тема- Расчет техникоэкономических показателей по ремонту узлов и агрегатов автомобилей
15. Иллюзорный мир игр современного общества
16. Библия дошла до нас сквозь толщу веков
17. Plte cpcitor. When you pull the pltes prt to lrger seprtion nd bttery remins connected to the cpcitor Decreses The resonnt ngulr frequency of series RLC circuit
18. Який фундаментальний критерій повинен бути покладений в основу управління змістом робіт організації
19. Характер современных военных конфликтов
20. Россия и мировой рынок