Математики Линейное программирование. Симплекс метод Индивидуальные задания и методические указания к модулю 18 Курск 2010



Дата06.06.2016
Размер0.56 Mb.


МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение

высшего профессионального образования «Юго-Западный государственный университет»

(ЮЗГУ)


Кафедра высшей математики

Линейное программирование. Симплекс-метод

Индивидуальные задания и методические указания к модулю 18

Курск 2010



УДК 519.863
Составители Е.В.Журавлева, Н.А.Епишева

Рецензент

Кандидат физико-математических наук, доцент кафедры

высшей математики Беседин Н.Т.

Линейное программирование. Симплекс-метод: Индивидуальные задания и методические указания к модулю 18 / Юго-Зап. гос. ун-т; сост.: Е.В.Журавлева, Н.А.Епишева. Курск, 2010. 40 с. табл. 26. Библиогр.: 4 назв.

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

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

Текст печатается в авторской редакции


Подписано в печать _______ . Формат 60х84 1/16.

Усл. печ. л. . Уч.-изд. л. .Тираж 50 экз. Заказ. Бесплатно.

Юго-Западный государственный университет.

305040 Курск, ул. 50 лет Октября, 94.

Содержание








  • Введение

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

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

Решение задач модуля «Линейное программирование. Симплекс-метод» направлено на выработку следующих навыков и умений:

- уметь составлять математические модели простейших экономических задач;

- уметь приводить задачу линейного программирования к каноническому виду;

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

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

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

Обозначения, используемые в методической разработке:

n – номер варианта, который соответствует номеру по порядку в списке группы.

Теоретическое упражнение выбирается по следующему правилу: m = mod(n, 14) + 1, где mod(n,q) – остаток от деления номера варианта n на число q.



  • 1. Теоретические упражнения

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



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





где - заданные постоянные величины и .

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

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



m = 1. Известно, что точки А(23, 8, 24), В(3, 2, 4), С(5, 5, 24) являются оптимальными решениями некоторой задачи линейного программирования. Докажите, что точка М(7, 4, 14) также является оптимальным решением этой задачи.

m = 2. Пусть - оптимальные решения задачи линейного программирования: при . Докажите, что отрезок целиком состоит из оптимальных решений данной задачи.

m =3. Приведите пример задачи линейного программирования ( ) при , область допустимых значений которой содержит какие-нибудь три точки, не лежащие на одной прямой. Может ли множество оптимальных решений задачи совпадать с точкой К(1, 2).

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

m = 5. Известно, что точки А(7, 9, 7), В(3, 2, 5), С(1, 3, 4) являются оптимальными решениями некоторой задачи линейного программирования. Докажите, что точка М(3, 4, 5) также является оптимальным решением этой задачи.

m = 6. Найдите все значения параметра а, при которых точка (3, 2) является оптимальным решением задачи линейного программирования

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





m =7. Приведите пример задачи линейного программирования ( ) при , область допустимых значений которой содержит какие-нибудь три точки, не лежащие на одной прямой. Может ли множество оптимальных решений задачи совпадать с отрезком с концами А(2, 3), В(7, 6)?

m =8. Приведите пример задачи линейного программирования вида при , для которой и .

m = 9. Известно, что точки А(8, 2, 13), В(1, 7, 5), С(7, 9, 15) являются оптимальными решениями некоторой задачи линейного программирования. Докажите, что точка М(5, 7, 11) также является оптимальным решением этой задачи.

m = 10. Найдите все значения параметра а, при которых точка (4, 10) является единственным оптимальным решением задачи ли-

нейного программирования



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





m=11. Приведите пример задачи линейного программирования ( ) при , область допустимых значений которой содержит какие-нибудь три точки, не лежащие на одной прямой. Может ли множество оптимальных решений задачи совпадать с лучом, выходящим из точки А(4, 3) и содержащим точку В(5, 5)?

m = 12. Докажите, что если точки А(1, 1), В(1, 2), С(4, 3) являются оптимальными решениями задачи линейного программирования при , то .

m = 13. Известно, что точки А(9, 13, 17), В(3, 11, 19), С(5, 14, 16) являются оптимальными решениями некоторой задачи линейного программирования. Докажите, что точка М(5, 13, 17) также является оптимальным решением этой задачи.

