Контрольные вопросы и задания

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

а)

б)

в)

2. Составьте двойственную задачу и обе задачи решите графически:

а)

б)

в)

3. Для следующих задач линейного программирования составьте двойственные. Одну из взаимно-двойственных задач решите графически. Решение другой найдите, опираясь на основные теоремы двойственности:

а)

б)

в)

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

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

6. Какую можно дать экономическую интерпретацию следующим равенствам в задачах А₂ и В₂:

а) x₄ = 0; б) x₃ = 0; в) y₄ = 0; г) y₅ = 5?

§ 4. Повысим рентабельность. Задача дробно-линейного программирования

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

Задача. Завод выпускает продукцию n видов P₁, P₂, ..., P_n. В процессе производства используются k видов сырья S₁, S₂, ..., S_k, запасы которого ограниченны. Требуется составить производственный план таким образом, чтобы обеспечить максимально возможную рентабельность завода. Нормы расхода дефицитных видов сырья, его запасы, а также удельные и условно-постоянные затраты и прибыль, получаемая заводом от реализации одного изделия, приведены в таблице:

Сырьё Продукция	S1, S2, ..., Sj..., Sk нормы расхода сырья на 1 изделие	Удельные затраты на 1 изделие	Прибыль от реализации изделия
P1 P2 : Pi : Pn	a11 a21 ... aj1 ... ak1 a12 a22 ... aj2 ... ak2 ... a1i a2i ... aji ... aki ... a1n a2n ... ajn ... akn	b1 b2 : bi : bn	c1 c2 : ci : cn
Запасы сырья	a10 a20 ... aj0 ... ak0	Условно-постоянные      b0               затраты

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

1. Условно-переменные затраты – те затраты, которые изменяются прямопропорционально объёмам выпуска товаров. К ним относятся затраты на материалы, энергию, комплектующие изделия, заработную плату.

2. Условно-постоянные затраты – те затраты, которые практически не зависят от изменения количества выпущенной продукции.

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

Решение. Построение математической модели начинаем с введения переменных, относительно которых будет решаться задача. Обозначим через x₁, x₂,..., x_n объёмы выпуска продукции P₁, P₂,..., P_n соответственно.

Прибыль от реализации продукции, произведённой в указанном количестве составит

денежных единиц, а затраты на производство будут равны сумме условно-переменных и условно-постоянных затрат

.

Получим выражение для подсчёта рентабельности:

.

Функция цели построена.

Затраты первого ресурса на производство x₁ единиц продукции P₁ находим, умножая нормы расхода сырья a₁₁ на объём выпуска x₁:

.

Так же определяем затраты S₁ на производство продукции второго, третьего и всех других видов:

.

Сумма этих произведений даёт величину затрат первого ресурса на все виды продукции. Запасы S₁ ограниченны, поэтому его суммарные затраты не должны превосходить a₁₀. Приходим к первому ограничению по запасам сырья:

.

Таким же образом получаем ограничения для S₂, S₃,..., S_n:

Каждый коэффициент a_ij имеет два индекса, указывающие на его положение в системе (как номер вашего дома на улице и квартиры, где вы живёте): первый индекс указывает номер уравнения, а второй – номер переменной, к которой относится коэффициент.

Учитывая, что все неотрицательны, получаем следующую математическую задачу:

Среди решений системы ограничений

(1)

найти такое (такие), при котором функция цели z достигнет своего наибольшего значения:

(2)

.

Теперь нам предстоит выбрать метод решения сформулированной задачи. Для этого сначала проанализируем её условие. В этой задаче математического программирования система ограничений (1) состоит из линейных неравенств, а функция цели (2) представляет собой отношение двух линейных функций.

Такие задачи называют задачами дробно-линейного программирования. Как же их решать? Оказывается, что задачи этого класса легко сводятся к задаче линейного программирования.

Обозначим через знаменатель функции цели (2)

b₁x₁ + b₂x₂ + … + b_nx_n +b₀ = .(3)

Очевидно, ν > 0.Умножим на него обе части уравнения (3), такую же операцию проделаем с каждым неравенством системы (1). Получим:

(4)

Функция цели z, с учетом введенного обозначения (3), запишется так:

(5)

Если обозначить через, то система (4) и функция (5) примут вид:

(6)

(7)

Задача (6) –(7) – задача линейного программирования. Решив ее относительно и ν , можем найти соответствующие оптимальные значения. Для этого достаточно воспользоваться формулами перехода:

(8)

Максимальное значение функции (7), очевидно, совпадает с максимальным значением дробно-линейной функции цели (2).

