Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Вычислительная процедура симплексного метода

Читайте также:
  1. Алгоритм метода ветвей и границ
  2. Алгоритмы метода Монте-Карло для решения интегральных уравнений второго рода.
  3. Биомикроскопия. Клинические возможности метода.
  4. Выбор вида и метода получения заготовки
  5. Гл. 6. Сертификация как процедура подтверждения соответствия.
  6. Глава 29. ОБЩИЕ ПОЛОЖЕНИЯ О ТАМОЖЕННЫХ ПРОЦЕДУРАХ

 

Чтобы получить представление о сущности симплексного метода, рассмотрим следующую задачу.

Задача 8.12. В авторемонтном предприятии, выпускающем неодно­родную продукцию, руководитель стремится определить, какими должны быть уровни производства для каждого узла и агрегата в течение некото­рого наперед заданного периода. Эти уровни ограничены технологиче­скими и другими «внутренними» для данного предприятия условиями, приведенными в табл. 8.18.

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

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

Z=4X1+5X2+9X3+llX4->max (8.76)

Таблица 8.18

Технологические условия производства продукции

Показатели Количество на единицу продукции для технологических процессов Имеется в наличии всего
№1 №2 №3 № 4
Трудовые ресурсы         ≤15
Материала типа А         ≤120
Материала типа В         ≤100
Доход с единицы продукции         max
Объем выпускаемой продукции X1 Х2 Хз X4 -

 

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

Обозначим через Х0 значение целевой функции и введем в рассмот­рение свободные переменные. В результате получим следующую систе­му уравнений:

где все переменные могут принимать лишь неотрицательные значение.

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

Задача шага 1 заключается в том, чтобы выбрать первоначальное допустимое решение системы уравнений (8.78). Существует множество таких решений, однако удобнее всего начать с Х0=0, Х5=15, Х6 = 120, Х7 = 100 при нулевых значениях остальных переменных. Другими словами, строится первое пробное решение с помощью только свободных переменных. Назовем его исходным базисным решением, а переменные X0, Х5, Xg, Х7 - базисными переменными или сокращенно базисом. Остальные переменные логично назвать внебазисными (небазисными) переменными.

Так как под X0 понимается в задаче прибыль, то предложенное пробное решение является не очень выгодным. Но его можно улучшить. Обратим внимание на коэффициенты при тех переменных, которые фигурируют в строке 0 и которые в предложенном выше пробном вари­анте не являются базисными (т. е. на коэффициенты при Х1, Х2, Х3, Х4). Каждый коэффициент в этой строке определяет величину положи­тельного приращения при увеличении значения соответствующей переменной на единицу. Таким образом, каждый коэффициент в строке О определяет положительное (если перед ним стоит знак минус) или отри­цательное (если перед ним стоит знак плюс) приращение Х0 при увели­чении на единицу соответствующей небазисной переменной.

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

Правило 1 (максимизация). Если в строке 0 имеются не­базисные переменные, коэффициенты при которых отрицательны, сле­дует выбрать переменную (обозначим ее через X j) с наибольшим абсо­лютным значением стоящего перед ней коэффициента, т. е. ту перемен­ную, которая обеспечивает наибольшее удельное приращение значения целевой функции. В случае, когда все небазисные переменные строки О имеют положительные или нулевые коэффициенты, оптимальное ре­шение можно считать полученным.

В соответствии с правилом 1 в базис следует ввести переменную Х4, так как каждое единичное приращение Х4 приводит к увеличению зна­чения X0 на 11. Увеличение значения Х4 возможно лишь за счет уменьшения значений базисных переменных в каждой строке, содержа­щей Х4 с положительным коэффициентом. Так, например, при увеличе­нии Х4 на единицу:

значение Х5 должно быть уменьшено на 1, чтобы удовлетворялось ограничение, приведенное в строке 1;

значение Х2 должно быть уменьшено на 2, чтобы удовлетворялось ограничение, приведенное в строке 2;

значение Х7 должно быть уменьшено на 15, чтобы удовлетворялось ограничение, приведенное в строке 3.

Сколь велико должно быть значение Х4, чтобы значение одной из выбранных вначале базисных переменных достигло своей нижней гра­ницы, т. е. нуля. Такой предел для Х4 равняется 100/15 = 6,67, при Х7 = 0. Следовательно, в базис нужно включить Х4, исключив из него Х7.

Обобщая вышеизложенное, сформулируем следующее правило для шага 3.

Правило 2:

а) рассмотрим отношения чисел, стоящих в правых частях ограниче­ний (7.55), к соответствующим коэффициентам при новой базисной пе­ременной X j (не обращая внимание на отношения, в которых знамена­тель равен нулю или представляет собой отрицательное число);

б) выберем отношение с наименьшим значением - в очередном пробном решении X j приравнивается именно этому значению. Пусть наименьшее из всех отношений правых частей (8.78) к соответствующим коэффициентам при Xj соответствует переменной Хк, входившей в предыдущее решение; тогда в очередном пробном решении следует по­ложить Хк = 0.

Результаты вычислений приведены в табл. 8.19.

Таблица 8.19

Итерация 1

Базисные перемен­ные Рассматри­ваемое пробное решение Коэффици­ент при Х4 Значения отношений Минималь­ное значе­ние Следующее пробное решение
Хо   -11 - - -
X5       - -
X6       - -
X7     100/15 6,67 Х4= 6,67; Х7= 0

 

Шаг 4. Перепишем соотношения (8.78) таким образом, чтобы в стро­ке 3 коэффициент при Х4 был равен единице, а в строках 0,1 и 2 - нулю. Процедуру, с помощью которой это достигается, называют операцией замены базиса. Сначала разделим обе части уравнения в строке 3 на ко­эффициент при Х4, т. е. на 15