m = 14. Приведите пример задачи линейного программирования ( ) при , область допустимых значений которой содержит какие-нибудь три точки, не лежащие на одной прямой. Может ли множество оптимальных решений задачи совпадать с прямой, проходящей через точки А(4, 3) и В(5, 5).
  • 2. Практические упражнения

  • 2.1. Задача 1

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



1. Фирма выпускает изделия двух типов, А и В. При этом используется сырье четырех видов. Расход сырья каждого вида на изготовление единицы продукции и запасы сырья заданы в таблице:

ИзделиеСырье1234А2102В3011Запасы сырья первого вида составляют 21 ед., второго вида – 4 ед., третьего – 6 ед. и четвертого – 10 ед. Выпуск одного изделия типа А приносит доход 300 ден. ед., одного изделия типа В – 200 ден. ед.

Составить план производства, обеспечивающий фирме наибольший доход.

2. Обработка деталей А и В может производится на трех станках. Причем каждая деталь при ее изготовлении должна последовательно обрабатываться на каждом из станков. Прибыль от реализации детали А – 100 ден.ед., детали В – 160 ден.ед. Исходные данные приведены в таблице.

СтанокНорма времени на обработку

одной детали, чВремя работы станка, чАВ10,20,110020,20,518030,10,2100Определить производственную программу, максимизирующую прибыль при условии: спрос на деталь А не менее 300 шт., на деталь В – не более 200 шт.

3. В суточный рацион цыплят включают два продукта питания, П1 и П2, причем продукта П1 должно войти в дневной рацион не более 200 ед. Стоимость одной единицы продукта П1 составляет 2 ден.ед., продукта П2 – 4 ден.ед. Содержание питательных веществ в одной единице продукта, минимальные нормы потребления указаны в таблице.

Питательное веществоМинимальная норма потребления, ед/деньСодержание питательных веществ в 1 ед. продуктаП1П2А1200,20,2В1600,40,2Определить оптимальный рацион питания, стоимость которого будет наименьшей.



4. Туристическая фирма в летний сезон обслуживает в среднем 7500 туристов в месяц и располагает флотилией из двух типов судов, характеристики которых представлены в таблице.

ПоказателиСудноIIIПассажировместимость, чел.20001000Горючее, т120007000Экипаж, чел.125100В месяц выделяется 60000т горючего. Потребность в рабочей силе не превышает 600 чел.

Определить количество судов I и II типа, чтобы обеспечить максимальный доход, который составляет от эксплуатации судов I типа 20 млн. руб., а II типа – 10 млн. руб.

5. Фирма производит для автомобилей запасные части типа А и В. Фонд рабочего времени составляет 5000 чел.-ч в неделю. Для производства одной детали типа А требуется 1 чел.-ч, а для производства одной детали типа В – 2 чел.-ч. Производственная мощность позволяет выпускать максимум 2500 деталей типа А и 2000 деталей типа В в неделю. Для производства деталей типа А уходит 2 кг полимерного материала и 5 кг листового металла, а для производства одной детали типа В – 4 кг полимерного материала и 4 кг листового металла. Еженедельные запасы каждого материала – соответственно 10 и 12 т. Общее число производимых деталей в течение одной недели должно составлять не менее 1500 штук.

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



6. Предприятие располагает ресурсами двух видов в количестве 120 ед. и 80 ед. соответственно. Эти ресурсы используются для выпуска продукции I и II , причем расход на изготовление единицы продукции первого вида составляет 2 ед. ресурса первого вида и 2 ед. ресурса второго вида, продукции второго вида - 3 ед. ресурса первого вида и 1 ед. ресурса второго вида. Доход от реализации единицы продукции первого вида составляет 6 ден. ед., второго

вида - 4 ден. ед.

Составить план выпуска продукции, обеспечивающий наибольшую прибыль, при условии, что продукции первого вида должно быть выпущено не менее продукции второго вида.

7. Предприятие производит два типа письменных столов, для чего использует 4 вида ресурсов в количествах, указанных в таблице.


  1. РесурсыЗапасы ресурсовРасход ресурсов на производство 1 столатип 1тип 2Доски стандартного сечения, м2832Металлическая арматура, кг2413Человеко - часы2723Лак, кг1821Прибыль, ден. ед.1520Определить план выпуска столов, обеспечивающий наибольшую прибыль.

8. Кирпичный завод выпускает кирпичи двух марок (I и II). Для производства кирпича применяется глина 3 видов (А, В и С). По месячному плану завод должен выпустить 10 усл. ед. кирпича марки I и 15 усл. ед. кирпича марки II. В таблице указаны расход различных видов глины для производства 1 усл. ед. кирпича каждой марки и месячный запас глины.

Какова наибольшая прибыль, если известно, что от реализации 1 усл. ед. кирпича марки I завод получает прибыль, равную 4 ден. ед., а марки II - 7 ден. ед.?

Марка

кирпичаКоличество глины, необходимое для производства 1 усл. ед. кирпича А В С I 1 0 1 II 0 2 2Запасы глины 15 36 479. Продукцией молокозавода являются молоко и кефир, расфасованные в бутылки. На производство 1 т молока и 1 т кефира требуется 1010 кг и 1020 кг молока соответственно. Затраты рабочего времени при разливе 1 т молока и 1т кефира составляют 0,18 и 0,19 машино-часов. Всего для производства продукции завод может использовать 200 т молока, а оборудование может использовать не более 22 машино-часов. Прибыль от реализации 1 т молока и кефира составляет соответственно 30 ден. ед. и 20 ден. ед. Завод должен ежедневно производить не менее 100 т молока, расфасованного в бутылки.



Составьте план ежедневного выпуска молока и кефира для достижения максимальной прибыли

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

Тип машины Виды продукцииОбщее время машинной работы за год продукция Iпродукция IIА351500В21600С381200D03450Прибыль на ед. продукции15Сколько продукции каждого вида необходимо выпустить, чтобы обеспечить максимальную прибыль?



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

Виды ресурсовОбъем ресурсовНормы расхода на 1 изделие (ед.)АВСталь5701070Цветные металлы4202050Токарные станки5600300400Фрезерные станки3400200100Прибыль (ден. ед.)300800Определить план выпуска продукции, при котором будет достигнута максимальная прибыль.



12. Цех выпускает трансформаторы видов А и В. На один трансформатор вида А расходуется 5 кг трансформаторного железа и 3 кг проволоки, а на трансформатор вида В - 3 кг железа и 2 кг проволоки. От реализации трансформатора вида А прибыль составляет 12 ден. ед., вида В - 10 ден. ед. Сменный фонд железа - 480 кг, проволоки - 300 кг.

Как следует спланировать выпуск трансформаторов, чтобы расход ресурсов не превышал выделенных фондов, а прибыль была наибольшей?



13. Для изготовления двух видов мебели используется 3 типа сырья, запасы которого и нормы расхода на единицу продукции заданы в таблице.

Вид мебелиТип сырьяПрибыль (ден. ед.) I II III I 4 1 2 20 II 1 2 335Запасы сырья, ед. 50 45 40Составить план производства мебели, при котором прибыль максимальна.



14. На судно грузоподъемностью 1000 т и емкостью трюмов 2400 м3 необходимо погрузить товары А и В. Объемные коэффициенты товаров составляют соответственно 3 и 1,2 . На складе имеется 800 т товара А и большое количество товара А. Прибыль от перевозки товара А 2 ден. ед., от перевозки товара В 3 ден. ед.

Каким образом надо загрузить судно, чтобы не превысить грузоподъемность и емкость трюмов, а стоимость перевозки была наибольшей?



15. Для производства двух видов сплавов используют в качестве добавок редкие металлы. Их запасы, нормы расхода на 1 т каждого сплава и прибыль от реализации 1 т каждого сплава приведены в таблице.

Вид сплаваПрибыль за 1 т (ден. ед.)Содержание добавок в 1 т сплава (кг) титанмолибден хром I 20 1 2 3 II 30 8 1 3Запасы металлов (в кг) 500 800 600Найти план выпуска сплавов, который дает максимальную прибыль.



16. На приобретение оборудования для нового производственного участка выделено 48 м2 и 36 ден. ед. Предприятие может заказать машины типа А стоимостью 6 ден. ед., занимающие площадь (с учетом проходов) в 6 м2 и выпускающие 7 ед. продукции за смену, и машины типа В стоимостью 3 ден. ед., занимающие площадь в 18 м2 и обеспечивающие выпуск 10 ед. продукции за смену. При этом следует учесть, что машин типа А можно заказать не более 5 штук. Денежные затраты и производственная площадь, занимаемая купленным оборудованием, не должны превышать указанных значений.

Сколько надо закупить оборудования, чтобы сменный выпуск продукции новым участком был наибольшим?



17. Трикотажное ателье изготовляет женские кофточки видов А и В. Запас пряжи, ее расход на одно изделие и цена готового изделия приведены в таблице.

ПряжаРасход на изделие, кгЗапас, кг А ВБежевая 0,05 0,120Салатная 0,1 0,260Коричневая 0,3 0,150Цена (ден. ед.) 250 300Как надо расходовать пряжу, чтобы ее расход не превышал имеющегося запаса, а сумма от реализации готовой продукции максимальна?



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

КормаРесурсы (кг)Содержание в 1 кг кормовкорм. ед.белоккальцийфосфорСено500,50,040,010,02Силос850,50,010,020,01Нормы потребления (не менее)3010,10,08Определите рацион с минимальной стоимостью, если стоимость 1 кг сена равна 12 ден. ед., 1 кг силоса - 8 ден. ед.



19. На животноводческой ферме при откорме телят в их рацион необходимо включить не менее 9 ед. белков, не менее 6 ед. жиров, не менее 8 ед. углеводов и не более 19 ед. нитратов. Для откорма телят можно закупить два вида кормов. Содержание питательных веществ в корме I составляет : 3 ед. белков, 1 ед. жиров, 1 ед. углеводов и 2 ед. нитратов, а в корме II соответственно : 1 ед., 3 ед., 8 ед., 4 ед. Один килограмм корма I стоит 60 ден. ед., а килограмм корма II - 10 ден. ед.

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



20. Кондитерская фабрика для производства двух видов карамели А и В использует три вида сырья: сахар, патоку и фруктовое пюре. Нормы расхода сырья каждого вида на производство 1 т карамели, запасы сырья и прибыль от реализации 1 т карамели указаны в таблице.

Вид сырьяЗапасы сырья, тНормы расхода сырья (т)

на 1кг карамелиАВСахар8000,60,5Патока5000,30,1Фруктовое пюре3000,10,4Прибыль от реализации 1 т карамели200350Найти план производства карамели, обеспечивающий наибольшую прибыль от ее реализации.

21. Мебельная фабрика выпускает стулья двух типов. На изготовление одного стула первого типа, стоящего 80 ден. ед., расходуется 2 м досок; 0,5 м2 обивочной ткани и 2 чел.-ч рабочего времени. Аналогичные данные для стульев 2-го типа составляет: 120 ден. ед., 4м; 0,25 м2 и 2,5 чел.-ч. На фабрике имеется 440 м досок, 65 м2 обивочной ткани и планируется затратить 320 чел.-ч рабочего времени.

Какие стулья и в каком количестве надо выпускать, чтобы стоимость продукции была максимальна?



22. Малое предприятие арендовало мини-пекарню для производства чебуреков и беляшей. Мощность пекарни позволяет выпускать в день не более 50 кг продукции. Ежедневный спрос на чебуреки не превышает 260 шт., а на беляши – 240 шт. Суточные запасы теста и мяса и расходы на производство каждой единицы продукции приведены в таблице.

Вид сырьяРасходы на производство, кг/шт.Суточные запасы сырья, кгчебурекабеляшаМясо0,0350,0621Тесто0,0650,0322Цена,руб./шт54,8Определить оптимальный план ежедневного производства чебуреков и беляшей, обеспечивающий максимальную выручку от продажи.



23. Биржевой маклер хочет вложить в акции некоторую сумму денег с тем, чтобы к концу года иметь 10 тыс. долл. Существует два типа акций, в которые стоит делать вложения: акции надежных компаний с минимальным риском (так называемые «голубые фишки»), приносящие в среднем 10% годовых, и акции компаний, занимающихся высокими технологиями. Последние акции имеют более высокую доходность – в среднем 25% годовых, однако они значительно более рисковые. Поэтому маклер решил вкладывать в них не более 60% средств.

