Метод линейного программирования в задачах оптимизации плана производства

4. Метод линейного программирования в задачах оптимизации плана производства

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

При небольшой размерности переменных до 10-ти в задачах линейного программирования (ЛП) используются итерационные процедуры ввиде конечного числа шагов, пи решении системы линейных уравнений, которые получили название симплексный метод.

Симплекс – многогранник.

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

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

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

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

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

Рассмотрим использование симплексного метода ЛП на примере задач оптимизации плана производства.

Пример №1:

Условие задачи (постановка):

Найти план производства предприятия обеспечивающий максимум прибыли.

Предприятие производит два вида продукции в трех цехах:

А 80

Б 60

В 100

Установлено соответственно: 80;60 и 100 единиц оборудования.

Нормы использования оборудования для производства за 1 час единицы продукции представлены в таблице в машино/часах:

Прибыль первого вида продукции 10 рублей

Прибыль единицы второй продукции 8 рублей

Требуется определить объем выпуска первого и второго вида продукции доставляющего максимум прибыли.

Решение:

1. Составляем модель.

Пусть х₁ искомый объем ₁ продукции первого вида;

х₂ - ₂ объем выпуска второго вида продукции.

Цель: максимальная прибыль.

Модель:

10х₁ – прибыль от реализации  первого вида продукции

8х₂ – прибыль от реализации  второго вида.

Целевая функция L(х₁х₂) = С₁х₁ + С₂х₂ = 10х₁ + 8х₂

С₁ = 10; С₂ = 8 – коэффициенты при переменных в целевой функции.

Планируемое использование машин по цехам не должно превышать наличие этого оборудования в цехах (по цехам)  отсюда система неравенств.

А – 4х₁ + 2х₂  80 ограничение по

Б – 1х₁ + 3х₂  60 использованию

В – 2х₁ + 3х₂  100 оборудования,

условие не отрицательности.

х₁  0; х₂  0.

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

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

4х₁ + 2х₂ + х₃  80

х₁ + 3х₂ + х₄  60

2х₁ + 3х₂ + х₅  100

Переведем систему неравенств в уравнение:

х₃ = 80 – (4х₁ + 2х₂) сколько машин

х₄ = 60 – (х₁ + 3х₂) нужно

х₅ = 100 – (2х₁ + 3х₂) (машино/часов)

Дополнительные переменные должны быть введены в целевую функцию, которая будет иметь вид:

L(х₁х₂) = С₁х₁ + С₂х₂ + С₃х₃ + С₄х₄ + С₅х₅ = 10х₁ + 8х₂ + 0х₃ + 0х₄ + 0х₅

стремится к максимуму

х₁  0; х₂  0; х₃ = 0; х₄ = 0; х₅ = 0.

Выразим х₃;х₄ их₅ через х₁ и х₂

х₃ = 80 – 4х₁ - 2х₂

х₄ = 60 – х₁ - 3х₂

х₅ = 100 – 2х₁ - 3х₂

Модель составлена и в этой модели имеются: х₁; х₂ – независимые (свободные) переменные; х₃; х₄; х₅ – базисные переменные.

По составленной модели используют итерационные процедуры метода, составим альтернативные варианты решения системы уравнений с пятью неизвестными.

Первым решением будет х₁ = 0; х₂ = 0; х₃ = 80; х₄ = 60; х₅ = 100.

Целевая функция будет равняться: L=10*0 + 8*0 + 0*80 + 0*60 + 0*100=0

Используя систему уравнений, составим отправную таблицу:

Ключевой столбец Генеральный элемент Ключевая строка

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

С_б – коэффициенты при базисных переменных целевой функции.

Х_б - базисные переменные.

В - столбец свободных членов.

Zj - определяется как сумма попарных произведений коэффициентов С_б на элементы столбца В.

Z₀ = 0*80+0*60+0*100 = 0

Сj - коэффициент целевой функции при переменной.

Zj - Сj - индексная строка.

Z₁ – С₁  Z₁ = 0*4+0*1+0*2-10 = -10

Z₂ = 0*2+0*3+0*3-8 = -8

Получение второго базисного решения, и решения вообще, надо преобразовать, первую таблицу во вторую получив улучшенное (решение) значения.

Z - значение целевой функции для данного решения.

Правила определения оптимального решения:

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

Если нет ни одного значения больше 0 (минимальное);

