Меню
Главная
Авторизация/Регистрация
 
Главная arrow Менеджмент arrow Менеджмент предприятия

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

А. Общие положения симплекс-метода

Общую методику симплекс-метода рассмотрим на примере, в состав которого входят четыре производственных цеха, где изготавливаются два изделия 1 и 2. Производственные мощности цехов (в часах) в расчете на сутки составляют соответственно: m1 = 12 m2 = 8, m3 = 16 m4 = 12.

Нормы времени, необходимого для изготовления единицы продукции:

Цех

Нормы времени (ч / ед.) Для изделий

1

2

1

2

2

2

1

2

3

4

0

4

0

4

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

Прибыль от реализации единицы изделия 1 составляет 2 тыс. Грн., А единицы изделия 2-3 тыс. Грн. (цифры условные). Следует выбрать тот из возможных вариантов производственного плана, при котором обеспечивается максимальная прибыль.

Обозначим через Х1 количество изделия 1, а через Х2 - количество изделия 2. Пользуясь нормами времени и данными о производственных мощностях цехов, можем утверждать, что должны выполняться условия:

так как возможны только такие варианты производства, за которыми не превышаются производственные мощности цехов.

Суммарная прибыль предприятия составляет

Необходимо определить такие объемы изготовления изделий 1 и 2, при которых достигается максимальная прибыль.

Введем вспомогательные переменные Х3, Х4, Х5, Х6, чтобы уравнение

Вспомогательные переменные означают неиспользованные производственные мощности первого, второго, третьего и четвертого цехов.

Симплекс-метод заключается в последовательном улучшении вариантов плана, до нахождения оптимального варианта.

Первым и, очевидно, наименее выгодным, можно принять вариант плана, в котором Х1 = Х2 = 0. Тогда прибыль от реализации продукции Z = 0, а производственные мощности цехов совсем не используются. От первого варианта можно перейти ко второму - лучшего, учитывая в планах один из изделий; выгоднее ввести в план изделие 2, так как он обеспечивает большую прибыль на единицу продукции.

Учитывая нормы времени, необходимые для изготовления изделия 2 в соответствующих цехах, можно установить объем производства этого изделия. В первом цехе он составляет 6 единиц (12: 2), во втором - 4 единицы (8: 2), а в четвертом - 3 единицы. Допустимый объем изготовления изделия 2 определяет четвертый цех.

Если бы изделие 1 не изготовлявшегося, то при полном использовании производственных мощностей четвертого цеха (Х6 = 0) можно было бы установить план производства в объеме Х2 - 3 ед. Тогда прибыль составила

Из уравнения (5.296) видно, что размер прибыли Z можно увеличить за счет введения в план изготовления изделия 1 в объеме Х1.

Числовые коэффициенты при неизвестном Х1 в уравнениях (5.25a) - (5.27) являются нормами времени для изделия 1, а свободные члены показывают производственные мощности первого, второго и третьего цехов, они еще имеют. Таким образом, количество изделий 1, которая может быть изготовлена в этих цехах, составляет 3 единицы (6: 2) в первом цехе, 2 единицы (2: 1) во втором и 4 единицы (16: 4) в третьем. Допустимый объем производства изделия 1 определяет второй цех: Х1 - 2.

Так мы получили второй, усовершенствованный вариант плана: Х1 = 2, Х2 = 3 Соответствующий ему прибыль составляет:

Из уравнения (5.29в) видно, что величина, с помощью которой можно увеличить размер прибыли, является переменная А ^, то есть неиспользованные мощности четвертого цеха. Вычисляя частного от деления свободных членов на дополнительные коэффициенты шестого столбца уравнений (5.25в), (5.27в), (5.28в), находим: 2: (1/2) = 4, 8: 2 = 4, 3: (1 / 4) = 12 Допустимое значение переменной Х $ можно найти из уравнения (5.25в) или (5.27в). Из уравнения (5.25) находим:

Из уравнения (5.29г) видно, что в нем нет ни одной переменной, с помощью которой можно было бы увеличить прибыль 2, так как коэффициенты у переменных в этом уравнении отрицательные. Прибыль достигает максимума как раз потому, что Х3 = Х4 = 0 (любое другое значение этих переменных уменьшило бы прибыль).

Подставляя Х3 = X4 = 0 последовательно в уравнение (5.25г) - (5.29г), находим: X6 = 4, Х1 = 4, Х5 = 0, Х2 = 2, Z max = 14 тыс. Грн.

Таким образом, мы получили лучший вариант производственного плана. Такой вариант предусматривает изготовление изделия 1 в количестве X1 = 4, изделия 2 - в количестве Х2 - 2. В случае использования такого варианта прибыль достигает максимума (14 тыс. Грн.), Причем для этого варианта производственные мощности первого, второго и третьего цехов используются полностью {Х3 = Х4 = Х5 = 0), тогда как недоиспользование производственных мощностей четвертого цеха составляет 4 единицы.

