<<
>>

4.1.2. Постановка и методика решения ассортиментной задачи симплексным методом

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

Эту задачу часто в экономической работе называют ассортиментной. Еще она известна как задача планирования и организации производства. В математическом виде эту задачу можно выразить следующим образом: найти максимум целевой функции

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



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

—              количество производимой продукции у-го вида;

—              расход г-го вида ресурса (сырья и материалов, производственной мощности, трудовых ресурсов) на единицу у-го вида продукции в процессе производства;

—              ограничения по г-му виду ресурса;

—              максимальное ограничение на объем производства k-го вида продукции;

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

Общее условие ассортиментной задачи представлено в виде табл. 4.1.

Количество производимого продукта обозначают через х1, х2, х3, х4, х5. В задаче некоторые Ху могут быть равны нулю. Отрицательных Ху быть не может, так как переход продукта в сырье и материалы невозможен.

Таблица 4.1

Ресурсы

Норма расхода на единицу продукции

Запасы

В1

В2

В

Вп

I (сырье, кг)

а11

а12

a1j

a1n

b1

i (материалы, кг)

ai1

ai2

aij

ain

b

m (полезный фонд времени работы оборудования, машино-час)

am1

am2

amj

a

mn

bm

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

П1

П2

П

П

n

В качестве примера условия задачи даны в табл. 4.2. Потребление первых видов сырья (материалов) составляет:


Таблица 4.2

Ресурсы

Расход на 1 т продукта

Запасы, т

В1

В2

В3

В4

В5

Сырье (материалы)

I вида

5

4

6

10

3

2700

II вида

3

3

1

2

3

1000

Производственная

4

1

5

4

1

1000

мощность

Прибыль, получаемая

5

3

4

6

4

от производства 1 т

продукта

Потребление сырья не может быть больше имеющегося в наличии количества сырья (материалов) данного вида, т.е.

2700 т. Рассуждая аналогично, можно выразить задачу в виде следующих неравенств:

Необходимо определить такиечтобы получить максимум прибыли:

4              -              1              23              4              5

Неравенства обращают в равенства, добавляя дополнительные переменные:

Дополнительные переменные показывают количество соответствующего неиспользованного сырья, которое может остаться на складе. Например, х6 — количество неиспользованного сырья первого вида, х7 — сырья второго вида, х8 — неиспользованная мощность предприятия. Дополнительные переменные хв, x7, х8 не спо-

собствуют увеличению прибыли, так как не участвуют в производстве, поэтому в линейной форме L(x) эти переменные записывают с коэффициентом прибыли, равным нулю.

Составляют симплексную таблицу (табл. 4.3). В столбце с записывают нули, так как за базис принимают дополнительные переменные, которые равны соответственно 2700, 1000, 1000, т.е.:

В столбце Xj проставляют коэффициенты при соответствующих неизвестных в уравнениях. Значение последней строки L(x) получается при вычислении разности между суммой произведений элементов столбца Cj для базисных переменных на соответствующие элементы столбца Xj (j = 1, 2, ..., 8) и значением с в линейном функционале L(x) для данной переменной.

Для следующих столбцов:

и т.д.

Переменную, которая находится в колонке, выделенной жирным шрифтом (табл. 4.3), вводят в базис, так как она способствует большому увеличению прибыли. Такой переменной в данном случае является х4, у которой значение L^) = —6. Чтобы выяснить, какую переменную необходимо удалить из базиса для введения х4, находят положительные значения делением соответствующих элементов столбца х0 на элементы ключевого столбца (на нуль и на отрицательные числа ключевого столбца не делят).


Средивыбирают наименьшее положительное (i = 1, 2, 3 — номера строк). Ключевая строка показывает, что необходимо вывести переменную х8. После составления первоначальной программы

приступают к следующей. В табл. 4.4 в базисе х6, х7, х4 (введена вместо х8 со значением с4 = +6). Преобразуют ключевую строку, производя деление элементов ключевой строки на главный элемент 4. Результат записывают в шестую строку табл. 4.4. Это правило можно представить в виде формулы

где 1000 — элемент столбца х0 в третьей строке;

4 — главный элемент, лежащий на пересечении третьей строки и четвертого столбца.

Для небазисных переменных следующих столбцов Остальные значения для других строк определяют по формуле

Ключевой элемент преобразуемой строки лежит на пересечении преобразуемой строки и ключевого столбца (табл.

4.3). Элемент преобразованной ключевой строки берется в том же столбце х. (j = 1, 2, ..., 8), для которого определяют новый элемент в новой таблице (табл. 4.4).

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