Каких акций и на какую сумму надо приобрести маклеру, чтобы достичь желаемой цели?



24. Мебельная фабрика для сборки столов и стульев привлекает к работе на 10 дней четырех столяров. Каждый столяр тратит 2 часа на сборку стола и 30 минут – на сборку стула. Покупатели обычно приобретают вместе со столом от четырех до шести стульев. Доход от одного стола составляет 135 долл. И 50 долл. – от одного стула. На фабрике установлен 8-часовой рабочий день.

Определите структуру производства (на 10 рабочих дней), которая максимизировала бы суммарный доход.



25. Магазин B&K продает два вида безалкогольных напитков: колу А1 известного производителя и колу B&K собственного производства. Доход от одной банки колы А1 составляет 5 центов, тогда как доход от одной банки собственного производства – 7 центов. В среднем за день магазин продает не более 500 банок обоих напитков. Несмотря на то, что А1 – известная торговая марка, покупатели предпочитают колу B&K, поскольку она значительно дешевле. Подсчитано, что объемы продаж колы B&K и А1 (в натуральном исчислении) должны соотноситься не менее 2:1. Кроме того, известно, что магазин продает не менее 100 банок колы А! в день.

Сколько банок каждого напитка должен иметь магазин в начале рабочего дня для максимизации дохода?



26. Завод Electra производит два типа двигателей, каждый на отдельной сборочной линии. Производительность этих линий составляет 600 и 750 двигателей в день. Двигатель первого типа использует 10 единиц некоего комплектующего, а двигатель второго типа – 8 единиц этого же компонента. Поставщик может обеспечить в день 8000 единиц этих деталей. Доходность изготовления двигателя первого типа составляет 60, второго – 40 долл.

Определите оптимальную структуру ежедневного производства двигателей.



27. Банк Elkins в течение нескольких месяцев планирует вложить до 200000 долл. в кредитование частных лиц (клиентов) и покупок автомобилей. Банковские комиссионные составляют 14% при кредитовании частных лиц и 12% при кредитовании покупок автомобилей. Оба типа кредитов возвращаются в конце годичного периода кредитования. Известно, что около 3% клиентских и 2% автомобильных кредитов никогда не возвращаются. В этом банке объемы кредитов на покупку автомобилей обычно более чем в два раза превышают объемы других кредитов для частных лиц.

Найдите оптимальное размещение средств по двум описанным видам кредитования и определите коэффициент возврата по всем кредитам.



28. Консервный завод перерабатывает за смену 60000 кг спелых помидоров (7 руб. за кг) в томатный сок и пасту. Готовая продукция пакетируется в упаковки по 24 банки. Производство одной банки сока требует одного кг спелых помидоров, а одной банки пасты – трети кг. Заводской склад может принять за смену только 2000 упаковок сока и 6000 упаковок пасты. Оптовая цена одной упаковки томатного сока составляет 540 руб., одной упаковки томатной пасты – 270 руб.

Определите оптимальную структуру производства консервного завода.



29. Компания имеет возможность рекламировать свою продукцию по местному радио и телевидению. Бюджет на рекламу ограничен суммой 10 000 долл. в месяц. Одна минута рекламного времени на радио стоит 15, а на телевидении – 300 долл. Компания предполагает, что реклама на радио по времени должна превышать рекламу на телевидении не менее сем в два раза. Вместе с тем, известно, что нерационально использовать более 400 минут рекламы на радио в месяц. Последние исследования показали, что реклама на телевидении в 25 раз эффективнее рекламы на радио.

Разработайте оптимальный бюджет для рекламы на радио и телевидении.



30. Факультет послевузовского обучения местного колледжа города Озарк предлагает в общей сложности до 30 курсов каждый семестр. Все курсы условно можно разбить на два типа: практические, такие как, обучение работе на компьютере, ремонт автомобиля и др., и гуманитарные, например, исторические знания, творческие мастерские и др. Чтобы удовлетворить запросы обучающихся, в каждом семестре должно предлагаться не менее 10 курсов каждого типа. Факультет оценивает доход от одного практического курса в 1500, а гуманитарного – 1000 долл.

Какова оптимальная структура курсов для факультета?