Наибольшее по абсолютной величине отрицательное число в индексной строке указывает на новую базисную переменную (в нашем случае это (– 10) х₁).

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

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

80/4=20; 60/1=60; 100/2=50.

Составляем вторую базисную таблицу:

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

Правила заполнения таблиц после отправной:

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

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

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

Все остальные элементы новой таблицы определяются расчетом по формуле:

Новый элемент = старый элемент – Элемент ключевой стоки * элемент ключевого столбца / генеральный элемент.

Для столбца свободных членов (В):

60-80*1/4=60-20=40

100-80*2/4=100-40=60

Для столбца х₂ по тому же правилу:

3-2*1/4=3-1/2=5/2

3-2*2/4=3-1=2

Для столбца х₃:

0-1*1/4=0-1/4=-1/4

0-1*2/4=0-1/2=-1/2

Определяем индексную строку:

0-80*(-10)/4=0+200=200=Z

-8-2*(-10)/4=-8-(-5)=-3

0-1*(-10)/4=0-(-5/2)=5/2

Определяем ключевой столбец таблицы №2 и ключевую строку используем ранее изложенные правила.

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

Х₄ заменит Х₂

Составляем третью таблицу:

40/5/2=40*8/5=16; -1/4/5/2= -1/10

Для столбца свободных членов (В):

20-40*1/2 / 5/2=20-8=12; 60-40*2 / 5/2=60-32=28

Для столбца х₃:

4-(-1/4)*1/2 / 5/2=4+1/20=81/20; -1/2-(-1/4)*2 / 5/2=-1/2+1/5=-3/10

Для столбца х₄ по тому же правилу:

0-1*1/2 / 5/2=0-1/5=-1/5; 0-1*2 / 5/2=0-4/5=-4/5

Определяем индексную строку:

200-40*(-3) / 5/2=200+40*3*2/5=200+48=248=Z

5/2-(-1/4)*(-3) / 5/2=5/2-3/10=22/10=11/5

0-1*(-3) / 5/2=0+6/5=6/5

Из таблицы №3 видно, что в индексной строке отсутствуют отрицательные значения и, следовательно, невозможно дальнейшее назначение итерационных процедур. Полученное значение прибыли Z₀ = 248 рублей прибыли в час, является оптимальным.

Пример №2:

Условие задачи (постановка):

Найти план производства предприятия обеспечивающий максимум прибыли.

Предприятие производит два вида продукции в трех цехах:

А 28

Б 20

В 10

Установлено соответственно: 28;20 и 10 единиц оборудования.

Нормы использования оборудования для производства за 1 час единицы продукции представлены в таблице в машино/часах:

Прибыль первого вида продукции 4 рубля

Прибыль единицы второй продукции 2 рубля

Требуется определить объем выпуска первого и второго вида продукции доставляющего максимум прибыли.

Решение:

Похожие работы

Методы принятия управленческих решений

Скачать

49243

2

0

... методов, являются лишь базой для принятия окончательного решения; при этом могут приниматься во внимание дополнительные критерии, в том числе и неформального характера . 3. Принятие управленческих решений в АО «Вятский торговый дом».    3.1. Организационно-распорядительные методы. Рассмотрим сначала организационно-распорядительные методы (ОРМ). ОРМ делятся на 2 вида: организационно- ...

Проблемы и методы принятия решений

Скачать

53234

0

1

... и использования специалистов-пpофессионалов по анализу ваpиантов пpинимаемых pешений; pазpаботки и пpактического использования специальных методов анализа и сpавнения сложных альтеpнатив, возникающих в пpоцессе выбоpа. 3.ОБЩИЕ ПОДОХДЫ И РАЦИОHАЛЬHЫЕ ПРОЦЕДУРЫ В ПРОБЛЕМАХ ВЫБОРА В последние 20-30 лет появились подходы, pассматpиваемые многими как унивеpсальное сpедство pешения всех ...

Рациональное решение и этапы его принятия

Скачать

24766

5

2

... работы; об оценке этих результатов; о том, насколько достигнуты цели организации; о корректировке целей. Рациональное решение - это решение, которое основывается на базе аналитического процесса, и часто не зависящее от предшествующего опыта. 1. Методология и методы принятия решения Эффективность управления зависит от комплексного применения многих факторов и не в последнюю очередь от ...

Процесс принятия управленческих решений в менеджменте

Скачать

91004

1

5

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