Аналогично вычисляют пятую строку для табл. 4.4.

После выбора ключевой строки и ключевого столбца переходят к заполнению следующей симплексной таблицы (табл. 4.5). Необходимо отметить, что в ней значение линейной функции L(x) возрастает до 1500, причиной чего служит переменная x4, которая вошла в базис. Экономический смысл нового допустимого плана, приведенного в табл. 4.5, состоит в том, что по нему рекомендуется производить продукцию В4 в объеме 250 ед.

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

а)              если строка L(x) имеет отрицательные числа, над которыми имеются положительные элементы, то программа требует улучшения;

б)              если над отрицательными числами в строке L(x) нет положительных элементов, то max L(x) находится в бесконечности (задача не решается);

в)              если нет ни одного значения L(x) lt; 0, то max L(x) достигнут (задача решена).

В табл. 4.5 в строке L(x) нет отрицательных чисел, поэтому достигнут max L(x) при x5 = 200, x4 = 200. Следовательно, если будут производить продукт В4 и В5 в объеме по 200 ед., то получат максимальную прибыль в размере 2000 руб.; xk = 100, значит, что 100 кг сырья (материалов) первого вида осталось неиспользованным.

Полученное решение проверяют. Для этого найденные значения неизвестных табл. 4.5 подставляют в симплексные уравнения и в значение L(x). х 0 + 4 х 0 + 6 х 0 + 10 х 200 + 3 х 200 + 100 = 2700, х 0 + 3 х 0 + 1 х 0 + 2 х 200 + 3 х 200 + 0 = 1000, х 0 + 1 х 0 + 5 х 0 + 4 х 200 + 1 х 200 + 0 = 1000,

L(x) =              5 х 0 + 3 х 0+ 4 х 0 + 6 х 200 + 4 х 200 + 3 х 0 + 0 + 0              = 2000.

Ценную дополнительную информацию представляют значения строки L(x), т.е. двойственные оценки в оптимальном решении. Значение строки L(x) для столбца x7, равное единице, показывает, сколько единиц прибыли приносит единица сырья (материала) II вида при производстве продукции. Значение строки L(x) для столбца х8, равное единице, показывает, сколько единиц прибыли приносит единица производственной мощности при производстве продукции.

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

для В4: 1 х 200 х 2 = 400; для В5: 1 х 200 х 3 = 600,

где первые сомножители представляют двойственные оценки;

вторые сомножители показывают количество производимой продукции по оптимальному варианту;

третьи сомножители показывают нормы расхода сырья II вида на производство продукции В4 и В5 соответственно.

В сумме прибыль составит: 400 + 600 = 1000.

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

для В4: 1 х 200 х 4 = 800;              для В5: 1 х 200 х 1 = 200.

Общая сумма прибыли, полученной при производстве продукции за счет использования производственной мощности, составит: 800+200=1000.

Общая сумма прибыли, получаемой за счет полного использования сырья II вида и производственной мощности, равна: 1000 + + 1000 = 2000.

Значение L(x) для столбца х6 равно нулю, это означает, что ресурсы сырья I вида не лимитируют производство продукции, и сырье данного вида осталось неиспользованным.

Оценки в строке L(x) для основных неизвестных, не вошедших в оптимальный план, представляют не менее интересную экономическую информацию. Цифра 2 в столбце х1 показывает, сколько единиц прибыли пришлось бы потерять, если была бы произведена одна единица продукции Bv Оценка 1 в столбце х2 показывает, что, если бы была произведена единица продукции В2, то прибыль в оптимальном решении уменьшилась бы на одну единицу. Аналогичные рассуждения относятся и к оценке в столбце х3. Все эти предположения нетрудно проверить. Если предположить, что будет произведено 20 ед. продукции В2 и 180 ед. продукции В5, то общий объем прибыли, вычисленный с помощью двойственных оценок, составит: 1980 (2000 — 20 х 1). Этот же объем прибыли получится, если в качестве исходных условий для данного расчета взять объем производства продукции и прибыль, получаемую от производства единицы продукции. Прибыль, получаемая от производства продукции В2, составляет 60 (3 х 20); от производства продукции В5 составит 720 (4 х 180); от В4 — 1200 (6 х 200). В сумме прибыль от произведенной продукции составит 1980 (60 + 720 + 1200).