31. Компания производит два вида продукции А и В. Объем продаж продукта А составляет не менее 80% от общего объема продаж продуктов А и В. Вместе с тем, компания не может производить более 100 единиц продукта А в день. Для производства этих продуктов используется одно и тоже сырье, поступление которого ограничено 240 фунтами в день. На изготовление единицы продукта А расходуется 2 фунта сырья, а единицы продукта В – 4 фунта. Цена одной единицы продуктов А и В составляет 20 и 50 долл. соответственно.

Найдите оптимальную структуру производства компании.



32. Завод бытовой химии производит два вида чистящих средств, А и В, используя при этом сырье I и II. Для производства чистящих средств ежедневно имеется 150 единиц сырья. На получение одной единицы средства А используется 0,5 единицы сырья I и 0,6 единицы сырья II. На производство одной единицы средства В затрачивается 0,5 единицы сырья I и 0,4 единицы сырья II. Доход на единицу средств А и В составляет соответственно 8 и 10 долл. Ежедневное производство средства А должно быть не менее 30 и не более 150 единиц. Для производства средства В аналогичные ограничения составляют 40 и 200 единиц.

Найдите оптимальную структуру выпуска чистящих средств.



  1. 2.2. Задача 2

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

Таблица 2.1.

Индивидуальные задания к задаче 2

nЗадача ЛПnЗадача ЛП12341 2 3 4 5 6 7 8 12349 10 11 12 13 14 15 16 17 18 19 20 Продолжение табл.2.1

  • 123421 22 23 24 25 26 27 28 29 30 31 32 2.3. Задача 3

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


Тип задачи 1:
Для изготовления различных изделий А и В используются три вида сырья. На производство единицы изделия А требуется затратить сырья первого вида - (кг), сырья второго вида - (кг), сырья третьего вида - (кг). На производство единицы изделия В требуется затратить сырья первого вида - (кг), сырья второго вида - (кг), сырья третьего вида - (кг).

Производство обеспечено сырьем первого вида в количестве (кг), сырьем второго вида в количестве (кг), сырьем третьего вида в количестве (кг).

Прибыль от реализации единицы готового изделия А составляет (руб.), а изделия В составляет (руб.).

Составить план производства изделий А и В, обеспечивающий максимальную прибыль от их реализации.

Таблица 2.2

Значения коэффициентов в условии задачи


n Затраты сырья на единицу изделия Затраты сырья на единицу изделия Количество имеющегося сырьяПрибыль от реализации ед. продукции123451 4 Продолжение табл.2.2123457 10 13 16 19 22 25 28 31 Тип задачи 2:
Для производства двух видов изделий А и В используются три типа технологического оборудования. На производство единицы изделия А оборудование первого типа используется - часов, оборудование второго типа - часов, а оборудование третьего типа - часов. На производство единицы изделия В оборудование первого типа используется - часов, оборудование второго типа - часов, а оборудование третьего типа - часов.

На изготовление всех изделий администрация предприятия может предоставить оборудование первого типа не более чем на часов, оборудование второго типа не более чем на часов, а оборудование третьего типа не более чем на часов

Прибыль от реализации единицы готового изделия А составляет руб., а изделия В составляет руб.

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

Таблица 2.3.

Значения коэффициентов в условии задачи


n Затраты сырья на единицу изделия Затраты сырья на единицу изделия Количество имеющегося сырьяПрибыль от реализации ед. продукции123452 5 8 Продолжение табл.2.31234511 14 17 20 23 26 29 32 Тип задачи 3:
Фирма изготовляет два вида красок для внутренних (В) и наружных (Н) работ. Для их производства используют исходные продукты: пигмент и олифу. Расходы исходных продуктов и максимальные суточные запасы указаны в таблице 2.4.

Таблица 2.4.

Расход и суточные запасы исходных продуктов

Исходный продуктРасход исходных продуктов на 1 т краскиСуточный запас, тКраска НКраска ВПигмент Олифа

Изучение рынка сбыта показало, что суточный спрос на краску для наружных (внутренних) работ никогда не превышает в сутки. Цена продажи 1 т краски для наружных работ - ден. ед., для внутренних работ - ден. ед.

Какое количество краски каждого вида должна производить фирма, чтобы доход от реализации продуктов был максимальным?

