Новости

Принимаются заказы на решение задач, контрольных работ по:

• математическому программированию,
• теории вероятностей и математической статистике,
• математическому анализу,
• дифференциальным уравнениям,
• аналитической геометрии и линейной алгебре;

Симплекс-метод.
Часть 2

Общая схема симплекс-метода. Рассмотрим задачу ЛП в канонической форме, где система ограничений задана совместной системой линейных уранений

{a₁₁x₁ + a₁₂x₂ + ... + a_1nx_n = b₁,
{a₂₁x₁ + a₂₂x₂ + ... + a_2nx_n = b₂,
{.............................................,
{a_m1x₁ + a_m2x₂ + ... + a_mnx_n = b_m.

и среди неотрицательных решений этой системы нужно найти такое, которое минимизирует линейную функцию

f = c₁x₁ + c₂x₂ + ... + c_nx_n + c₀.

Пусть можно выразить x₁, x₂, ... , x_r (r < m) через остальные переменные:

{x₁ = a'_1,r+1x_r+1 + ... + a'_1nx_n + b'₁,
{x₂ = a'_2,r+1x_r+1 + ... + a'_2nx_n + b'₂,
{...............................................,
{x_r = a'_r,r+1x_r+1 + ... + a'_{r n}x_n + b'_r,

где b'₁ > 0, b'₂ > 0, ... , b'_r > 0. Переменные x₁, x₂, ... , x_r называются базисными, а весь набор {x₁, x₂, ... , x_r} - базисом, остальные переменные называются свободными, система ограничений называется системой, приведенной к единичному базису.

Подставляя в линейную форму вместо базисных переменных их выражения через свободные из системы, получим

f = d + d_r+1x_r+1 + ... + d_nx_n.

Теперь, полагая все свободные переменные равными нулю, найдем значения базисных переменных: x₁ = b'₁, x₂ = b'₂, ... , x_r = b'_r. Таким образом, решение col(b'₁;b'₂;...;b'_r;0;...;0) системы является допустимым - оно называется базисным.

Для получения базисного решения значение линейной формы f_Б = d. Решение задачи с помощью симплекс-метода распадается на ряд шагов, заключающихся в том, что от данного базиса Б переходят к другому базису Б' с таким расчетом, чтобы значение f_Б' уменьшилось или, по крайней мере, не увеличилось, т.е. f_Б' < f_Б.

Реализация симплекс-метода в одном частном случае. Для упрощения дальнейших записей будем считать, что имеется всего пять неизвестных x₁,x₂,x₃,x₄,x₅< /nobr> и система ограничений приведена к единичному базису {x₁, x₂, x₃}:

{x₁ = A₄x₄ + A₅x₅ + A,
{x₂ = В₄x₄ + В₅x₅ + В,
{x₃ = Г₄x₄ + Г₅x₅ + Г,

(где А > 0, В > 0, Г > 0),

а целевая функция к виду - f = d + d₄x₄ + d₅x₅.

Решается задача минимизации f при соответствующих огрничениях и условиях x₁ > 0, x₂ > 0, x₃ > 0, x₄ > 0, x₅ > 0.

Положим все свободные переменные равгыми нулю (x₄ = 0, x₅ = 0). и найдем из системы значения базисных неизвестных: x₁ = А, x₂ = В, x₃ = Г. Полученное решение системы col(А;В;Г;0;0) будет неотрицательным и является базисным решением, отвечающим базису {x₁, x₂, x₃}.

Для этого решения значение функции f равно f_Б = d.

Возможны три случая.

1) Все коэффициенты при свободных неизвестных в выражении для f неотрицательны, т.е. d₄ > 0, d₅ > 0.

Тогда для любого неотрицательного решения системы имеем d₄x₄ > 0, d₅x₅ > 0. Значит, f = d₄x₄ + d₅x₅ + d > d. Таким образом, min f = d, т.е. базисное решение оптимально и задача решена.

2) Имеется свободное неизвестное, коэффициент при котором в выражении f отрицателен, а все коэффициенты при этом неизвестном в уравнениях системы - положительны.

Пусть, например, d₄ < 0, А > 0, В > 0, Г > 0. Тогда, отправляясь от базисного решения col(А;В;Г;0;0), будем увеличивать значение x₄, не меняя x₅ = 0. Значения базисных переменных также будут меняться, получим

x₁ = A₄x₄ + A > A > 0,
x₂ = В₄x₄ + В > В > 0,
x₃ = Г₄x₄ + Г > Г > 0,

т.е. допустимое решение col(x₁;x₂;x₃;x₄;0) будет оставаться неотрицательным. При этом f = d₄x₄ + d с ростом x₄ будет неограниченно уменьшаться, так как d₄ < 0.

Значит, в этом случае min f = - оо на X, т.е. задача не имеет решения.

3) Имеется свободное неизвестное, коэффициент при котором в неотрицателен, но и среди коэффициентов при этом неизвестном также есть отрицательные.

Тогда производим шаг, а именно, от базиса Б переходим к новому базису Б', с таким расчетом, чтобы значение f_Б' уменьшилось или, по крайней мере, не увеличилось, т.е. f_Б' < f_Б.

Ясно, что изменение базиса влечет за собой соответствующую перестройку системы ограничений и выражения для функции f.

Опишем подробно содержание шага. Пусть, например, в случае d₄ < 0 имеем А₄ < 0, В₄ < 0, а Г₄ > 0.

Так как А₄ < 0 и В₄ < 0, то значения x₁ = A₄x₄ + A и x₂ = В₄x₄ + В будут уменьшаться при увеличении x₄, а значение x₃ будет оставаться неотрицательным (x₃ > Г). При увеличении x₄ наступит момент, когда одно из неизвестных x₁ или x₂ обратится в нуль: для x₁ таким моментом будет x₄ = -(A/A₄), а для x₂ будет x₄ = -(В/В₄). Выберем из этих соотношений -(A/A₄) и -(В/В₄) наименьшее. Пусть, например, это будет -(A/A₄) = p. Тогда увеличение x₄ возможно только от 0 до р. При x₄ = p неизвестное x₁ обратится в нуль, а при дальнейшем увеличении x₄ неизвестное x₁ станет уже отрицательным, что недопустимо. Полагая в системе x₄ = p и x₅ = 0, получим неотрицательное решение

x₁ = 0,
x₂ = В₄р₄ + В,
x₃ = Г₄р₄ + Г,
x₄ = р,
x₅ = 0,

для которого значение функции f будет d₄p + d < d поскольку d₄ < 0 и p > 0.

Таким образом, с ростом x₄ первым из базисных переменных обращается в нуль переменное x₁. Тогда базис Б = {x₁;x₂;x₃} заменяем на базис Б' = {x₄;x₂;x₃}, а именно: из старого базиса удаляется неизвестное x₁ и вместо него в базис вводится из числа прежних свободных неизвестное x₄.

Смена базиса влечет за собой перестройку системы. Из первого уравнения для x₁ выражаем x₄:

x₄ = (1/A₄)x₁ - (A₅/A₄)x₅ - A/A₄. Подставляем это выражение в остальные два уравнения системы. Получим систему вида

{x₄ = а₁x₁ + а₅x₅ + а,
{x₂ = b₁х₁ + b₅x₅ + b,
{x₃ = c₁x₁ + c₅x₅ + c,

с базисным решением

x₁ = 0,
x₂ = b,
x₃ = с,
x₄ = a,
x₅ = 0.

Как видно из самой системы, двух разных значений с x₁ = 0, x₅ = 0 быть не может, и, значит, является неотрицательным.

Новое значение целевой функции f равно

Пример. Найдем минимум линейной формы f = x₄ - x₅ при ограничениях: x₁ + x₄ - 2x₅ = 1, x₂ - 2x₄ + x₅ = 2, x₃ + 3x₄ + x₅ = 3 и условиях x_i > 0, i = 1,2,3,4,5.

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

x₁ = 1 - х₄ + 2x₅,
x₂ = 2 + 2х4 - x₅,
x₃ = 3 - 3x4 - x₅.

Линейная форма f = x₄ - x₅ через свободные переменные уже выражена. Теперь при x₄ = 0, x₅ = 0 найдем значения базисных переменных: x₁ = 1, x₂ = 2, x₃ = 3. Таким образом, первое допустимое решение системы уравнений есть col(1;2;3;0;0). При найденном допустимом решении имеем f_Б = 0.

Теперь попытаемся уменьшить значение f. Увеличение x₄ увеличит f, так как перед x₄ стоит положительный коэффициент, а увеличение x₅ дает уменьшение f. Увеличим величину x₅ так, чтобы x₁, x₂, x₃ не стали отрицательными, оставив x₄ = 0. Из второго уравнения следует, что x₅ можно увеличить до 2. Таким образом, получаем следующие значения переменных: x₁ = 5, x₂ = 0, x₃ = 1, x₄ = 0, x₅ = 2 или col(5;0;1;0;2).

Значение целевой функции при этом допустимом решении равно f_Б' = -2, т.е. уменьшилось.

Далее, примем за свободные переменные x₂ и x₄, т.е. те переменные, которые в новом базисе имеют нулевые значения. Тогда

{x₁ = 5 - 2х₂ + 3x₄,
{x₃ = 1 + х₂ - 5x₄,
{x₅ = 2 - x₂ + 2x₄.

f = -2 + x₂ - x₄.

Для уменьшения значения f будем увеличивать x₄. Из второго уравнения системы вытекает, что при условии неотрицательности x₃ значение x₄ можно увеличивать до x₄ = 1/5. При этом условии новое допустимое решение есть col(28/5;0;0;1/5;12/5). Значение линейной формы f_Б' = -11/5.

Выразим теперь x₁, x₄, x₅ через свободные переменные x₂ и x₃:

{x₁ = 28/5 - (3/5)х₃ - (7/5)x₂,
{x₄ = 1/5 - (1/5)х₃ + (1/5)x₂,
{x₅ = 12/5 - (2/5)x₃ - (3/5)x₂.

f = -11/5 + (1/5)x₃ + (4/5)x₂.

Так как в последней линейной форме обе свободные переменные входят с положительными коэффициентами, то наименьшее значение f достигается при x₂ = 0, x₃ = 0. Значит, решение col(28/5;0;0;1/5;12/5) является оптимальным и min f = -11/5.

Свои вопросы присылайте по адресу mathematician@home.tula.net.

Математика для экономистов на базе Mathcad.
Урок 2

Индексы матриц и векторов в Mathcad могут принимть целые неотрицательные значения. Начало индексации (нумерации) строк и столбцов матриц задается системной переменной ORIGIN. Например, ORIGIN:=0 означает, что нумерация строк и столбцов начинается с нуля. По умолчанию значение переменной ORIGIN равно нулю.

Ввод элементов матрицы аналогичен вводу координат векторов (см. Урок 1). Пусть, к примеру, нало ввести матрицу

В нужном месте рабочего листа введите имя матрицы mat и знак присваивания :=. Затем выведите диалоговое окно Вставить матрицу (Insert Matrix). В поле Строк (Rows) этого окна надо задать число строк 3, а в поле Колонок (Columns) - число столбцов 2. После щелчка кнопкой ОК справа от знака присваивания появится шаблон матрицы с метками для ввода ее элементов.

Чтобы извлечь элемент матрицы, находящийся на позиции (i,k), необходимо набрать имя матрицы с индексами i, k (индексы - через запятую) в случае равенства ORIGIN единице или с индексами i-1, k-1 в случае равенства ORIGIN нулю. Рассмотрим, например, элемент 8.2 матрицы mat, который находится на позиции (3,2). Предположим, что ORIGIN равно нулю. Для извлечения элемента 8.2 наберите имя матрицы mat, затем комбинацией клавиш <Ctrl>+<[> перейдите в режим ввода индексов. Введите на месте метки индексы 2, 1. Клавишей <=> введите знак равенства, справа от которого появится искомый элемент: mat_2,1=8.2.

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

Стандартные функции rows(M) и cols(M) определяют соответственно число строк и столбцов матрицы М. Например, rows(mat)=3 и cols(mat)=2.

Задача 1. Предприятие выпускает m видов продукции с использованием n видов сырья. Нормы расхода сырья даны в матрице А, в которой на позиции (i,k) находится число, равное количеству расходуемого сырья (кг) k-го вида на производство единицы продукции i-го вида. Плановый объем выпуска продукции дан в векторе-строке Q, в которой i-й элемент равен количеству единиц продукции i-го вида. Вектор-строка S задает себестоимость единицы сырья каждого вида, а вектор-строка t задает транспортные расходы на единицу сырья каждого вида (k-е элементы этих векторов соответствуют k-му виду сырья). Пользуясь только умножением матриц, найти: количество сырья каждого вида для выполнения планового выпуска продукции; производственные и транспортные затраты на сырье, расходуемое на производство единицы продукции каждого вида; затраты на все сырье, необходимое для выполнения плана.

Q = (160, 125, 140, 311, 83),
S = (150, 22, 13, 15, 81, 211, 400),
Q = (8, 2, 3, 3, 2, 4, 1).

Задача 2. Данные о дневной производительности 6 предприятий, выпускающих 5 видов продукции, приведены в матрице

в которой на позиции (i,k) находится дневная производительность (изделий в день) k-го предприятия по i-му виду продукции. Нормы расхода сырья трех видов даны в матрице

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

r = (250, 222, 175, 124, 140, 140),
S = (0.5, 150, 124).

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

Решение. Ввести исходные данные: матрицы А, В, векторы-строки r, c. Определить годовую производительность каждого предприятия по каждому виду продукции:

ORIGIN:=1 n:= cols(A) k:=1;n C^<k>:=A^<k>*r_1,k

(в матрице С на позиции (i,k) будет число, равное годовой производительности k-го предприятия по i-му виду продукции).

Определить годовую потребность каждого предприятия по каждому виду сырья: D:=B^T*C (в матрице D элемент на позиции (i,k) будет равен годовой потребности k-го предприятия в i-м виде сырья).

Определить годовую сумму кредитования каждого предприятия для закупки сырья, необходимого для выпуска всей продукции d:=c*D (в вектор-строке d k-й элемент равен сумме, которая необходима для закупки сырья всех видов k-м предприятием).

Свои вопросы, решения задач 1 и 2 присылайте по адресу mathematician@home.tula.net.

Анализ безубыточности.
Часть 1

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

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

Для расчета объема выручки, покрывающего постоянные и переменные издержки фирмы, целесообразно использовать такую величину, как сумма покрытия. Расчет суммы покрытия позволяет определить, сколько средств зарабатывает фирма, производя и реализуя свою продукцию с тем, чтобы окупить постоянные издержки и получить прибыль. Понятие средней величины покрытия используется, когда речь идет не о выручке фирмы в целом, а о цене отдельного товара. Расчет суммы и средней величины покрытия дает возможность определить также точку безубыточности.

Сумма покрытия, средняя величина покрытия, коэффициент покрытия

Суммой покрытия называется разница между выручкой от реализации и всей суммой переменных затрат (издержек). Ее можно рассчитать и подругому - как сумму постоянных затрат (издержек) и прибыли. Для расчета суммы покрытия из выручки необходимо вычесть все прямые затраты, а также часть накладных расходов, которые зависят от объма производства и поэтому относятся к категории переменных затрат.

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

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

Коэффициентом покрытия называется доля суммы покрытия в выручке от реализации или (для отдельного товара) доля средней величины покрытия в цене товара.

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

Пример 1. Фирма выпускает и продает товар, средние переменные издержки на производство и сбыт которого составляют 100 руб./шт. Товар продается по цене 120 руб. Постоянные затраты фирмы в месяц составляют 60 тыс. руб. Рассчитаем, какую прибыль может получить фирма в месяц, если она продаст даного товара 4000, 5000, 6000 шт.

Поскольку постоянные затраты фирмы не зависят от объема выпуска, найдем сумму покрытия и прибыль (как разность суммы покрытия и постоянных издержек) для всех трех вариантов (cм табл. 1).

Таблица 1. Прибыль фирмы при различных объемах выпуска, тыс. руб.

Так как величина покрытия одинакова для всех трех вариантов, расчет прибыли можно упростить. Определим прибыль фирмы при любом объеме выпуска. Для этого:

1) умножив среднюю величину покрытия на объем выпуска, получим сумму покрытия;

2) от суммы покрытия отнимем постоянные издержки.

Например, какую прибыль получит фирма, если произведет и продаст 4560 шт. товара?

Сумма покрытия: 20 руб. * 4560 = 91,2 тыс. руб.

Прибыль: 91,2 тыс. руб. - 60 тыс. руб. = 31,2 тыс. руб.

Пример 2. Фирма производит и продает одновремено два товара: А и Б. Данные об объемах продаж, ценах и затратах приведены в табл. 2.

Таблица 2. Объемы продаж, цены товаров А и Б и издержки производства.

Предположим, что требуется определить:

1) размер прибыли, получаемой фирмой за месяц;

2) среднюю величину покрытия для каждого товара;

3) коэффициент покрытия для каждого товара;

4) размер прибыли, который получит фирма, если расширит продажу товара А до 7000 шт., а товара Б - до 4500 шт.

Для ответа на поставленные вопросы все необходимые данные сведены в табл. 3.

Таблица 3. Порядок расчета средней величины и коэффициента покрытия, а также размера прибыли фирмы.

Итак, за месяц фирма зарабатывает 10 тыс. руб. прибыли. Средняя величина покрытия для товара А составляет 8 руб. (коэффициент покрытия 0,154), для товара Б - 13 руб. (коэффициент покрытия 0,144).

При расширении объема продаж фирма получит:

1) сумма покрытия от продажи товара А: 8 руб.*7000 = 56 тыс. руб.;
2) сумма покрытия от продажи товара Б: 13 руб.*4500 = 58,5 тыс. руб.;
3) сумма покрытия от продажи товаров А и Б: 56 тыс. руб. + 58,5 тыс. руб. = 114,5 тыс. руб.;
4) постоянные издержки фирмы: 90 тыс. руб.;
5) прибыль фирмы: 114,5 тыс. руб. - 90 тыс. руб. = 24,5 тыс. руб.

Пример 3. Компания производит и реализует один товар, переменные затраты на единицу которого приведены ниже, руб.:

Сырье и материалы: . . . . . . . . . . . . . . 20
Заработная плата:  . . . . . . . . . . . . . . 16
Переменные производственные накладные расходы:  8
Переменные сбытовые накладные расходы: . . . .  4
-------------------------------------------------
И т о г о  . . . . . . . . . . . . . . . . . . 48

Товар продается по цене 60 руб. за 1 шт., постоянные затраты составляют 136 тыс. руб. Определим, какое количество товара должна продать компания, чтобы обеспечить получение 32 тыс. руб. прибыли?

1. Для решения этой задачи найдем сумму покрытия. Ее можно определить как разницу между валовой выручкой и переменными затратами, а также как сумму постоянных затрат и прибыли:

136 тыс. руб. + 32 тыс. руб. = 168 тыс. руб.

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

60 руб. - 48 руб. = 12 руб.

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

168 тыс. руб. : 12 руб./шт. = 14 тыс. шт.

Пример 4. Фирма желает продать 20 тыс. шт. товара. Средние переменные издержки на производство и реализацию составляют 15 руб. Постоянные издержки - 250 тыс. руб. Фирма планирует получить прибыль в размере 50 тыс. руб. По какой цене следует продавать товар?

1. Найдем сумму покрытия, прибавив к постоянным издержкам планируемый объем прибыли:

250 тыс. руб. + 50 тыс. руб. = 300 тыс. руб.

2. Найдем среднюю величину покрытия, разделив сумму покрытия на количество продаваемых товаров:

300 тыс. руб. : 20 тыс. шт. = 15 руб./шт.

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

15 руб. + 15 руб. = 30 руб.

Свои вопросы присылайте по адресу mathematician@home.tula.net.

Содержание рассылки зависит и от Вас: чем активнее Вы проявляете свою заинтересованность в той или иной теме, задаете те или иные вопросы - тем полезнее рассылка будет для каждого из Вас! Пишите: mathematician@home.tula.net.