Пример. Проведем подробное решение задачи на максимализацию рентабельности для предприятия, выпускающего два вида продукции P₁ и P₂ при наличии двух дефицитных ресурсов S₁ и S₂. Под S₁ можем понимать, например затраты электроэнергии, а под S₂ – трудовые ресурсы. Предположим также, что при подсчете рентабельности будем учитывать лишь чистую прибыль предприятия (часть прибыли, остающаяся в распоряжении предприятия после уплаты налогов и внесения других обязательных платежей). Данные необходимые для решения задачи, приведены в таблице (в расчете на тысячу изделий):

Ресурсы Продукция	S1	S2	Удельные затраты на производство (в млн.руб.)	Прибыль от реализации (в млн.руб.)
	Нормы расхода сырья (в тыс.руб.)
P1 P2	1,8 0,2	2,55 1,2	0,01 0,04	0,012 0,008
Запасы ресурсов (тыс.руб.)	20	45	Условно-постоянные затраты (в млн.руб.)

Пусть x₁ и x₂ соответственно объемы выпуска изделий первого и второго видов (в тыс.штук). Тогда чистая прибыль от реализации этих изделий составит

а затраты на производство будут равны

Рентабельность вычисляется по формуле:

(9)

Ограничения по затратам электроэнергии и трудовых ресурсов запишем в виде неравенств

(10)

Учитывая неотрицательность переменных и, а также (9) и (10), получаем задачу дробно-линейного программирования:

(11)

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

(12)

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

С учетом (12) преобразуем функцию цели:

Введем новые переменные:

(13)

Окончательная задача запишется так:

(14)

Это задача линейного программирования. Решим ее. Прежде всего исключим переменную ν из первых двух ограничений. Для этого к первому неравенству прибавим третье ограничение, умноженное на 20, а ко второму неравенству прибавим это уравнение, умноженное на 45. Система ограничений примет вид:

Из уравнения выразим ν через и:

(15)

Теперь мы можем отбросить положительное ν в третьем ограничении. Баланс нарушается. Уравнение заменится неравенством. В результате проведенных преобразований получим задачу линейного программирования с ограничения ми-неравенствам, содержащую всего две переменные и.

(16)

Эту вспомогательную задачу решим графически. Для построения граничных прямых используем, например, следующие пары точек:

,

Рис.6

Область допустимых решений системы ограничения имеет вид четырехугольника Нормаль к опорной прямойпредставлена векторомЭтот вектор, очевидно коллинеарен векторукоторый неудобен для изображения. Для задачи на максимизацию функции цели оптимальное решение находится в точке выхода из области допустимых решений. Это точка В. Найдем ее координаты. С этой целью решим систему, составленную из уравнений прямыхI и II:

Решив эту систему, найдем Получим:

и

.

Вспомогательная задача решена. Воспользуемся формулами перехода (15) и (13) для отыскания Прежде всего определим величину

Теперь найдем и:

Округляем результаты до 0,01. С указанной точностью запишем ответ задачи:

Итак, при плане тыс. штук,тыс. штук рентабельность составит 14%.

Вопрос. Можно ли результат округлить до целых десятых, до тысячных? Почему?

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

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

Сначала построим область допустимых планов (рис7).

рис.7.

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

Это уравнение можно преобразовать к виду

Очевидно, что при каждом постоянном значении α, это уравнение задает прямую, так как его можно записать в виде

Кроме того, все прямые проходят через точкуS, в которой равны нулю оба выражения, стоящие в числителе и в знаменателе целевой функции. Действительно, в этой точке уравнение превращается в равенствокоторое справедливо при любом значении α.

Точка S не входит в область допустимых значений целевой функции. Семейство прямых имеет вид, представленный на рисунке 8. Это пучок прямых на плоскости, проходящих через точкуS (но не содержащие ее).

рис.8.

Изменяя α, мы будем «вращать» вокруг точки S линию уровня . При вращении в одну сторону значение целевой функции будет увеличиваться, а при вращении в другую – уменьшаться.

Найдем координаты точки S. Для этого нужно решить систему уравнений

Применяя какой-либо способ решения, находим (проверьте это!).

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

,

так как

Поэтому В точка максимума. Ее координаты находим из системы уравнений, задающих прямые и

Умножим на 6 обе части первого уравнения и вычтем из них соответствующие части второго уравнения. Получим т.е.

Подставив в первое уравнение, находим:

Далее определяем значение целевой функции В процентах это значение равно 14%.

Ответ: максимальная рентабельность 14% достигается при и

Выводы:

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

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

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

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

4. Оптимальные значения функции цели основной и вспомогательной задачи совпадают.