Лекция: Пример реализации приложения

Приведем пример приложения для решения задачи симплекс-методом. В приложении приняты следующие обозначения: G – количество ограничений вида >= в системе ограничений, Е – количество ограничений вида = в системе ограничений, L — количество ограничений вида <= в системе ограничений, N – количество неизвестных, Esp – требуемая точность (допустимая погрешность). Всего в задаче M=G+E+L ограничений. Ниже запишем целевую функцию Z. В задаче N неизвестных величин X. Числа: а1,1 a1,2 и т д, т.е. коэффициенты матрицы А, а также числа: b1, b2, — вектор правой части системы неравенств, и числа: c1, c2,… — коэффициенты при неизвестных целевой функции – известны. Нужно найти такие значения (ПОЛОЖИТЕЛЬНЫЕ) неизвестных Х, чтобы все М ограничений были выполнены, и целевая функция Z имела минимальное значение. Если Вам требуется решить задачу, в которой целевая функция максимальна, просто умножьте коэффициенты при целевой функции на -1. Максимум Вашей целевой функции будет равен (со знаком минус) минимуму этой «исправленной» целевой функции. В процессе решения задачи, программа выполняет две проверки полученного решения: проверку допустимости решения и проверку оптимальности решения. Допустимость решения несложно проверить матричным умножением, а оптимальность – просмотром теневых цен и остатков ресурсов. Решение осуществляется модифицированным симплекс-методом (рисунок 15).

Рисунок 15 – Главное окно программы решения задач

симплекс-методом

Результаты решения выводятся на форме «Таблица результатов» (рисунок 16). Форма содержит разделы: «Решение», «Значение целевой функции», «Расход ресурсов и анализ ограничений».

Рисунок 16 – Форма «Таблица результатов»

Весь процесс решения задачи при помощи данного приложения состоит из нескольких этапов:

1. Записываем исходный текстовый файл с данными с расширением *.dat. (Для создания такого файла проще всего использовать «Блокнот» ОС Windows).

2. Запускаем исходный файл программы и выбираем пункт меню «Файл\Открыть».

3. Открываем исходный файл и нажимаем кнопку «Решить».

4. После появления сообщения «Решение задачи окончено», выбираем пункт меню «Результаты», в котором отображаются результаты решения задачи.

5. Возможен вывод отчетной документации. Для этого предназначена кнопка «Текстовый отчет» (рисунок 17).

Рисунок 17 – Пример отчетной информации о решении задачи

Варианты задания к курсовой работе

Вариант № 1.Компания производит два вида телевизоров – «Астро» и «Космо». Имеются две производственные линии, каж­дая для своего типа телевизоров. Мощность линии по производ­ству «Астро» составляет 70 телевизоров в день, а «Космо» – 50 единиц в день. Цех А производит телевизионные трубки. В этом цехе на производство одной трубки к телевизору «Астро» требуется потратить 1,8 чел/ч, а на производство трубки к «Космо» – 1,2 чел/ч. В настоящее время в цехе А на производство трубок к обеим маркам телевизоров может быть затрачено не более 120 чел/ч в день. В цехе Б производятся шасси. В этом цехе на производство одной единицы шасси как к телевизору «Астро», так и к «Космо» требуется затратить 1 чел/ч. В цехе Б на производство шасси к обеим маркам телевизоров может быть затрачено не более 90 чел/ч. Продажа каждого телевизора марки «Астро» обеспечивает полу­чение прибыли в размере 150 тыс. руб, а марки «Космо» – 200 тыс. руб. Спрограммировать информационную систему, позволяющую определить ежеднев­ный план производства телевизоров определенной марки, а также моделирующую увеличение прибыли, с учетом возрастания в цехе чел/ч.

Вариант № 2.Чулочно-носочная фирма производит и продает два вида то­варов. Фирма получает прибыль в размере 12 тыс. руб от производства и продажи каждой единицы товара 1 и в размере 4 тыс. руб от производства и продажи каждой единицы товара 2. Фирма состоит из трех подразделений. Затраты труда (чел/дни) на производство этих товаров в каждом из подразделений указаны в таблице.

Руководство рассчитало, что в следующем месяце фирма бу­дет располагать следующими возможностями обеспечения произ­водства трудозатратами: 800 чел-дней в подразделении 1, 600 – в подразделении 2 и 2000 – в подразделении 3. Спрограммировать информационную систему, позволяющую определить максимальную прибыль фирмы (тыс. руб), и определяющую на сколько увеличится прибыль, если объем использования трудовых ресурсов в каждом из подразделений возрастет на X %.

Вариант № 3.Мастер Гамбс – владелец небольшого мебельного цеха. Он производит три типа столов: А, Б, и В. Каждая модель стола тре­бует определенных затрат времени на выполнение трех операции производства заготовок, сбора заготовок и покраски. Мастер име­ет возможность продать все столы, которые он производит. Более того, модель В может быть продана и без покраски. Мастер Гамбс нанимает несколько рабочих, которые работают у него по совме­стительству, так что количество чел/ч, отводимое на каждый вид работ, изменяется от месяца к месяцу. Используйте данные таб­лицы и постройте программную модель линейного программирования, которая помогла бы мастеру найти такую программу выпуска продукции, которая максимизировала бы его прибыль в каждом следующем месяце. Предполагается, что по каждому виду работ возможны трудозат­раты до X чел/ч.

Определите, какую максимальную прибыль может получить мастер Гамбс (тыс. руб) и следует ли продавать неокрашенные столы типа В, а также на сколько увеличится прибыль, если объем использования трудовых ресурсов на каждой работе возрастет на Х %.

Вариант №4.Совхоз закупает корма трех видов. Цены на корма разные. В кормах содержатся питательные вещества четырех видов. Требует­ся так составить кормовой рацион, чтобы в нем содержалось не­обходимое количество питательных веществ и затраты на покупку кормов были минимальными. Данные приводятся в таблице.

Разработать программу, определяющую, какое количество корма вида В2 следует закупить и какое общее количество кормов следует закупить, также каковы будут минимальные затраты на покупку кормов (тыс. руб.).

Вариант № 5.В аптеке продается семь наименований поливитаминов. Каж­дое наименование содержит витамины трех различных типов. Цены на витамины различны. Необходимо пройти профилактический курс, в течение которого с минимальными суммарными затрата­ми получить 100 единиц витамина А, 80 – витамина С и 120 еди­ниц витамина В6. Необходимое количество поливитаминов поку­пается одновременно.

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

Вариант № 6.Из 500 листов железа первого размера и 300 листов железа второго размера несколькими способами выкраиваются три вида деталей. Даны нормы одновременного выхода деталей по различ­ным способам.

Разработать программу, позволяющую определить максимальное число комплектов деталей, если комплект состоит из четырех деталей вида 1, трех деталей вида 2 и двух деталей вида 3. Определить, сколько листов железа размера 2 раскраивается по первому способу, каково максимальное количество комплектов, на сколько изменится максимальное количество комплек­тов, если в комплект решено добавить третью деталь вида 3?

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

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

Вариант № 8.На производство поступила партия стержней длиной 250 и 190 см. Необходимо получить не менее 470 отрезков по 45 см и не менее 450 отрезков по 80 см. Разработать информационную систему, определяющую, как разрезать имеющиеся стержни, чтобы сократить до минимума отходы, какое количество стержней длиной 190 см надо разрезать, какова величина отходов после раскроя (см), может ли увеличение потребности в стержнях длиной 80 см привести к сокращению отходов?

Вариант № 9. Завод заключил договор на поставку комплектов отрезков стер­жней длиной по 18, 23 и 32 см. Причем количества отрезков раз­ной длины в комплекте должны быть в соотношении 1:5,3. На сегодняшний день имеется 80 стержней длиной 89 см. Разработать информационную систему, позволяющую определить, как их сле­дует разрезать, чтобы количество комплектов было максималь­ным, сколько комплектов стержней будет выпущено и какова при этом величина отходов (см)?

