Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf

Запишем условие задачи в виде системы ограничений

0,0\Х\ + 0,1*25-220

0,3*! + l,l;t2s^330

*1^0, *2>0.

7 = 0,2*!+ 1,5*2-Hnax.

Здесь *i — план выпуска лопат; *2 — план выпуска ящиков.

Перепишем эту систему с добавлением дополнительных

Решение задачи заключается в последовательном введении в

план основных переменных, пока не будет получено оптималь­ ное решение. При этом на каждом этапе расчета вводится лишь одна переменная. Одновременно другая переменная вы­ водится из базиса. Встает вопрос: какую именно из основных переменных вводить в базис, т. е. выпуск какого изделия за­ планировать в первую очередь? Поскольку задача решается по максимум прибыли, целесообразнее начать с наиболее при­ быльного изделия. В данном примере наиболее прибыльным изделием являются ящики *2. Разрешающим столбцом будет столбец с коэффициентом заключительной строки —1,5, а раз­ решающей строкой будет первая. Разрешающий элемент 0,1

53

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

Анализ таблицы показывает, что 'решение еще не опти­ мальное — имеется отрицательный элемент в заключительной строке —0,05. Сделаем еще один шаг Жорданова исключения с разрешающими первым столбцом и второй строкой и полу­ чим таблицу

0.190.19

j/2 = i/i = 0; л'2= 142; *3 = 580; Z = 329.

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

Решим предыдущий пример, используя специальные симп­ лексные таблицы, и покажем порядок их заполнения.

Итак, дано условие задачи:

0,01*1 ”Ь 0,1*2=^20

0,3*i Т-1,1 *2 330 * i^ 0 ; *2> 0

Z = 0,2*2+1,5*2—>-гп ах.

54

Для перехода к симплексным таблицам необходимо от не­ равенств перейти к равенствам путем введения дополнитель­ ных переменных. Перепишем систему, введя дополнительные переменные:

0,01Х\ -f-0,1Х2+ У\ —20

0,3*1 +1,1 *2+ У2= 330

*1^:0; *23й0.

Z =0,2*2+1,5*2-*-тах.

По своему экономическому содержанию дополнительные переменные обозначают недоиспользованные ресурсы. Пере­ ходим к симплексной таблице (табл. 7).

55

На нулевом шаге в таблице записывается условие задачи. Так, в строке,, где находится дополнительное неизвестное у\,

Дополнительным переменным соответствуют нулевые коэффи­ циенты (недоиспользованные ресурсы прибыли не приносят).

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

Величина z для /-го столбца получается как сумма произ­ ведений величин столбца С на соответствующие коэффициен­ ты столбца /. Поскольку, однако, в нашем первоначальном плане в столбце С находятся только нули, величины Zj для столбца «План» и столбцов всех переменных будут равны нулю и соответственно Zy—C; = —Су. Поэтому в строке Z,■—Су