Как видно из проведенных расчетов, производство единицы продукции В2 снизило получение прибыли на одну единицу. Оценку 2 для столбца х1 можно интерпретировать и так, чтобы производство продукции В1 не было невыгодным, цена на нее должна быть увеличена на 2 руб. прибыли. Нулевая оценка основных неизвестных х4 и х5 соответствует тому, что продукция В4 и В5 входит в оптимальный план.

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

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

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

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

Таблица 4.6

Показатель

Неизвестное

Тип исходного уравнения

lt;

=

gt;

При преобразовании исходного уравнения в симплексное вводится

дополнительное

Да

Нет

Да

искусственное

Нет

Да

Да

Коэффициенты в симплексном уравнении

при дополнительном

+ 1

-

-1

при искусственном

+1

+1

Коэффициенты в уравнении целевой функции

при дополнительном

при

искусст

венном

задача на max

задача на min

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

В решениях задач, вычисляемых симплексным методом, есть одна неслучайная особенность: каким бы ни было количество основных неизвестных, в оптимальном варианте решения число ненулевых значений неизвестных не превышает количества исходных ограничений. Эта особенность формально вытекает из построения симплексной таблицы. В основании таблицы ровно столько строк, сколько в задаче ограничений. Каждая строка представляет только одно неизвестное. Поэтому в план входят только те неизвестные, которые представлены в таблице, остальные неизвестные равны нулю. Следовательно, о количестве неизвестных, имеющих в решении ненулевое значение, можно знать еще до решения задачи, но при условии полной формулировки условий. Однако все это верно для случая, когда имеется только одно оптимальное решение. Если же задача имеет множество оптимальных решений, то часть этого множества вариантов может иметь больше положительных значений неизвестных. (Аналогичный случай существует для транспортной задачи, когда из части множества число вариантов оптимального плана будет больше m + n — 1.) 

<< | >>
Источник: Маркин Юрий Павлович. Экономический анализ : учеб. пособие для студентов вузов, обучающихся по направлению «Экономика» и другим эконом. специальностям. 2011

Еще по теме 4.1.2. Постановка и методика решения ассортиментной задачи симплексным методом:

  1.               Симплексный метод решения задачи
  2. 4.2.1. Постановка и методика решения задач динамического программирования
  3. Постановка и решение задачи оптимального распределения инвестиций
  4. Методики решения задач
  5. 4. МЕТОДЫ РЕШЕНИЯ ЗАДАЧ
  6. 2.2.1D. Метод теории решения изобретательски! задач (TPI3)
  7. 2.2. Стандартные методы решения задач стохастического программирования
  8. 4.3.10. Эвристические методы и приемы решения творческих задач
  9. Метод решения задачи определения экономически выгодных размеров партий предметов
  10. 2.2. Методы упрощения решения глобальной задачи прогнозирования и формирование системы прогнозных моделей
  11. ТЕМА 7. ТИПЫ ОПТИМИЗАЦИОННЫХ МОДЕЛЕЙ БАНКА И МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ
  12. 3.1. Постановка целей и задач
  13. Постановка задач
  14. Задачи проекта по постановке маркетинга
- Бюджетная система - Внешнеэкономическая деятельность - Государственное регулирование экономики - Инновационная экономика - Институциональная экономика - Институциональная экономическая теория - Информационные системы в экономике - Информационные технологии в экономике - История мировой экономики - История экономических учений - Кризисная экономика - Логистика - Макроэкономика (учебник) - Математические методы и моделирование в экономике - Международные экономические отношения - Микроэкономика - Мировая экономика - Налоги и налолгообложение - Основы коммерческой деятельности - Отраслевая экономика - Оценочная деятельность - Планирование и контроль на предприятии - Политэкономия - Региональная и национальная экономика - Российская экономика - Системы технологий - Страхование - Товароведение - Торговое дело - Философия экономики - Финансовое планирование и прогнозирование - Ценообразование - Экономика зарубежных стран - Экономика и управление народным хозяйством - Экономика машиностроения - Экономика общественного сектора - Экономика отраслевых рынков - Экономика полезных ископаемых - Экономика предприятий - Экономика природных ресурсов - Экономика природопользования - Экономика сельского хозяйства - Экономика таможенного дел - Экономика транспорта - Экономика труда - Экономика туризма - Экономическая история - Экономическая публицистика - Экономическая социология - Экономическая статистика - Экономическая теория - Экономический анализ - Эффективность производства -