Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.07.2024
Просмотров: 245
Скачиваний: 0
Симплекс-метод для отыскания оптимального решения да ет специальное правило перехода от полученной вершины мно гогранника Q к той соседней вершине этого многогранника, в которой z принимает большее значение. Этот процесс продол жается до тех пор, пока не будет найдена вершина, в которой значение z максимально, т. е. для которой все коэффициенты z-той строки будут неотрицательны.
Геометрически это означает, что прямая z= const вышла полностью из многогранника Q и соприкасается с ним только в одной точке (в одной вершине). Чтобы осуществить переход от вершины г/, = . . . = £/„== О к упомянутой соседней вершине, делаем один шаг модифицированного Жорданова исключения со следующим правилом выбора разрешающего элемента.
1. В качестве разрешающего берем столбец, содержащий отрицательный элемент z-той строки.
2. Отбираем все положительные коэффициенты этого столб ца (если такие имеются), делим на них соответствующие сво бодные члены; сравниваем полученные отношения и в качест ве разрешающего берем тот из коэффициентов, для которого отношение имеет наименьшее значение (если их окажется больше одного, то берем любой из них).
После шага модифицированного Жорданова исключения с разрешающим элементом, выбранным по только что сформу лированному правилу, знак элемента разрешающего столбца строки изменится на противоположный. Если все остальные новые коэффициенты z-строки неотрицательны, то задача ре шена— получено оптимальное решение. Если же среди остальных коэффициентов новой z-строки есть отрицательные, то расчет продолжается, и после конечного числа шагов при дем либо к случаю, когда в z-строке не окажется отрицатель ных коэффициентов (задача решена), либо к случаю отсут ствия положительных коэффициентов в некотором столбце, содержащем отрицательный коэффициент z-строки, что озна чает неограниченность сверху функции Z (рис. 10).
Поясним применение симплекс-метода для отыскания оп тимального решения на примерах.
Пример 1. Примем систему ограничений туж е, что и для отыскания опорного решения. Итак, даны система ограни чении:
Х\—Хо+ х3^ 4
2х 1+ л'2—Л'з Д55
2х 1—2х2—-Зл'зГ-;0
х2> 0 ; х3> 0
и целевая функция
Z = 2х\—3x2 -{- Х3.
4—9SI |
49 |
Найти такие значения Х\, х 2 и х3, которые обращали бы це левую функцию в максимум. Записывая условные задачи с помощью дополнительных переменных
У\ = 1(—* 1) — 1(■—х2) +1 (—*з) + 4 ^ 0
У2 ——2(—Х\) —1(—х2) + 1 (—х'з)—5 ^ 0
Уз = — 2(-- Х\) + 2 (—Х2)+ 3 ( —Х3) —1 ^ 0
Z ——2(—X]) + 3(—х2) —1(—х3)-мпах,
переходим к таблице: |
|
|
|
—Xj |
—Ха |
—Х3 |
1 |
1 |
- 1 |
1 |
4 |
— 2 |
- 1 |
1 |
- 5 |
- 2 |
2 |
3 |
— 1 |
— 2 |
3 |
— 1 |
0 |
После первого шага Жорданова исключения с третьей раз решающей строкой и первым столбцом получим таблицу:
— У з |
— х я |
—х3 |
1 |
|
1 |
2 |
5 |
7 |
|
2 |
2 |
|
||
|
~2 |
|||
— 1 |
- 3 |
—2 |
—4 |
|
1 |
— 1 |
3 |
1 |
|
~ 2 |
~ 2 |
2 |
||
|
||||
— 1 |
1 |
—4 |
1 |
50
После втрого шага со второй разрешающей строкой и пер вым столбцом получим таблицу:
—Уз —х 2 —x t
1 |
3 |
3 |
3 |
2 |
_ 2 |
2 |
2 |
- 1 |
3 |
2 |
4 |
1 |
1 |
1 |
5 |
2 |
2 |
~2~ |
2 |
- 1 |
4 |
- 2 |
5 |
Анализ последней таблицы показывает, что опорное реше ние задачи найдено (коэффициенты заключительного столбца положительны). Однако среди коэффициентов Z-той строки есть отрицательные, значит решение еще не оптимальное.
Сделаем еще один шаг модифицированного Жорданова исключения с разрешающими третьим столбцом и первой строкой и получим следующую таблицу:
|
—Уз |
—х 2 |
- у , |
|||
■*з= |
|
1 |
— 1 |
|
2 |
|
|
3 |
~ |
3 |
|||
|
|
|||||
Уз= “ |
5 |
5 |
|
4 |
||
3 |
~ |
3 |
||||
|
||||||
A'l — |
|
1 |
0 |
|
1 |
|
~ |
3 |
|
3 |
|||
|
|
|||||
|
|
|
||||
Z = |
|
1 |
2 |
|
4 |
|
~ |
3 |
|
3 |
|||
|
|
|||||
|
|
|
||||
Опять решение еще не оптимальное.
4*
1
2
3
7
51
Сделаем еще один шаг с разрешающим первым столбцом и первой строкой и получим следующую таблицу:
—-«3 |
—*3 |
—У\ |
1 |
||
- 3 |
- 3 |
- 2 |
3 |
||
5 |
0 |
|
14 |
7 |
|
_ |
3 |
||||
|
|
|
|||
1 |
— 1 |
|
1 |
4 |
|
- |
з" |
||||
|
|
|
|||
1 |
1 |
2/3 |
8 |
||
Получено оптимальное решение, при котором
Хз= Хо = У\=0\
*/2= 3, г/з= 7, *1=4 и Z=8(max).
П р и м е р 2. Этот пример был решен в введении графи ческим методом.
Условие задачи: необходимо наладить выпуск деревянных лопат и ящиков для хранения инструмента; нормы расхода и
ресурсы материалов, а также |
прибыль на единицу изделий |
||||||
приведены в табл. |
6. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Таблица 6 |
|
|
|
Нормы затрат |
|
|
||
Виды изделии |
|
на единицу продукции |
Прибыль на единицу |
||||
|
древесины, |
фанеры, |
м2 |
продукции, руб |
|||
|
|
|
|||||
|
|
|
М* |
|
|
||
Лопаты |
деревянные . . |
0,01 |
|
0,3 |
|
0,2 |
|
Ящики для хранения ин- |
0,1 |
|
0,1 |
|
1.5 |
||
струмента.................... |
|
|
|||||
Ресурсы |
материалов |
в |
20 |
|
330 |
|
|
месяц ............................ |
|
|
|
||||
Задача заключается в том, чтобы запланировать такой вы пуск продукции по ее видам, при котором общий расход мате риалов не превышает ресурсов и обеспечивается наибольшая рентабельность производства.
52