первоначального варианта фактически проставлены коэффи­ циенты целевой функции с обратным знаком. В самом деле, например, для столбца под неизвестной х\ Zy— у= (0-0,01 +

тельные переменные получают свои предельные значения в соответствии с исходными1уравнениями. Это отвечает такому «плану», при котором ничего не производится, ресурсы не ис­ пользуются и значение целевой функции равно нулю (т. е. прибыль отсутствует).

Этот план не является, конечно, оптимальным. Для полу­ чения прибыли необходимо, чтобы в плане были представлены основные переменные, обозначающие выпуск изделий.

Решение задачи заключается в последовательном введении в план основных переменных до тех пор, пока не будет полу­ чено оптимальное решение. На первом шаге в план вводим наиболее прибыльное изделие — ящики х2.

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

Произведем один шаг модифицированного Жорданова ис­ ключения, в результате которогополучим новый план (см. шаг 1). Этот план также оказался не оптимален, поскольку в

56

заключительной строке имеется один отрицательный элемент в столбце под л+

Просматривая положительные отношения данных столбца плана к соответствующим коэффициентам столбца под л+ устанавливаем, что разрешающим элементом в данном слу­ чае будет элемент 0,19, который и заключаем в прямоуголь­ ник. После второго шага Жорданова исключения получим окончательный оптимальный план. В этом плане в заключи­ тельной строке нет ни одного отрицательного элемента (см. шаг 2 табл. 7). Можно проверить правильность наших вы­ числений. Проверка производится по результатам заключи­ тельной строки.

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

Посмотрим так ли это.

(1,5X142)+ (0,2X580) =329.

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

3. Задачи минимизации линейной формы

До сих пор мы рассматривали решение симплекс-методом задачи отыскания максимума линейной формы

Во многих задачах требуется найти минимум формы (34) при ограничениях (35).

Для этого достаточно положить

2 = — Z — — с, + — . .. сп хп

ирешить задачу максимизации полученной формы при огра­ ничениях (35).

Задачу минимизации линейной формы (34) можно решить

ине сводя ее к указанной задаче максимизации.

Вэтом случае признаком оптимальности опорного реше­ ния (т. е. достижения на нем minZ) будет отсутствие поло­ жительных коэффициентов в z-той строке. Разрешающий эле­ мент при этом берется не над отрицательным коэффициентом строки, а над положительным.

57

СИМПЛЕКС-МЕТОД В ЗАДАЧАХ ПО ОПТИМИЗАЦИИ ПЛАНОВ РЕМОНТА

ИСОДЕРЖАНИЯ ЖЕЛЕЗНОДОРОЖНОГО ПУТИ

Вданной лекции рассматриваются примеры решения прак­

тических задач с использованием симплекс-метода.

З а д а ч а 1

На дистанции планируется капитальный ремонт пути в

•объеме N километров. Дистанция располагает ограниченными ресурсами. Имеется возможность ремонтировать путь по трем различным технологиям.

Потребность ресурсов для производства ремонта 1 км пути различными технологиями представлена в табл. 8.

сов

Требуется установить, какими технологиями следует вы­ полнять капитальный ремонт, с тем чтобы при заданных огра­ ничениях на ресурсы отремонтировать максимальное коли­ чество километров пути.

58

Р е ше н и е . На основании исходных данных составляем ■систему ограничений. Для этого количество отремонтирован­ ных километров по 1-й технологии обозначим через x it по

'2-й —х2, по 3-й — х3.

Тогда -*1 + 1,5х2 + I,2x3s^1,5

1,\х\ + 0,75х2+Лз^ 1,0

350^1 + 550х2 + 450хз:^450

l,5xi + 1,7х2 + 2,0х3^2 ,0

х ,^ 0 ; х2Ы); х3^ 0 ;

Z —Х\ + х 2+Х з—»-гпах.

Для решения задачи с применением симплексных таблиц систему неравенств превращаем в систему равенств путем введения дополнительных переменных: х4, х5, xs, и х-

Х\ + 1,5x2+ 1,2хз+ Х4= 1,5.

1,1 х1+ 0,75х2+ х 3+ х 5= 1,0.

350Х[ + 550х2+ 450х3+ х6=450

1,5xi + 1 ,7х2+ 2,0х3+ Х7= 2

Xi^O; х2> 0; х3> 0

Z= х1+ х2+ х3-ип ах.

Переходим к симплексной таблице (табл. 9).

Итак, за две итерации получен оптимальный план, при ко­ тором по первой технологии следует ремонтировать 0,6 N, по второй — 0,4 N, по третьей — 0,0 километров.

З а д а ч а 2

Дорога располагает материальными ресурсами на год:

рельсы — 5200 г; щебень — 70 000 jh3; шпалы — 90 000 шт.\

скрепления — 1500 г; трудовыми ресурсами — 110 000 чел-дней. Есть необходимость в производстве ремонтов пути: капиталь­ ного, среднего и подъемочного. Состояние пути позволяет де­ лать некоторое смещение объемов работ на следующий год, в котором предполагается получить дополнительные ресурсы.

59