Обратим в нули коэффициенты при X4 в строках 0, 1,2, действуя по следующей схеме:

1) умножить строку 3 на 11 и результат прибавить к строке 0;

2) умножить строку 3 на - 1 и результат прибавить к строке 1;

3) умножить строку 3 на - 2 и результат прибавить к строке 2.

В результате получим

Полученное уравнение (8.80) эквивалентно уравнению (8.78). Его удобство заключается в том, что, полагая X1 = X2 =...= Х6 = Х7 = 0, сразу можно определить значения переменных для нового пробного ба­зисного решения. X0=220/3; Х5=25/3; Х6=320/3; Х4=20/3. Прибыль для нового пробного решения равняется прибыли при предыдущем проб­ном базисе плюс значение новой базисной переменной, умноженной на удельный вклад новой базисной переменной, в приращении прибыли:

Смысл правила 2 становится теперь более ясным. Если бы вместо Х7 из первоначального базиса исключить Х5 (или Х6), то Х4, Х7, Х6 (или Х5) приняли бы отрицательное значение, что противоречит предположению о том, что ни одна из переменных не может быть отри­цательной.

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

Таблица 8.20

Итерация 2

Базисные перемен­ные Рассматри­ваемое пробное решение Коэффици­ент при X, Значения отношений Минималь­ное значе­ние Следующее пробное решение
Хо 220/3 -9/5 - - -
Х5 25/3 4/5 125/12 125/12 X1 = 125/12 Х6 = 0
Х6 320/3 33/5 1600/99 - -
Х4 20/3 1/5 100/3 - -

При этом в очередной базис можно включить либо Х1, либо Х2, ли­бо Х3. На основании правила 1 выбор падает на X1, так как эта пере­менная обеспечивает наибольшее удельное приращение для значения це­левой функции.

В соответствии с табл. 8.20 в очередном пробном решении Х5 сле­дует заменить на X1. С учетом произведенной замены необходимо пре­образовать систему уравнений (8.80). Вначале выполним нормировку ко­эффициента при Х1 в строке 1:

Затем исключим X1 из уравнений в строках 0, 2, 3, действуя по сле­дующей схеме:

1) умножить строку 1 на 9/5 и результаты сложить со строкой 0

2) умножить строку 1 на -33/5 и результаты сложить со строкой 2;

3) умножить строку 1 на -1/5 и результаты сложить со строкой 3.

В результате получим:

Третье пробное базисное решение дало следующие результаты:

Итерация 3. Завершив вторую симплекс-итерацию, видим (стро­ка 0), что решение может быть улучшено за счет Х3. Определим, какая переменная должна быть исключена из базиса. Пронормируем коэффициент X3 в строке 3 путем деления обеих частей соответствующего уравнения на 7/12 и исключим Х3 из уравне­ний в строках 0, 1 и 2 следующим образом:

1)умножить строку 3 на 11/12 и результат сложить со строкой 0;

2) умножить строку 3 на 5/12 результат сложить со строкой 1;

3)умножить строку 3 на 13/12 и результат сложить со строкой 2.

В результате получим:

В строке 0 все коэффициенты положительны, следовательно, согласно правилу 1, полученное решение является оптимальным (табл. 8.21).

 

 

Таблица 8.21

Итерация 3

Базисные перемен­ные Рассматри­ваемое пробное решение Коэффици­ент при Х3 Значения отношений Минималь­ное значе­ние Следующее пробное решение
Хо 1105/12 - 11/12 - - -
X1 125/12 5/12   - -
Х6 455/12 -13/12 - - Хз= 55/7,
Х4 55/12 7/12 55/7 55/7 Х4=0

Коэффициенты при переменных в окончательном варианте строки 0 иногда называют скрытыми издержками. Каждый коэффициент опреде­ляет отклонение значения целевой функции от оптимального при увели­чении значения соответствующей небазисной переменной на единицу. Таким образом, предприятие будет иметь прибыль 695/7 при выпуске продукции по технологическому процессу 1 и 3.

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

Шаг 1. Выбирается исходный базис.

Шаг 2. Используется правило 1. Если рассматриваемое пробное ре­шение не является оптимальным, осуществляется переход к шагу 3. В противном случае вычисления прекращаются.

Шаг 3. Выполняется процедура, предписанная правилом 2.

Шаг 4. Сменяется базис, после чего возвращаются к шагу 2.


Дата добавления: 2015-08-09; просмотров: 160 | Нарушение авторских прав


Читайте в этой же книге: Основные правила построения структуры управления | Системы контроля и регулирования движения подвижного состава | РУКОВОДИТЕЛЬ КОЛЛЕКТИВА | СТИМУЛЫ И НАКАЗАНИЯ | АВТОМОБИЛЬНЫМИ ПЕРЕВОЗКАМИ | ГРАФОАНАЛИТИЧЕСКИЙ МЕТОД | МЕТОД ПОТЕНЦИАЛОВ | МАРШРУТИЗАЦИЯ ПЕРЕВОЗОК | ОБСЛУЖИВАНИЯ В ОРГАНИЗАЦИИ ПЕРЕВОЗОК | РЕШЕНИЕ ЗАДАЧ В СЕТЕВОЙ ФОРМЕ |
<== предыдущая страница | следующая страница ==>
ОБЩИЕ ПОЛОЖЕНИЯ| Определение исходного базиса

mybiblioteka.su - 2015-2024 год. (0.011 сек.)