Таблица 2.5.

Значения коэффициентов условий задачи

n36912151821242730коэф. 3112321324 2142212435 1233133111 2121141112 661234246678 2113421224 1222111113 8661288581024 0110111000 1001000111 22,53,544314,563Примечание. Если по условию задания спрос на краску для наружных (внутренних) работ не превышает т в сутки, то в математической модели задачи следует принять, что коэффициент системы ограничений при неизвестном значении краски для наружных (внутренних) работ, обозначенных в таблице ( ), равен 1 (0), а при неизвестном значении краски для внутренних (наружных) работ ( ), равен 0 (1).

  1. 2.4. Задача 4

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

Таблица 2.6.

Индивидуальные задания к задаче 4

nЗадача ЛПnЗадача ЛП12341 2 3 4 5 6 Продолжение табл.2.612347 8 9 10 11 12 13 14 15 16 Продолжение табл.2.6.

123417 18 19 20 21 22 23 24 25 26 Продолжение табл.2.6.

123427 28 29 30 31 32

  1. 2.5. Задача 5

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

Таблица 2.7.

Индивидуальные задания к задаче 5

nЗадача ЛПnЗадача ЛП1 2 Продолжение табл.2.7.

12343 4 5 6 7 8 9 10 11 12 Продолжение табл.2.7.

123413 14 15 16 17 18 19 20 21 22 Продолжение табл.2.7.

123423 24 25 26 27 28 29 30 31 32


  • 3. Пример решения задач



3.1. Пример 1

Решить задачу линейного программирования:




Строим область допустимых решений задачи. Нумеруем ограничения задачи. В прямоугольной декартовой системе координат строим прямую , соответствующую ограничению (1). Находим, какая из двух полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1) . Для этого достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство. Так как прямая не проходит через начало координат, подставляем координаты точки O (0,0) в первое ограничение . Получаем неравенство . Следовательно, точка O лежит в полуплоскости решений. Таким образом, стрелки на концах прямой должны быть направлены в полуплоскость, содержащую точку O. Аналагично строим прямые и области решений ограничений (2),(3) и (4). Находим общую часть полуплоскостей решений, учитывая при этом условия неотрицательности; полученную область допустимых решений отметим штриховкой.

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

Решая систему , получаем . Вычисляем .


3.2 Пример 2

Решить задачу линейного программирования:



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

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

3. Решить задачу линейного программирования:




Строим прямые линии, соответствующие неравенствам системы ограничений и находим полуплоскости, являющиеся областями решений этих неравенств.

Область допустимых решений задачи является пустым множеством. Задача не имеет решения ввиду несовместности системы ограничений.
3.4. Пример 4

Задача. Ткацкая фабрика располагает 300 станками первого типа и 200 станками второго типа. Станки могут вырабатывать два вида ткани. Каждый вид станка может производить любой вид ткани, но в неодинаковом количестве. Станок первого типа производит в единицу времени 10 м ткани первого вида и 8 м ткани второго типа, а станок второго вида – соответственно 8 и 6 м ткани.

Каждый метр ткани первого вида приносит фабрике прибыль 2 руб. и второго вида – 3 руб. Согласно плану производства фабрика обязана выпустить в единицу времени не менее 2700 м ткани первого вида и 1400 – второго вида. Требуется так распределить загрузку станков, чтобы был выполнен план, и при этом прибыль в единицу времени была максимальной.



Решение. Введем обозначения: x1, x2 – число станков первого и второго типа, производящих ткань первого вида, x3, x4 – число станков первого и второго типа, производящих ткань второго вида.

Целевой функцией в этой задаче является общая прибыль предприятия:

F(x) = F(x1, x2, x3, x4) = 2(10x1 + 8x2) + 3(8x3 + 6x4) = 20x1 +

+ 16x2 + 24x3 + 18x4

При этом должны выполняться следующие ограничения:


Решим задачу симплекс – методом. Введем дополнительные переменные x5, x6, x7, x8  0, так чтобы система неравенств превратилась в систему равенств. Ограничения примут вид:


Так как в системе ограничений нет очевидного базиса (т.е. нет решения, где бы базисные переменные были положительны), используем М – метод. Введем искусственные переменные x9  0, x10  0 для получения очевидного базиса. За использование этих переменных в целевой функции введем штраф -M(x9 + x10). Пусть для определенности М=100.Выразим x9 и x10 из уравнений ограничений и подставим в целевую функцию. Исходная симплекс – таблица примет вид:

Таблица 3.1

базисx1x2x3x4x5x6x7x8x9x10Св.чF102081682461800-100-10000--x51010100000300x60101010000200x91080000-10102700x100086000-1011400Т.к. F(x)  max, то избавляться надо от положительных слагаемых. Найдем отношения .Разрешающий элемент находится в четвертой строке первом столбце. Разделим четвертую строку на 10. Затем вычтем из первой строки четвертую, умноженную на 1020, вычтем из второй строки четвертую. Получим таблицу.

Таблица 3.2

базисx1x2x3x4x5x6x7x8x9x10Св.чF00824618002-100-1020--x50-0,810100,100,1030x60101010000200x110,80000-0,100,10270x100086000-1011400

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

Таблица 3.3

базисx1x2x3x4x5x6x7x8x9x10Св.чF0659,20618-8240-80,4-100-19,60--x30-0,810100,10-0,1030x60101010000200x110,80000-0,100,10270x1006,406-80-0,8-10,811160Найдем отношения 181, 25. Разрешающий элемент находится в пятой строке втором столбце. Вычтем из первой строки пятую, умноженную на 659,2; прибавим ко второй строке пятую, умноженную на 0,8; вычтем из третьей строки пятую; вычтем из четвертой строки пятую, умноженную на 0,8. Получим таблицу.

Таблица 3.4

базисx1x2x3x4x5x6x7x8x9x10Св.чF00000023102-103--x30010,75000-1/801/8175x60001/165/411/85/32-1/8-5/3275/4x1100-3/41001/801/8125x201015/16-5/40-1/8-5/321/85/32725/4

Найдем отношения Разрешающий элемент находится в третьей строке девятом столбце. Разделим третью строку на Вычтем из первой строки третью, умноженную на 3; прибавим ко второй строке третью, умноженную на 1/8; вычтем из четвертой строки третью, умноженную на 1/8; прибавим к пятой строке третью, умноженную на 5/32. Получим таблицу.

Таблица 3.5

базисx1x2x3x4x5x6x7x8x9x10Св.чF000-1,2-24-19,2-0,40-99,6-100--x30010,810,80,10-0,10190x80000,486,40,81-0,8-1120x1100-0,80-0,8-0,100,10110x20101010000200

Так как в строке для F нет положительных слагаемых, то оптимальное решение получено. Значения переменных:

x1 = 110, x2 = 200, x3 = 190, x4 = 0, x5 = 0, x6 = 0, x7 = 0, x8 =120, x9 = 0, x10=0. При этом значение функции равно F = 20x1 + 16x2 + 24x3 + 18x4 = 20110 +16200 + 24190 + 180 = 9960.
Ответ: 100 станков первого типа производит ткань 1 вида

200 станков второго типа производит ткань 1 вида

190 станков первого типа производит ткань 2 вида.

Прибыль при этом составляет 9960 руб. Ткань первого вида выпускается по плану 2700 м, а второго вида больше на 120 м.



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





  1. Что называется допустимым решением?

  2. Каким множеством является множество допустимых решений? Из каких точек оно состоит?

  3. Сформулируйте условие оптимальности.

  4. Сформулируйте условие допустимости.

  5. Расскажите алгоритм графического метода решения задач линейного программирования.

  6. Расскажите алгоритм симплекс-метода решения задач линейного программирования.

  7. Сформулируйте задачу линейного программирования в каноническом виде.

  8. Как привести задачу линейного программирования, записанную в стандартном виде, к каноническому виду.



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





  1. Таха, Хемди А. Введение в исследование операций. – М.: Издательский дом «Вильямс», 2005.

  2. Фомин Г.П. Математические методы и модели в коммерческой деятльности. – М.: Финансы и статистика, 2005.

  3. Красс М.С., Чупрынов Б.П. Математика для экономистов. – СПб.: Питер, 2006.

  4. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. – М.: Дело, 2003.







Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©uverenniy.ru 2019
обратиться к администрации

    Главная страница