На практике описанный метод можно упростить, использовав матричная запись. Коэффициенты при неизвестных в системе уравнений (5.25) - (5.29) можно записать в виде матрицы АА. Поскольку мы ищем максимум Z, то столбец, в котором целевая функция имеет наибольший коэффициент, принимаем "избранным" и для того, чтобы выделить его, обводим его рамкой. Деля столбец свободных членов на положительные коэффициенты "избранного" столбца, находим числа, выписанные справа от матрицы АА. Выделим строку, в которой доля от этого деления имеет наименьшее значение (это допустимый объем производства). Имеем матрицу использования производственных мощностей.

С помощью выделенной строки преобразуем матрицу АА так, чтобы на пересечении выделенных строки и столбца получить единицу, а в других строках выделенного столбца - нули. Для этого достаточно четвертый выделенную строку матрицы АА поделить на 4, а затем полученную долю умножить на (-2) и добавить последовательно с первым и вторым рядами, умножить на (-3) и добавить с пятым строкой, а третью строчку оставить без изменений. После этих преобразований получим матрицу АБ.

в которой выбран столбец - первый, а выбранный строка - второй. Обведем их рамками. Справа от матрицы - вычисленные частного от деления свободных членов на положительные элементы выбранного столбца. Умножив избран строку на (-2), добавив его последовательно с первым и пятым строками, умножив его на (-4) и добавив с третьей строкой, превратим матрицу АБ таким образом, чтобы в выбранном столбце везде были нули, кроме второй строки , где должна быть 1,0. После этих преобразований получаем матрицу

С последней строки матрицы Ав видно, что следующим "избранным" столбцом должен быть шестой, а избранным строкой - первый или третий.

После соответствующих преобразований получаем матрицу Аг.

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

Те переменные, для которых в последней строке получили отрицательные коэффициенты, следует приравнять к нулю (Хз = Х4 = 0), а остальные переменные вычислить по отдельным строк, каждая из которых является уравнением с соответствующими коэффициентами при неизвестных, а в правой части оно дано последнее

Из сказанного становится понятной такая очередность этапов нахождения целевой функции симплекс-методом:

1. Неровности меняются уравнениями путем введения соответствующих вспомогательных переменных.

2. Задача записывается в виде симплексной матрицы.

3. Определяется переменная, имеет наибольший коэффициент в целевой функции, а столбец, содержит эту переменную, принимается как "избранный".

4. Определяется строку, в которой результат деления свободного члена на положительный коэффициент "избранного" столбца имеет наименьшее значение; эта строка принимается как "избранный".

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

6. Эту операцию повторяем до тех пор, пока в целевой функции не получим только неположительны коэффициенты.

7. Переменные, коэффициенты которых негативные, принимаются как нулевые (поскольку они не увеличивают целевую функцию).

8. Другие переменные рассчитываются из уравнений, соответствующих последний матрицы.

При использовании ЭВМ этапы 3-8 выполняет вычислительная машина. При этом достаточно ввести в ЭВМ расчетную матрицу, а затем распечатать и проанализировать полученные результаты.

Ниже рассмотрены примеры решения моделей линейного программирования с помощью ЭВМ.

Б. Выбор портфеля инвестиций

Клиент поручил биржевому брокеру инвестировать значительную сумму денег в портфель обыкновенных акций. Цель - максимизация роста капитала. При этом для выбранного портфеля инвестиций риск не должен превышать заданной величины. Кроме того, должен быть обеспечен достаточный доход, чтобы оплатить налоги и осуществить другие платежи. Биржевой брокер владеет информацией о большом количестве компаний различных отраслей промышленности. Каждая компания ранжированы по балльной шкале от 0 до 9 по возрастанию капитала и потенциальным риском. При этом 0 означает отсутствие роста или риска, а 9 - максимальные роста или риск. Кроме того, более 35% портфеля инвестиций могут быть вложены в любую отдельную отрасль промышленности. Общий коэффициент риска не должен превышать 10. Информация о компании приведена в таблице 5.10.

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

Таблица 5.10. Характеристика предприятий

Характеристика предприятий

Решение матрицы показывает, что оптимальное значение целевой функции равно 8,7. Оптимальное значение переменных 4, 8 и 16 равна соответственно 0,35; 0,3; 0,35. Другие переменные равны нулю. Таким образом, для инвестиций выбираем предприятие 4 отрасли А, предприятие 8 отрасли Б и предприятие 16 области Г.

В. Решение задачи

Предположим, что предприятие производит трех изделия А, Б и В. При этом используются две производственные процессы - 1 и 2. На каждое изделие расходуется такое количество рабочего времени (в часах):

Изделие

Производственный процесс

1

2

А

9

11

Б

5

18

В

20

6

Решение матрицы показывает, что максимум прибыли тысяче четыреста семьдесят один грн. за неделю достигается при производстве 33, 28 товаров А и 21, 94 товаров Б. При этом производство товаров В должно равняться нулю.

 
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Инвестирование
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Политэкономия
Право
Психология
Региональная экономика
Религиоведение
Риторика
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее