Менеджмент: конспект лекций

Шевчук Денис Александрович

Х 1 + 2/3 Х 2 + 2/1,2 Х 3 + 200 Х 4 = 20000,

7/900 Х 2 + 4/900 Х 3 – 2/3 Х 4 + Х 5 = 100/3,

Х 3 / 80 + Х 6 = 100,

2 Х 2 – 11 Х 3 – 3000 Х 4 = F – 300000.

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

Х 1 = 20000, Х 2 = Х 3 = Х 4 = 0, Х 5 = 100/3, Х 6 = 100, F = 300000.

В

терминах исходной задачи это решение означает, что надо выпускать только кухни. Такое решение приемлемо, если допустимо выпускать только один вид продукции.

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

20000 / (2/3) = 30000, (100/3) / (7/900) = 30000/7, 100/0 = + ∞.

Таким образом, нужно выбрать вторую строку, для которой имеем наименьшее положительное отношение 30000/7. Вторую строку умножим на 900/7 (чтобы коэффициент при Х 2 равнялся 1). Затем добавим обновленную строку ко всем строкам, содержащим Х 2, предварительно умножив их на подходящие числа, т. е. такие, чтобы все коэффициенты при Х 2 стали бы после сложения равны 0, за исключением коэффициента второй строки, который уже стал равняться 1. Получим систему уравнений:

Х 1 + 9/7 Х 3 + 1800/7 Х 4 – 600/7 Х 5 = 120000/7,

Х 2 + 4/7 Х 3 – 600/7 Х 4 + 900/7 Х 5 = 30000/7,

Х 3 / 80 + Х 6 = 100,

– 85/7 Х 3 – 19800/7 Х 4 – 1800/7 Х 5 = F – 308571.

Поскольку все переменные неотрицательны, то из последнего уравнения следует, что прибыль F достигает своего максимального значения, равного 308571, при Х 3 = Х 4 = Х 5 = 0. Из остальных уравнений следует, что при этом Х 1 = 120000/7 = 17143, Х 2 = 30000/7 = 4286, Х 6 = 100. Поскольку в строке с F не осталось ни одного положительного коэффициента при переменных, то алгоритм симплекс—метода закончил свою работу, оптимальное решение найдено.

Практические рекомендации таковы: надо выпустить 17143 кухни, вчетверо меньше, т. е. 4286, кофемолок, самоваров не выпускать вообще. При этом прибыль будет максимальной и равной 308571. Все производственное оборудование будет полностью загружено, за исключением линии по сборке самоваров.

Транспортная задача. Различные технико—экономические и экономические задачи менеджмента, от оптимальной загрузки станка и раскройки стального листа или полотна ткани до анализа межотраслевого баланса и оценки темпов роста экономики страны в целом, приводят к необходимости решения тех или иных задач линейного программирования. В качестве очередного примера рассмотрим т. н. транспортную задачу. Имеются склады, запасы на которых известны. Известны потребители и объемы их потребностей. Необходимо доставить товар со складов потребителям. Можно по—разному организовать «прикрепление»

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

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

Рассмотрим пример транспортной задачи, исходные данные к которой представлены в табл. 3. В ней, кроме объемов потребностей и величин запасов, приведены стоимости доставки единицы товара со склада i, i = 1,2,3, потребителю j, j = 1,2,3,4. Например, самая дешевая доставка – со склада 2 потребителям 1 и 3, а также со склада 3 потребителю 2. Однако на складе 2 имеется 80 единиц товара, а потребителям 1 и 3 требуется 50+70 =120 единиц, поэтому к ним придется вести товар и с других складов. Обратите внимание, что в табл.3 запасы на складах равны суммарным потребностям. Для примера с доставкой песка кирпичным заводам это вполне естественное ограничение – при невыполнении такого ограничения либо порты будут засыпаны горами песка, либо кирпичные заводы не выполнят заказы.

Надо спланировать перевозки, т. е. выбрать объемы Х ij поставок товара со склада i потребителю j , где i = 1,2,3; j = 1,2,3,4. Таким образом, всего в задаче имеется 12 переменных. Они удовлетворяют двум группам ограничений. Во—первых, заданы запасы на складах:

X 11 + Х 12 + Х 13 + Х 14 = 60,

X 21 + Х 22 + Х 23 + Х 24 = 80,

X 31 + Х 32 + Х 33 + Х 34 = 60.

Во—вторых, известны потребности клиентов:

X 11 + Х 21 + Х 31 = 50 ,

X 12 + Х 22 + Х 32 = 40 ,

X 13 + Х 23 + Х 33 = 70 ,

X 14 + Х 24 + Х 34 = 40 .

Итак, всего 7 ограничений типа равенств. Кроме того, все переменные неотрицательны – еще 12 ограничений.

Целевая функция – издержки по перевозке, которые необходимо минимизировать:

F = 2 X 11 + 5 Х 12 + 4 Х 13 + 5 Х 14 + X 21 + 2 Х 22 + Х 23 + 4 Х 24 +