Оптимизация целевой функции с помощью двухфазного симплекс методаТеоретическая часть: 1. Каков порядок решения задачи симплексным методом? 2. Какова структура симплексной таблицы? 3. Что такое опорное решение системы линейных уравнений? 4. Сформулировать алгоритм нахождения опорного решения задачи. 5. Сформулировать алгоритм нахождения оптимального решения задачи. 6. Как определяется отсутствие решения задачи линейного программирования в процессе её решения симплексным методом. Как определяется существование альтернативного оптимума в задаче линейного программирования при её решении симплексным методом? 7. Сформулировать алгоритм решения общей задачи линейного программирования. 8. Вырожденные задачи линейной оптимизации. Способы ликвидации вырожденности.
Практическая часть: 1. Цех выпускает три вида изделий. Суточный плановый выпуск: 90 ед. изделия I, 70 ед. изделия II и 60 ед. изделия III. Суточные ресурсы: 780 ед. производственного оборудования (станки, машины и т. п.), 850 ед. сырья (метал и т. п.) и 790 ед. электроэнергии. Их расход на одно изделие указан в табл.1. Стоимость изделия I – 8 ден. ед., изделия II – 7 ден. ед., изделия III – 6 ден. ед. Сколько надо производить изделий каждого вида, чтобы стоимость продукции, выпущенной сверх плана, была максимальной? Таблица 1
2. Для грузовых перевозок создается автоколонна. На приобретение автомашин выделено 600 тыс. ден. ед. Можно заказать машины трех марок – А, Б и В, характеризующиеся данными, приведенными в табл. 2. Количество машин не должно превышать 30, а общее число водителей в автоколонне должно быть не более 144 человек. Сколько автомашин каждой марки следует заказать, чтобы автоколонна имела максимально возможную производительность (т/км) в расчете на одни сутки? Считать, что каждая машина будет использоваться в течение всех трех смен, а водители будут работать по одной смене в сутки. Таблица 2
3. Найти оптимальное сочетание посевов трех культур: пшеницы, гречихи и картофеля. Эффективность возделывания названных культур (в расчете на 1 га) характеризуется показателями, значения которых приведены в табл.3. производственные ресурсы: 6000 га пашни, 5000 чел.-дней труда механизаторов, 9000 чел.-дней ручного труда. Критерий оптимальности – максимум прибыли. Таблица 3.
4. Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 450 тыс. л бензина прямой перегонки и 200 тыс. л изопентона. В результате смешения этих четырех компонентов в отношении 2: 3: 5: 2 образуется бензин А стоимостью 120 ден.ед. за 1 тыс. л; в отношении 3: 1: 2: 1 – бензин Б стоимостью 100 ден.ед. за 1 тыс.л; в отношении 2: 2: 1: 3 – бензин В стоимостью 150 ден.ед. за 1 тыс.л. Составить план, при котором стоимость всей выпущенной продукции будет максимальной.
5. Для изготовления обуви четырех моделей на фабрике используются два сорта кожи. Ресурсы рабочей силы и материала, затраты труда и материала для изготовления каждой пары обуви, а также прибыль от реализации единицы продукции приведены в табл. 4. Составить план выпуска обуви по ассортименту, максимизирующий прибыль. Таблица 4.
6. Автопогрузчики АП-1 и АП-2 заняты работами на площадках П1 и П2. Не более чем за 24 ч на площадке П1 необходимо погрузить 230 т груза, на площадке П2 – 168 т. Количество груза, которое может погрузить каждый автопогрузчик за один час на той или иной площадке, а также стоимость погрузки одной тонны груза приведены в табл. 5. Установить, сколько тонн должен погрузить каждый автопогрузчик на той или другой площадке так, чтобы своевременно выполнить задание с минимальными затратами. Таблица 5.
7. Производственные участки У1 и У2 получили заказ на изготовление 32 изделий И1 и 4 изделий И2. Производительность участков по изделиям и фонд рабочего времени участков приведены в табл.6, а затраты, связанные с производством единицы каждого изделия, - в табл.7. Найти оптимальный план размещения заказа по участкам, минимизирующий затраты, при условии, что фонд рабочего времени участка У2 будет использован полностью. Таблица 6. Таблица 7.
8. Из листов стального проката размером 6× 13 м необходимо выкроить 800 заготовок А размером 4× 5 м и 400 заготовок Б размером 2× 3 м. Раскрой можно производить четырьмя способами. В табл.8 указано количество заготовок каждого типа, получаемых при раскрое одного листа различными способами. Составить такой план раскроя, чтобы расход материала был минимальным. Таблица 8
9. Имеющийся фонд материалов Мi (i= Таблица 9.
10. Предприятие может выпускать продукцию П1, П2, П3, и П4, сбыт любого количества которой обеспечен. При производстве продукции расходуются различные ресурсы, запасы которых и удельные затраты приведены в табл.10, там же указана и цена продукции. Найти оптимальный план выпуска продукции, максимизирующий выручку предприятия от реализованной продукции. Таблица 10.
11. На предприятии освоены четыре технологии производства основной продукции. В табл.11 указаны запасы потребляемых ресурсов, затраты их в течение месяца и объемы выпуска готовой продукции при каждой технологии за тот же период. Установить такое время работы предприятия по каждой технологии, при котором выпуск продукции будет максимальным, а расход ресурсов не превысит их наличия. Таблица 11.
12. На приобретение оборудования для нового производственного участка выделено 30 тыс. ден.ед. и помещение площадью в 45 м2. Участок может быть оснащен машинами трех типов, характеристики которых приведены в табл.12. Найти оптимальный план приобретения машин, обеспечивающий новому производственному участку максимальную производительность. Таблица 12.
13. Торговое предприятие реализует товары Т1, Т2 и Т3, используя при этом площади торговых залов и время обслуживающего персонала. Затраты указанных ресурсов на продажу одной партии товара каждого вида, их объемы и прибыль, получаемая от реализации каждой партии товара, приведены в таб.13. Найти оптимальную структуру товарооборота, обеспечивающую предприятию максимальную прибыль. Таблица 13.
14. Механический завод при изготовлении деталей Д1 иД2 использует токарное, фрезерное и сварочное оборудование. Обработку деталей можно вести по технологиям I и II. Полезный фонд времени работы каждой группы оборудования (в станко-часах), затраты времени изготовления детали (в часах) и прибыль от выпуска каждой детали приведены в табл.14. Составить оптимальный план загрузки оборудования, обеспечивающий заводу максимальную прибыль. Таблица 14.
15. Имеются два проекта на строительство жилых домов. Расход стройматериалов, их запас и полезная площадь дома каждого проекта приведены в табл.15. Определить, сколько домов первого и второго проекта следует построить, чтобы полезная площадь была наибольшей. Таблица 15.
16. Сельскохозяйственное предприятие может приобрести тракторы марок М1 и М2 для выполнения работ Р1, Р2 и Р3. Производительность тракторов при выполнении указанных работ, общий объем работ и стоимость каждого трактора приведены в табл.16. Найти оптимальный вариант приобретения тракторов, обеспечивающий выполнение всего комплекса работ при минимальных денежных затратах на технику. Таблица 16.
17. На заготовительный участок поступили стальные прутья длиной 111 см. Необходимо разрезать их на заготовки по 19, 23 и 30 см, которых требуется соответственно 311, 215 и 190 шт. Построить модель, на основе которой можно решить задачу выбора варианта выполнения этой работы, при котором число разрезаемых прутьев минимально.
18. На заготовительный участок поступило 69 металлических прутьев длиной 107 см. Их необходимо разрезать на заготовки по 13, 15 и 31 см в комплектности, задаваемой отношением 1: 4: 2. Построить модель, на основе которой можно сформулировать задачу максимизации комплектов заготовок. Найти оптимальный план.
19. На заготовительный участок мебельной фабрики поступили листы фанеры размерами 152× 152 см. Необходимо разрезать их на заготовки по 105× 31, 47× 90 и 30× 51 см. Потребность в них – соответственно 315, 215 и 416 шт. Построить модель, на основе которой можно сформулировать задачу выбора варианта раскроя, при котором количество разрезаемых листов минимально.
20. На заводе ежемесячно скапливается около 14 т отходов металла, из которого можно штамповать большие и малые шайбы. Месячная потребность завода в больших шайбах – 600 тыс. шт., в малых – 1100 тыс. шт. (недостающее количество шайб закупается на специализированном предприятии). Оптовая цена больших шайб – 1, 9 ден.ед. (за тысячу штук), малых – 5, 2 ден.ед. Расход металла на тысячу больших шайб – 22 кг, на тысячу малых – 8 кг. Для изготовления шайб используются два пресса холодной штамповки. Производительность каждого за смену – 9 тыс. шт. больших шайб либо 11, 5 тыс. шт. малых. Завод работает в две смены. Построить модель, на основе которой можно решить задачу определения плана производства шайб (из отходов), обеспечивающего максимальную долю в валовой продукции предприятия. За плановый период принять год. Найти оптимальный план.
21. Предприятие изготавливает приборы типа А, В и С, которые реализует соответственно по 6000, 7000 и 11500 ден.ед. за изделие. Трудоемкость их производства задана отношением 1: 2: 3. Ранее предприятие изготавливало только прибор типа А в количестве 900 шт. за сутки. Однако изменение объема поставок экранированного провода (при сборке приборов каждого типа расходуется одинаковое количество этого материала) в планируемом году позволит выпускать за сутки 1000 приборов. Для укомплектования каждого прибора необходим датчик того же типа, что и тип прибора. Их предполагается получать по кооперированным поставкам в количестве, обеспечивающем в сутки сборку не более 400, 500 и 200 приборов типа А, В и С соответственно. Построить модель, на основе которой можно решить задачу определения напряженных месячных планов по объему реализации и ассортименту выпускаемой продукции. Найти оптимальные планы.
22. Предприятие располагает ресурсами сырья трех видов: С1, С2, С3. Используя это сырье, оно выпускает четыре вида продукции: П1, П2, П3 и П4. В таблице указаны затраты каждого вида и объем ресурсов сырья. Прибыль получаемая от реализации 1 тонны продукции равна: П1 - 48, П2 - 25, П3 – 56, П4 – 30. Определить ассортимент выпускаемой продукции, при котором прибыль будет максимальной, при условии, что продукции П2 необходимо выпустить не менее 8 т, продукции П4 не более 5т, а продукции П1 и П3 в отношении 3: 1. Таблица 17
23. Фабрика выпускает кожаные брюки, куртки и пальто специального назначения в ассортименте, заданном отношением 2: 1: 3. В процессе изготовления изделия проходят три производственных участка: дубильный, раскройный и пошивочный. Фабрика имеет практически неограниченную сырьевую базу, однако сложная технология предъявляет высокие требования к квалификации рабочих. Время обработки изделий на каждом участке, их плановая себестоимость, оптовая цена предприятия приведены в табл.18 Таблица 18
Ограничения на фонд времени для дубильного, раскройного и пошивочного участков составляют соответственно 3360, 2688 и 5040 ч. Учитывая заданный ассортимент, построить модель, на основе которой можно сформулировать задачу определения напряженного месячного плана по прибыли от реализованной продукции. Найти оптимальный план.
24. В сплав может входить не менее 4% никеля и не более 80% железа. Для составления сплава используются три вида сырья, содержащего никель, железо и прочие вещества. Стоимость различных видов сырья и процентное содержание в нем соответствующих компонентов сплава представлены в табл. Определить состав шихты таким образом, чтобы стоимость 1 кг сплава была минимальной. Таблица 19
25. Металлургический цех выпускает три вида продукции: А, Б и В. Прибыль от тонны производственной продукции каждого вида составляет соответственно 35, 25 и 40 ден.ед. Цех располагает необходимым оборудованием, каждый тип которого имеет свой фонд рабочего времени и производительность (табл.). Составить план выпуска продукции, обеспечивающий максимум прибыли. Таблица 20
26. Предприятию задан план производства по времени и номенклатуре: требуется не более чем за 6 единиц времени выпустить 30 единиц продукции П1 и 96 единиц продукции П2. Каждый из видов продукции может производиться машинами А и Б, значения мощностей которых и затраты, вызванные изготовлением каждого из видов продукции на той или иной машине, заданы табл.. Требуется составить оптимальный план работы машин, а именно: найти, сколько времени каждая из машин А и Б должна быть занята изготовлением каждого из видов продукции П1 и П2, чтобы стоимость всей продукции предприятия оказалась минимальной и в то же время был бы выполнен заданный план как по времени, так и по номенклатуре. Таблица 21
27. Сельскохозяйственное предприятие отвело три земельных массива площадью в 5000, 8000 и 9000 га под посевы ржи, пшеницы и кукурузы. Средняя урожайность по массивам указана в табл.. За 1ц ржи предприятие получает 2 ден.ед. прибыли, за 1ц пшеницы – 2, 5 ден.ед., за 1ц кукурузы -1, 4 ден.ед.. Сколько гектаров и на каких массивах следует отвести под каждую культуру, чтобы получить максимальную прибыль, если по плану необходимо сдать не менее 1900т ржи, 15 800т пшеницы и 30 000т кукурузы? Таблица 22
28. Три типа самолетов следует распределить между двумя авиалиниями. В табл. Заданы количество самолетов каждого типа, месячный объем перевозок каждым самолетом на каждой авиалинии и соответствующие эксплуатационные расходы. Требуется распределить самолеты по авиалиниям так, чтобы при минимальных суммарных эксплуатационных расходах перевезти по каждой из них соответственно не менее 300 и 200 ед. груза. Таблица 23
29. Завод производит два вида продукции: велосипеды и мотоциклы. При этом цех по сборке велосипедов имеет мощность 100 тыс. шт. в год, цех по сборке мотоциклов – 30 тыс. шт. в год. Механические цеха завода оснащены взаимозаменяемым оборудованием, и одна группа цехов может производить либо детали для 120 тыс. велосипедов, либо детали для 40 тыс. мотоциклов, либо любую комбинацию, ограниченную этими данными. Другая группа механических цехов может выпускать детали либо для 80 тыс. велосипедов, либо для 60 тыс. мотоциклов, либо любую допустимую их комбинацию. В результате реализации каждой тысячи велосипедов завод получает прибыль в 2 тыс. ден.ед., а каждой тыс. мотоциклов – 3 тыс. ден.ед.. Найти такое сочетание объемов выпуска продукции, которое даст наибольшую сумму прибыли.
30. На кондитерской фабрике весь ассортимент выпускаемой карамели разделен на три однородные группы, условно обозначенные К1, К2, К3. Расход основного сырья и его запас указаны в таблице. Другие виды сырья, входящие в готовый продукт в небольших количествах, не учитываются. Составить план выпуска продукции, обеспечивающий максимум прибыли.
Таблица 24
|
) нужно распределить между изготовителями продукции Пj (j= 
) так, чтобы получить максимальную прибыль от реализации всей продукции, произведенной из имеющихся материалов. Нормы расхода на единицу продукции, запас материалов и прибыль, получаемая от реализации единицы готовой продукции, приведены в табл.9.
