Главная | Обратная связь | Поможем написать вашу работу!

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

1. Задача составления рациона (задача о диете, задача о смесях).

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

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

Питательное вещество	Необходимый минимум	Число единиц питательных веществ в 1 кг корма
I	II

Стоимость 1 кг корма I и II соответственно 4 и 6 руб.

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

Решение.

Пусть – количество I корма, входящего в дневной рацион,

– количество II корма, входящего в дневной рацион.

Так как содержание питательных веществ не должно быть менее 9, 8 и 12 единиц, то получим систему неравенств:

(1.8)

(1.9)

Общая стоимость руб.

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

Общая формулировка задачи:

Пусть - число единиц корма.

- необходимый минимум содержания в рационе питательного вещества .

- число единиц питательного вещества в 1 кг корма .

- стоимость 1 кг корма -го вида.

Экономико-математическая модель:

Найти такой рацион , удовлетворяющий системе:

и условию при котором функция принимает минимальное значение.

2. Задача об использовании ресурсов (задача планирования производства).

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

Вид ресурса	Запас ресурса	Число единиц ресурсов, затрачиваемых на изготовление единицы продукции



		–
			–

Прибыль, получаемая от единицы продукции и , – соответственно 2 и 3 руб.

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

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

Обозначим , – число единиц продукции соответственно и , запланированных к производству. Для их изготовления потребуется единиц ресурса , единиц ресурса , единиц ресурса и единиц ресурса . Так как потребление ресурсов , , и не должно превышать их запасов, соответственно 18, 16, 5 и 21 единицы, то связь между потреблением ресурсов и их запасами выразится системой неравенств:

(1.10)

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

(1.11)

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

. (1.12)

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

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

Обозначим – число единиц продукции , запланированной к производству; – запас ресурса , – число единиц ресурса , затрачиваемого на изготовление единицы продукции (числа часто называют технологическими коэффициентами); – прибыль от реализации единицы продукции .

Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид: найти такой план выпуска продукции, удовлетворяющий системе

(1.13)

и условию

(1.14)

при котором функция

(1.15)

принимает максимальное значение.

3. Задача об использовании мощностей (задача о загрузке оборудования).

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

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

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

Обозначим – время, в течение которого станок будет занят изготовлением продукции .

Так как время работы каждого станка ограничено и не превышает , то справедливы неравенства:

(1.16)

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

(1.17)

Кроме того,

. (1.18)

Затраты на производство всей продукции выразятся функцией

. (1.19)

Экономико-математическая модель задачи об использовании мощностей примет вид: найти такое решение , удовлетворяющее системам (1.16) и (1.17) и условию (1.18), при котором функция (1.19) принимает минимальное значение.

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

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

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

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

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

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

. (1.20)

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

. (1.21)

Очевидно, что

. (1.22)

Экономико-математическая модель задачи: найти такое решение , удовлетворяющее системе уравнений (1.20) – (1.21) и условию (1.22), при котором функция принимает максимальное значение.

Пример 3. Для изготовления брусьев длиной 1,2 м, 3 м и 5 м в соотношении 2:1:3 на распил поступают 195 бревен длиной 6 м. Определить план распила, обеспечивающий максимальное число комплектов. Составить экономико-математическую модель задачи.

Решение. Прежде всего определим всевозможные способы распила бревен, указав соответствующее число получаемых при этом брусьев (см. следующую таблицу).

Способ распила	Число получаемых брусьев длиной, м
1,2	3,0	5,0
		–	–
			–
	–		–
	–	–

Обозначим: – число бревен, распиленных -м способом ; – число комплектов брусьев.

Учитывая, что все бревна должны быть распилены, а число брусьев каждого размера должно удовлетворять условию комплектности, экономико-математическая модель задачи примет вид:

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

Задачу о раскрое легко обобщить на случай раскраиваемых материалов.

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

Обозначим – число единиц -го материала, раскрываемого - м способом.

Экономико-математическая модель задачи о раскрое в общей постановке примет вид: найти такое решение , удовлетворяющее системе

и условию , при котором функция принимает максимальное значение.

5. Транспортная задача

Важным частным случаем задачи линейного программирования является так называемая транспортная задача.

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

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

Пример 4.

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

Поставщики	Мощность поставщиков	Потребители и их спрос
B ₁	B ₂	B ₃	B ₄

A ₁		x ₁₁	x ₁₂	x ₁₃	x ₁₄
A ₂		x ₂₁	x ₂₂	x ₂₃	x ₂₄
A ₃		x ₃₁	x ₃₂	x ₃₃	x ₃₄

В левом верхнем углу произвольной – клетки ( – номер строки, – номер столбца) стоит так называемый коэффициент затрат – затраты на перевозку единицы груза от -го поставщика к -му потребителю, например, в левом верхнем углу клетки стоит число 2, следовательно, перевозка единицы груза от 1-го поставщика к 4-му потребителю обойдется в 2 условных денежных единицы и т.д.

Задача ставится следующим образом: найти объемы перевозок для каждой пары «поставщик – потребитель» так, чтобы:

- мощности всех поставщиков были реализованы;

- спросы всех потребителей были удовлетворены;

- суммарные затраты на перевозку были бы минимальны.

Построим экономико-математическую модель данной транспортной задачи.

Обозначим искомые объемы поставок от -ого поставщика -му потребителю через .

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

(2.1)

Аналогично, чтобы спрос каждого из потребителей был удовлетворен, подобные уравнения баланса составляем для каждого столбца таблицы поставок:

(2.2)

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует дополнительно предположить, что

Суммарные затраты на перевозку выражаются через коэффициенты затрат и поставки следующим образом:

(2.3)

Теперь можно дать математическую формулировку задачи (без обращения к ее содержательному экономическому смыслу). На множестве неотрицательных решений системы ограничений (2.1) и (2.2) найти такое решение , при котором линейная функция (2.3) принимает минимальное значение.

Особенности экономико-математической модели транспортной задачи:

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

- коэффициенты при переменных системы ограничений равны единице или нулю;

- каждая переменная входит в систему ограничений два раза: один раз – в систему (2.1) и один раз – в систему (2.2).

Для математической формулировки транспортной задачи в общей постановке обозначим через коэффициенты затрат, через - мощности поставщиков, через - спросы потребителей, где , – число поставщиков, – число потребителей. Тогда система ограничений примет вид:

, (2.4)

. (2.5)

Система (26) включает в себя уравнение баланса по строкам, а система (2.5) – по столбцам. Линейная функция в данном случае

. (2.6)

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (2.4), (2.5) найти такое решение , при котором значение линейной функции (2.6) минимально.

Произвольное допустимое решение системы ограничений (2.4), (2.5) назовем распределением поставок. Такое решение задает заполнение таблицы поставок, поэтому в дальнейшем значение произвольной переменной и содержимое соответствующей клетки таблицы поставок будут отождествляться.

Транспортная задача, приведенная в примере 1, обладает важной особенностью: суммарная мощность поставщиков не равна суммарному спросу потребителей, т.е.

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

Для решения открытой транспортной задачи необходимо свести ее к закрытому виду.

Поскольку в представленной транспортной задаче суммарный спрос потребителей меньше суммарной мощности поставщиков на 90:

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

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

Поставщики	Мощность поставщиков	Потребители
B ₁	B ₂	B ₃	B ₄	B ₅

A ₁		x ₁₁	x ₁₂	x ₁₃	x ₁₄	x ₁₅
A ₂		x ₂₁	x ₂₂	x ₂₃	x ₂₄	x ₂₅
A ₃		x ₃₁	x ₃₂	x ₃₃	x ₃₄	x ₃₅

С учетом фиктивного поставщика математическая модель будет иметь вид: