Решение первой задачи ПП симплекс-методом.
В z-строке оптимальной симплекс-таблицы расположены оценки ?j=d'j+d''j t0, которые в случае задачи максимизации должны быть неотрицательными:
(15)
Решая полученную систему, находим выражения для определения нижнего t1 и верхнего t2 значений параметра t:
t1=
(16)
t2=
(17)
Для всех t1?t?t2 задача (1)-(3) имеет один и тот же план, что и при t=t0.
Если задача (1)-(3) при t=t0 неразрешима, то в z-строке последней симплекс-таблицы есть оценка ?k=d'k+d''k t0 в столбце хk, все коэффициенты которого неположительные. Тогда:
- если d''k=0, то задача (1)-(3) неразрешима при любом t;
- если d''klt;0, то задача (1)-(3) неразрешима при любом tlt;t1=-d'k/d''k;
- если d''kgt;0, то задача (1)-(3) неразрешима при любом tgt;t1.
Определив все значения t, для которых задача (1) – (3) имеет один и тот же оптимальный план или для которых задача неразрешима, получаем промежуток изменения параметра t, который исключаем из рассмотрения. Снова берем значение параметра t равным некоторому числу из промежутка ??,?? и находим решение полученной задачи, и т.д.
Получаем следующий алгоритм решения
- Считая значение параметра t равным некоторому числу t0???,??, находим оптимальный план Х* или устанавливаем неразрешимость полученной задачи ЛП.
- Определяем множество значений t???,??, для которых найденный оптимальный план является оптимальным или задача неразрешима. Эти значения параметра исключаем из рассмотрения.
- Полагаем значение параметра t равным некоторому числу, принадлежащему оставшейся части промежутка ??,?? и находим решение полученной задачи ЛП.
- Определяем множество значений параметра t, для которых найденный оптимальный план остается оптимальным или задача неразрешима. Вычисления повторяем до тех пор, пока не будут исследованы все значения параметра t???,??.
Пример 2. Для всех значений t?(-?,+?) найти оптимальные планы следующей задачи:
z=2х1+(3+4t)х2?max, (18)
х1+х2+х3=12,
х1-х2+х4=?10, (19)
-х1+х2+х5=?6,
xj?0, j=1, 2,…,5.
¦ Возьмем, например, t=0 и ищем симплекс-методом оптимальный план полученной задачи (в каждой таблице подчеркнут разрешающий элемент, итер. 0-2):
| Итерация 0 | Итерация 1 | ||||||||||||||||||||||||||||||||
|
|
| Итерация 2 | Получен оптимальный план | |||||||||||||||
|
t1=max{(-2,5/2), (-0,5/2)}=-0,25, t2=+?.
Т.о., если t??-0,25,+?), то задача (18) – (19) имеет оптимальный план 
(3;9;0;16;0), для которого zmax=33+36t руб.
Пусть теперь t?-0,25, например, -1. Тогда оценка в столбце х5 итерации 2 станет отрицательной, столбец х5 выбираем в качестве разрешающего и переходим к новой таблице (итер. 3):
| Итерация 3 | Новый план t1=max{(-2,5/2)}=-1,25, t2=min{(-0,5/2)}=-0,25. Т.о., если t??-1,25,-0,25?, | |||||||||||||||
|
то задача (18) – (19) имеет оптимальный план 
(11;1;0;0;16), для которого zmax=25+4t руб.
Пусть теперь t?-1,25, например, -2. Тогда оценка в столбце х2 итерации 3 станет отрицательной, столбец х2 выбираем в качестве разрешающего и переходим к новой таблице (итер. 4):
| Итерация 4 | Новый план Т.о., если t?(-?,-1,25?, то задача имеет оптимальный план | |||||||||||||
|
Получено следующее решение задачи:
при t?(-?,-1,25? оптимальный план 
(10;0;2;0;16), zmax=20 руб.;
при t??-1,25,-0,25? оптимальный план (11;1;0;0;16), zmax=25+4t руб.;
при t??-0,25,+?), оптимальный план (3;9;0;16;0), zmax=33+36t руб. ?
Еще по теме Решение первой задачи ПП симплекс-методом.:
- Анализ методов решения задач распределительной логистики Для решения задач распределительной применяется большое количество
- 1.7. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД
- 2.5. Симплексный метод решения задачи
- 1.4. СИМПЛЕКС-МЕТОД
- Симплекс-метод с искусственным базисом (М-метод).
- 1.5. МОДИФИЦИРОВАННЫЙ СИМПЛЕКС-МЕТОД
- 1.3. Анализ методов решения задач распределительной логистики
- 15.2. Первая задача ПП. Графический метод решения.
- 16.4. Решение задачи о кратчайшем пути методами динамического программирования.
- • Принцип оптимальности в планировании и управлении, общая задача оптимального программирования • Формы записи задачи линейного программирования и ее экономическая интерпретация • Математический аппарат • Геометрическая интерпретация задачи • Симплексный метод решения задачи 2.1. Принцип оптимальности в планировании и управлении, общая задача оптимального программирования
- 1.3. Методы синтеза и выбора (в среде заданного конечного набора алгоритмов) оптимальных законов параметрического регулирования развития экономической системы страны, условия существования решения соответствующих задач вариационного исчисления и условия влияния на них неуправляемых параметров 1.3.1. Исследование условий существования решения задачи вариационного исчисления по синтезу и выбору оптимальных законов параметрического регулирования непрерывной детерминированной динамической сис
- Типовые задачи и задачи для самостоятельного решения.
- Типовые задачи и задачи для самостоятельного решения.
- Вопрос 90. Сущность процесса принятия управленческих решений. Модели и методы принятия решений