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

Симплексные методы решения задач

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

Цель работы

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

Методические указания

При решении задач линейного программирования используйте программы lablp.exe и lpbalans.exe или постройте их, используя исходные тексты lablp.c и lpbalans.c. Отличие lpbalans.c состоит в том, что с её помощью можно решать "балансовые" задачи линейного программирования. Решать задачи линейного программирования можно также в системе Maple V. Пример решения задачи линейного программирования в системе Maple V:

> with(simplex):

> cnsts:= {3*x+4*y-3*z <= 23, 5*x-4*y-3*z <= 10, 7*x+4*y+11*z <= 30}:

> obj:= -x + y + 2*z:

> maximize(obj,cnsts union {x>=0,y>=0,z>=0});

{x = 0, y = 49/8, z = 1/2}.

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

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

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

3. Составить двойственную задачу для любой поставленной задачи линейного программирования и решить её. Дать интерпретацию переменным двойственной задачи.

Варианты заданий

1. (Распределительная задача)

Плановое задание по изготовлению 4 видов костюмов необходимо распределить между 3 швейными фабриками. Производственные мощности i фабрики (i=1,2,3) позволяют за рассматри­ваемый период времени выпустить r(i,j) костюмов j модели (j=1,2,3,4). При этом, если все производственные мощности фабрики идут на производство костюмов одного типа, то костюмы других видов производится не могут. Заданы цены c(j) на костюм j модели и себестоимости s(i,j) изготовления j модели на i фабрике.

,

,

.

Плановое задание (180, 150, 100, 100).

Опираясь на эти данные ответить на вопросы:

· Может ли быть выполнено плановое задание?

· Составить оптимальный план загрузки фабрик из условия миними­зации себе­стоимости плановой продукции.

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

· То же, при допустимости перевыполнения планового задания.

· Составить оптимальный план загрузки фабрик, обеспечивающий максимальное количество комплектов костюмов, если числа плано­вого задания рассматривать как ассортиментные отношения.

2. (Определение оптимального ассортимента)

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

По этим исходным данным ответить на вопросы:

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

· Определить, как повлияет на максимальную прибыль увеличение каждого ресурса на единицу.

· Определить оптимальный ассортимент при дополнительном усло­вии: 1-го товара выпустить не более 5 ед., 2-го - не менее 8 ед., а 3-го и 4-го в соотношении 1:2.

· Дополнительно к пункту 1 заданы производственные издержки в рублях на 1 ед. каждого изделия: 60, 90, 120, 30. Найти опти­мальный ассортимент, максимизирующий прибыль, при условии, что суммарные производственные издержки не должны превы­шать 960 руб.

· Определить изменение в оптимальном ассортименте, найденном в пункте 1, если ресурсы сырья увеличены на 50%, а ресурсы рабочей силы и оборудования на 30%.

3. (Задача о смесях)

Нефтеперерабатывающий завод получает 4 различных полуфа­бриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина пря­мой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А 2:3:5:2, бензин Б - 3:1:2:1 и бензин С - 2:2:1:3.

Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 12000 руб., 10000 руб., 15000 руб.

По этим исходным данным решить следующие задачи:

· Определить план смешения компонентов, при котором будет до­стиг­нута максимальная стоимость всей продукции.

· Определить оптимальный план смешения из условия максималь­ного использования компонентов.

4. (Задача о раскрое)

Полуфабрикаты поступают на предприятие в виде листов фанеры. Всего имеется две партии материала, причем первая партия содержит 400 листов, а вторая 250 листов фанеры. Из поступающих листов фанеры необходимо изготовить комплекты, включающие 4 детали 1-го типа, 3 детали 2-го типа и 2 детали 3-го типа. Лист фанеры каждой партии может раскраиваться различными способами.

Количество деталей каждого типа, которое получается при рас­крое одного листа соответствующей партии по тому или иному спосо­бу раскроя, представлено в таблице.

Требуется раскроить материал так, чтобы обеспечить изгото­вление мак­си­мального количества комплектов.

5. (Определение оптимального плана производства)

На фабрике производится продукты двух типов. Для производства используются станки трех типов, два типа сырья, квалифицированная и неквалифицированная рабочая сила.

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

Станки. Станок первого типа имеет ресурс мощности 3×10⁶, второго типа – 1×10⁶, третьего типа – 3×10⁵. При производстве первого продукта используется 0.5 единиц ресурса мощности станка первого типа, 0.2 единицы ресурса мощности станка второго типа и 0.025 единиц ресурса мощности станка третьего типа. При производстве второго продукта используется 2 единицы ресурса мощности станка первого типа, 0.5 единиц ресурса мощности станка второго типа и 0.1 единица ресурса мощности станка третьего типа.

Персонал. Бригада из одного квалифицированного рабочего и восьми неквалифицированных рабочих может выпустить 1.5×10⁵ единиц первого продукта. Бригада из двух квалифицированных рабочих и 11-ти неквалифицированных рабочих может выпустить 4×10⁴ единиц второго продукта.

Стоимость одной единицы сырья первого типа 1 руб., второго типа – 0.15 руб. Стоимость одного станка первого типа 8×10⁶ руб., станка второго типа – 7×10⁶ руб., станка третьего типа – 9×10⁶ руб. Амортизационные отчисления составляют 5 % от стоимости станка. Заработная плата квалифицированных рабочих 6.25×10³ руб., неквалифицированных – 4×10³ руб.

Цена первого продукта составляет 3.5 руб., второго – 12.5 руб.

Считается, что имеется неограниченное количество сырья. В наличии имеется 5 станков первого типа, 5 – второго типа, 3 ­– третьего типа. Максимальное число квалифицированных рабочих – 360, неквалифицированных – 2500. Платежеспособный спрос на первый продукт составляет 2.2×10⁷ руб., на второй продукт – 2.7×10⁷ руб.

Плановое задание: 1.25×10⁷ единиц первого продукта и 4×10⁶ единиц второго продукта.

По этим исходным данным решить следующие задачи:

· Выполнимо ли плановое задание? Если да, то вычислить себестоимость плановой продукции и объем необходимых ресурсов.

· Определить оптимальный план выпуска продукции из условия максимальной стоимости продукции.

· Определить оптимальный план выпуска продукции из условия максимальной прибыли.

Содержание отчета

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

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

1. Прямая и двойственная задачи линейного программирования.

2. Теоремы двойственности.

3. Решение задач линейного программирования в системе MAPLE V.

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