Задача № 10.Президент фирмы Г. Альба заключил контракт на покупку зе­мельного участка стоимостью 900 млн руб. В соответствии с услови­ями контракта задаток в размере 200 млн руб необходимо уплатить через два месяца, а остальное – через шесть месяцев, когда уча­сток будет освобожден прежним владельцем. Чтобы расплатиться полностью, Альба решил образовать це­левой фонд, который предполагает использовать для инвестиций, чтобы получить проценты и вовлечь их в сумму, которую следует уплатить продавцу земли. Возможности инвестирования представ­лены в следующей таблице.

Разработать информационную систему, позволяющую составить модель линейного программирования для решения данной задачи, при данных возможностях инвестирования и требуемом графике выплат, разработать стратегию вложений, минимизирующую наличную сумму, которую Г. Альба должен иметь в самом начале для выплаты всех денег по заключенному контракту. При разработке этой стратегии Г. Альба должен быть уверен, что в течение каждого месяца средний индекс риска ин­вестированных фондов не будет превышать 6. В начале каждого месяца средняя продолжительность погашения ин­вестированных фондов не должна превышать 2,5 месяца. Определить, какой размер целевого фонда следует иметь без учета риска и продолжительности погашения инвестиций (тыс. руб), следует ли в этом случае делать инвестиции вида А (на ме­сяц 1), какой размер целевого фонда следует иметь с учетом риска, но без учета продолжительности погашения инвестиций (тыс. руб) и какой размер целевого фонда следует иметь с учетом риска и продолжительности погашения инвестиций (тыс. руб)?

Вариант № 11. Лихтеровоз может принять на борт до 2100 стандартных кон­тейнеров. В порту отгрузки находятся 1500 контейнеров с продо­вольственными товарами, 1300 контейнеров с бытовой техникой, 1200 контейнеров с продукцией производственного назначения. Прибыль от реализации одного контейнера соответственно: 4,8, 5,8; 7,9 млн руб Удельные затраты на перевозку соответственно 35, 40, 50 тыс. руб. На перевозку можно затратить до 80 млн руб. Эта сумма не учитывается в прибыли от реализации продукции. Спроектируйте информационную систему, позволяющую определять максимальную прибыльность рей­са. Предложите вариант загрузки лихтеровоза. Возможно, что фирме придется заплатить 5 млн руб за хране­ние одного неперевезенного контейнера с продовольственными товарами, 1 млн руб за хранение одного контейнера с бытовой тех­никой или с продукцией производственного назначения. Каков вариант загрузки следует принять в этом случае? Какую максимальную прибыль можно получить в случае, если штрафных санкций не будет (млн руб)? Какая должна быть минимальная величина прибыли от реализации одного контейнера (млн р.) с продуктами питания, что­бы стала выгодна их перевозка? Какую максимальную прибыль можно получить в случае, если придется платить за хранение неперевезенных контейнеров (млн руб)?

Вариант № 12. Завод заключил договор на поставку своему смежнику метал­лических заготовок для производства комплектов деталей. Детали выполняются по индивидуальному заказу, масштабы производства строго оговорены, и сверхплановая продукция оплачена не будет. Приоритетным является комплектность заказа. Заготовки представляют собой отрезки стержней по 20, 23, 26 см. В наличии имеется 120 стержней длиной 92 см. Договор зак­лючен на 50 комплектов. Каким образом должно быть организова­но производство заготовок, чтобы потребности смежника были бы удовлетворены в наибольшей степени? Какое максимальное количество комплектов можно произве­сти из имеющегося материала?

Вариант № 13. Запасы топлива в районе для трех комбинатов — главных по­требителей тепла – составляют: нефть – 200 тыс. т, уголь – 100 тыс. т, газ – 8 млн м3. Удельная теплоотдача видов топливо нефть – 3 усл. ед. /т, уголь – 2 усл. ед. /т, газ – 2,5 усл. ед./100 м. Комбинаты выпускают три типа железобетонных панелей (по одному типу на каждом комбинате) для строительства жилых домов. Строительный трест разместил на комбинатах заказ на производ­ство 150 комплектов панелей. Типовой проект предусматривает использование комплектующих в количествах 400:300:600. Удель­ная теплоемкость продукции: первый комбинат – 3 усл. ед. /шт, второй – 4, третий – 3,5. В процессе производства используются цемент и металлическая арматура. Удельные расходы этих ресур­сов по типам панелей составляют: цемент — 3, 2,3, 2,5 т/шт арматура – 0,8, 0,9, 1,2 т /шт. Данные ресурсы поступают от од­ного поставщика в количествах: цемент – 500 тыс. т, арматура 190 тыс. т. Прибыль комбинатов от реализации 1 ед. продукции 1204, 870, 931 тыс. руб. Трест согласен закупать и сверхплановую продукцию. Требуется составить план производства панелей на комбинатах. Критерии: максимальное число комплектов и макси­мальная прибыль. Постройте множество парето-оптимальных то­чек. Чему равно максимальное количество комплектов? Какова максимальная прибыль (млн. руб)? Сколько крайних точек содержит граница Парето?

Вариант № 14. Фирма «Мондодыр» оценила спрос на производимый ею лосьон для каждого из четырех следующих месяцев: 100 ящиков в июне, 140 ящиков в июле, 170 ящиков в августе и 90 ящиков в сентябре. Без использования сверхурочного времени фирма может производить до 125 ящиков лосьона в месяц. В сверхурочное время может быть произведено еще 25 ящиков в месяц, но производство каждого ящика обходится при этом на 100 тыс. руб дороже. Хранение одного ящика в течение месяца обходится в 80 тыс. руб. Используя модель транспортной задачи, определите, сколько ящиков лосьона следует производить ежемесячно, чтобы удовлет­ворить спрос с минимальными совокупными затратами. Сколько ящиков лосьона следует произвести в июне? Сколько ящиков лосьона следует произвести в августе?

Вариант № 15. Справочная университетской библиотеки получает запросы, поступающие по пуассоновскому закону со скоростью в среднем 10 запросов в час. Время обслуживания распределено экспонен­циально, скорость обслуживания – 12 запросов в час. Определите: вероятность того, что в системе нет запросов; среднее число запросов в очереди; среднее время ожидания; среднее время, которое запрос проводит в системе; вероятность того, что запросу придется ждать обслуживания.

Вариант № 16. Грузовики, прибывающие на обслуживание в порт, образуют одноканальную очередь. Их прибытие распределено по закону Пу­ассона. Время погрузки/разгрузки распределено экспоненциально. Средняя скорость прибытия – 12 грузовиков в день, обслужива­ния – 18 грузовиков в день. Определите: вероятность того, что в системе нет грузовиков; среднее число грузовиков в очереди; среднее время ожидания; вероятность того, что прибывающему грузовику придется ждать обслуживания.

Вариант № 17. Контора принимает обрабатываемые единственным клерком заказы, поступающие по закону Пуассона со средней скоростью 6 заказов в день. Время на их обработку распределено экспонен­циально со средним уровнем обслуживания 8 заказов в день. Опре­делите: среднее число заказов в системе; среднее время ожидания начала обработки заказа клерком; среднее время, которое заказ проводит в системе.

Вариант № 18. Механики компании «Автосервис» прибывают на главный склад за запчастями со средней скоростью 4 механика в 1 мин. Сейчас на складе один работник. Каждый механик в среднем ждет обслуживания 4 мин. Найдите: среднее число клиентов в системе; среднее время обслуживания одного клиента в системе; среднее число клиентов в очереди. Опыт использования двух работников на складе показал, что время ожидания механиком своей очереди снизилось до 1 мин. Определите для двухканальной системы: среднее число клиентов в системе; среднее время обслуживания одного клиента в системе; среднее число клиентов в очереди. Механик получает 20 тыс. руб /ч, а работник отдела запчастей – 12 тыс. руб в час. Какая из двух (одноканальная или двухканальная) систем более экономична?

Вариант № 19. Мастерская занимается авторемонтом. Процесс прибытия опи­сывается законом Пуассона со средней скоростью 2 автомашины за восьмичасовой рабочий день. Время выполнения работ распре­делено по нормальному закону со средним 3,2 ч и среднеквадратическим отклонением 2 ч. Учитывая, что система одноканаль­ная, разработайте информационную систему, позволяющую определить: какова средняя скорость прибытия, выраженная в количе­стве автомобилей в час, какова средняя скорость обслуживания, выраженная в ко­личестве автомобилей в час, чему равно среднее число автомобилей в очереди, чему равно среднее время ожидания, какой средний промежуток времени между прибытием авто­мобиля и завершением ремонта, какую часть рабочего времени система занята (т.е. в системе есть хотя бы одно требование)?

Вариант № 20. Пять узлов на сети, представленной ниже, отражают точки во времени, с первого по четвертый год. Каждый узел означает вре­мя, когда принимается решение: оставить или заменить компью­терное оборудование. Если принимается решение заменить обору­дование, то одновременно должно быть принято и решение, как долго это оборудование предполагается использовать. Дуга от узла 0 к узлу 1 означает решение сохранить имеющееся оборудование до конца первого года, а в конце года заменить его. Дуга от узла 0 до узла 2 означает решение сохранять имеющееся оборудование в течение двух лет и заменить его в конце второго года. Числа над дугами показывают суммарные затраты, связанные с решением о замене оборудования. Эти затраты включают в себя дисконтиро­ванную цену на оборудование, текущие затраты, затраты на ре­монт и т.д. Определите политику замены оборудования с мини­мальными затратами на четырехлетний период. Каковы минимальные затраты на замену оборудования? Следует ли проводить замену оборудования в году 1?

Список литературы

1. Вентцель Г.С. Исследование операций. − М.: Дрофа, 2006

2. Математические методы и модели исследования операций. − М.: Юнити, 2008.

3. Токарев В.В., Соколов А.В. Методы оптимальных решений. Общие положения. Математическое программирование. – М.: Физматлит, 2011 – 564 с.

4. Алексеев В.М. Сборник задач по оптимизации. – М.: Физматлит, 2011. – 256 с.

5. Карманов В.Г. Математическое программирование. – М.: Физматлит, 2010. – 264с.

6. Измаилов А.Ф., Солодов М.В. Численные методы оптимизации: учеб. пособие – 2-е изд., перераб. и доп. – М.: Физматлит, 2008. – 320с.

7. Балдин К.В., Брызгалов Н.А., Рукосуев А.В. Математическое программирование. – М.: Дашков и К°, 2010. – 220с.

8. Акулич И.Л. Математическое программирование в примерах и задачах: учебное пособие. – СПб.: Лань, 2009. – 352с.

9. Просветов Г.И. Методы оптимизации: задачи и решения. – М.: Альфа-Пресс, 2009. – 168с.

10. Ерзин А.И. Введение в исследование операций: учеб. пособие. Новосибирск: НГУ, 2006.

11. Гончаров Е.Н., Ерзин А.И., Залюбовский В.В. Исследование операций. Примеры и задачи: учеб. пособие. – Новосибирск: НГУ, 2005.

12. Гимади Э.Х., Глебов Н.И. Математические модели и методы принятия решений: учеб. пособие. – Новосибирск: НГУ, 2008. – 163 с.

13. Глухов В.В., Медников М.Д., Коробко С.Б. Математические методы и модели для менеджмента. — СПб.: Лань, 2000. – 480 с.

14. Акулич И.Л. Математическое программирование в примерах и задачах: учеб. пособие – 2-е изд., испр. и доп. – М.: Высш. шк.,1993. – 336 с.

15. Ашманов С.А. Линейное программирование. – М.: Наука, 1981.

16. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч. 1. Общие задачи. – Минск: Изд-во БГУ им. В.И. Ленина, 1977. — 176 с.

17. Габасов Р., Кириллова Ф.М. Методы линейного программирования. Ч. 2. Транспортные задачи. – Минск: Изд-во БГУ им. В.И. Ленина, 1977. — 240 с.