Имеются два вида корма i и ii содержащие питательные вещества вита

На главную страницу

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

В конец страницы

10.1. ПРИМЕРЫ ЗАДАЧ
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

1. Задача использования сырья
(задача планирования производства).

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

Таблица 10.1

 Составим
экономико-математическую модель (математическое описание исследуемого
экономического процесса) задачи.

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

(10.1)

     
По смыслу задачи переменные
,
.
(10.2)

Суммарная прибыль
F(x) составит
 руб.
от реализации продукции  и
 руб.
– от реализации продукции ,
т.е.

                                                    
.
(10.3)

Итак, экономико-математическая
модель задачи: найти такой план выпуска продукции
,
удовлетворяющий системе (10.1) и условию (10.2), при котором функция (10.3)
принимает максимальное значение.

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

2. Задача составления рациона
(задача о диете).

Имеется два вида корма
I и II, содержащие
питательные вещества (витамины) ,
 и
.
Содержание количества единиц питательного вещества в 1 кг каждого вида корма и
стоимость 1 кг корма приведены в таблице 10.2.

 Таблица
10.2

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

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

(10.4)

Кроме того, переменные

                                                    
,
. (10.5)

Общая стоимость рациона (в руб.)
составит

                                          
. (10.6)

Итак, экономико-математическая
модель задачи: составить дневной рацион
,
удовлетворяющий системе (10.4) и условию (10.5), при котором функция (10.6)
принимает минимальное значение.

3. Задача о раскрое материалов.

На раскрой поступает материал
одного образца в количестве a единиц. Требуется
изготовить из него l разных комплектующих
изделий в количествах пропорциональных числам 
,
,
…,  (условие
комплектности). Каждая единица материала может быть раскроена
n различными способами, при этом использование
i-го способа (i
=1, 2, …, n) дает
 единиц
k-го изделия (k
= 1, 2, …, l). Требуется составить план
раскроя, обеспечивающий максимальное количество комплектов.

Составим экономико-математическая
модель задачи. Обозначим через  количество
единиц материала, раскраиваемых i-м способом, и
x – количество изготавливаемых комплектов
изделий.

Так как общее количество материала
равно сумме его единиц, раскраиваемых различными способами, то

(10.7)

 Условие комплектности выразится
уравнениями

 (k
= 1, 2, …, l)                       
(10.8)

по смыслу задачи переменные

                                                    
 (i
= 1, 2, …, n).                           
(10.9)

Итак, экономико-математическая
модель задачи: найти такое решение ,
удовлетворяющее системе уравнений (10.7) – (10.8) и условию (10.9), при котором
функция F = x
принимает максимальное значение.

 Назад     К
началу страницы    
Вперед

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

Область допустимых решений OABCDE представлена на рис. Рис.4

Рис.1. Многоугольник решений к примеру 1

Действительно, соответствующие границы ограничений представлены уравнениями прямых:

Вектор и линии уровня определяются соотношениями:

Перемещаем линию уровня по направлению вектора . Точкой выхода из области допустимых решений является точка С. Её координаты определяются как пересечение прямых:

Решая систему, получим координаты точки С(312,5; 300), в которой и будет оптимальное решение, т. е.

Таким образом, для получения максимального дохода, равного 9200 руб., предприятие должно выпускать 312,5 кг сливочного мороженого и 300 кг шоколадного мороженого.

Пример 2. (задача о диете и смесях). Имеются два вида корма I и II, содержащие питательные вещества (витамины): B1, В2 и В3. Содержание числа единиц питательных веществ в 1 кг каждого вида корма и необходимый минимум питательных веществ приведены в табл. 2. Стоимость 1 кг кормов видов I и II равна соответственно 4 и 6 руб.

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

Таблица 2.

Решение. Составим экономико-математическую модель задачи.

Если x1 – количество корма вида I, входящего в дневной рацион, а х2 – количество корма вида II, то задачу линейного программирования можно записать в виде:

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

Область допустимых решений ABCD (рис 2) представляет собой неограниченную многоугольную область.

Рис. 2. Многоугольник решений к примеру 2

Соответствующие границы ограничений представлены уравнениями прямых:

Вектор и линии уровня определяются соотношениями:

Перемещаем линию уровня по направлению вектора . Точкой выхода из области допустимых решений является точка B. Её координаты определяются как пересечение прямых:

Решая систему, получим координаты точки В(2;3), в которой и будет оптимальное решение, т. е.

Таким образом, для получения минимальной стоимости рациона, равной 26 руб., в него включают 2 единицы корма вида I н 3 единицы корма вида II.

Задачи для самостоятельной работы

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

Таблица 3.

Задача 2. На предприятии, выпускающем изделия двух типов, производственная мощность цеха сборки составляет 100 изделий первого или 300 изделий второго типа в сутки; в то же время отдел технического контроля в состоянии проверить не более 150 изделий (любого типа) в сутки. Изделие первого типа стоит вдвое дороже, чем изделие второго типа. Требуется при этих условиях найти такой план выпуска продукции, который обеспечивал бы предприятию наибольшую прибыль.

Задача 3. Компания специализируется на выпуске хоккейных клюшек и наборов шахмат. Каждая клюшка приносит компании прибыль в размере 2$, а каждый шахматный набор – в размере 4$. На изготовление одной клюшки требуется четыре часа работы на участке A и два часа работы на участке B. Шахматный набор изготавливается с затратами шести часов на участке A, шести часов на участке B и одного часа на участке C. Доступная производственная мощность участка A составляет 120 н-часов в день, участка В – 72 н-часа и участка С – 10 н-часов.

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

Задача 4. На птицеферме употребляются два вида кормов – I и II. В единице массы корма I содержатся единица вещества A, единица вещества В и единица вещества С. В единице массы корма II содержатся четыре единицы вещества А, две единицы вещества В и не содержится вещество C. В дневной рацион каждой птицы надо включить не менее единицы вещества А, не менее четырех единиц вещества В и не менее единицы вещества С. Цена единицы массы корма I составляет 3 рубля, корма II – 2 рубля.

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

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

Таблица 4

Запасы сырья 1-го вида составляют 21 ед., 2-го вида – 4 ед., 3-го вида – 6 ед. и 4-го вида – 10 ед. Выпуск одного изделия типа А приносит доход 300 руб., одного изделия типа В – 200 руб.

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

Задача 6. Сельскохозяйственное предприятие на промышленной основе производит откорм бычков. Имеется два вида продуктов П1 и П2. При откорме каждое животное должно ежедневно получать не менее 9 ед. питательного вещества С1, не менее 8 ед. вещества С2 и не менее 12 ед. вещества С3. Содержание количества единиц питательных веществ в 1 кг каждого вида продуктов приведено в табл. 5.

Таблица 5

Корм П1 стоит 4 руб., а корм П2 – 6 руб. Требуется составить такой пищевой рацион, т. е. определить входящие в него такие количества исходных продуктов П1 и П2, чтобы заданные условия по содержанию в смеси питательных веществ были выполнены, но при этом стоимость рациона была минимальна.

Задача 7 (об использовании сырья). Для изготовления двух видов продукции П1 и П2 используется три вида сырья: С1, С2 и С3. Запасы сырья на складе и количество единиц сырья, затрачиваемых на изготовление единицы продукции, приведены в табл. 6.

Таблица 6

Прибыль от реализации единицы продукции П1 составляет 50 руб., продукции П2 – 40 руб. Необходимо составить такой план выпуска продукции, чтобы при ее реализации получить максимальную прибыль.