«Brian D Bunday, B.Sc., Ph.D., F.S.S., F.I.M.A. School of Mathematical Sciences, University of Bradford Edward Arnold Б. Банди ОСНОВЫ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Перевод с английского О.В. Шихеевой Под редакцией В.А. ...»

Теперь при изменении только коэффициентов bj, уравнение (3.14) для новой задачи останется неизменным. Поэтому если базисное решение остается допустимым и для новой формулировки задачи, то оно будет и оптимальным базисным допустимым решением для этой задачи. Новые значения для базисных переменных находятся по формуле Если х* > 0, то оно будет базисным допустимым значением для новой задачи, а также оптимальным решением уравнения (3.14). Новым значением функции z будет Таким образом из уравнения (3.13) можно получить где zopt рассматривается как функция от b1, b2,…, bm. Разумеется, если сильно изменить bi, то точка хB*, определяемая уравнением (3.15), будет неоптимальна и задачу придется решать сначала.

Пример Рассмотрим еще раз пример 1 разд.1.1. (Для удобства повторим задачу.) Фирма производит две модели А и В сборных книжных полок. Их производство ограничено наличием сырья высококачественных, досок и временем машинной обработки. Для каждого изделия модели А требуется 3 м2 досок, а для изделия модели В - 4 м2. Фирма может получить от своих поставщиков до 1700 м2 досок в неделю. На каждое изделие модели А требуется 12 мин машинного времени, а на изделие модели В — 30 мин. В неделю можно использовать 160 ч машинного времени. Если каждое изделие модели А приносит 2 дол.

прибыли, а изделие модели В — 4 дол. прибыли, сколько изделий каждой модели фирме необходимо выпускать в неделю?

Если план выпуска изделий модели А — х1 единиц, а модели В – x2 единиц, то задача линейного программирования состоит в том, чтобы найти такие х1, x2 0, что при которых минимизируется функция -2x1-4x2=z (прибыль, взятая с обратным знаком).

Первая и последняя (оптимальная) таблицы имеют соответственно следующий вид:

Итерация Базис Значение x x2 x3 x Обращенный базис имеет вид В 1 = 7 7 ; симплекс-множители равны 2/7,4/7.

1. Предположим, что появилась возможность приобрести дополнительное сырье у второго поставщика. Сколько ему можно заплатить за 1 м2?

Допустим, что в первом ограничении 1700 было заменено на 1701. Вектор b заменяется на новый вектор 1600. Новыми значениями базисных переменных будут что допустимо.

Оптимальное значение для функции z меняется на значение (-bii) в данном случае Таким образом, прибыль возрастает на 2/7 дол., и это - максимальная цена, которую следует заплатить за дополнительный 1 м2 доски. Нет смысла приобретать дополнительное сырье.

Максимальная цена равна i.

2. Предположим, что имеется возможность получения дополнительного машинного времени.

Выгодно ли это, если 1 ч машинного времени зтоит 7 дол.?

В этом случае в математической задаче вектор b заменяется на вектор 1610.Новыми значениями базисных переменных будут Оптимальное значение для функции z заменяется на значение -(2/7*1700 + 4/7*1610) =-1400Прибыль увеличивается на 40/7 дол. Поскольку дополнительный 1 ч машинного времени стоит 7 дол., это невыгодно. ; Легко видеть, что решение этой задачи с начала приведет к тем же результатам. Но нет никакой необходимости начинать с начала. В больших по объему задачах это неэффективно.

Заметьте, что в пункте 1 новое значение для функции z равно -2 (300 + 5/7) - 4(200 - 2/7), а в пункте 2- равно -2(300 - 40/7) - 4(200 +30/7) 2) Изменения в сj.

Пример Пусть в примере 1 прибыль от одной модели А составляет P1 дол., а от одной модели В — Р дол. Для каких значений Р1 и Р2 полученное решение является оптимальным?

Целевая функция в первой таблице задается формулой –P1x1-P2x2 = z + 0. Поскольку в таблице изменяется только последняя строка, каноническая форма ограничений в том же базисе останется прежней, т. е.

Чтобы записать функцию z в канонической форме, следует исключить x1 и x2 из выражения для функции z. Это можно сделать, умножив первое ограничение (в конечной таблице) на P1, второе — на Р2 и прибавив их к выражению для функции z; в результате получим Решение будет оптимальным, если предположить, что оба коэффициента при небазисных переменных положительны. Поэтому решение оптимально при условиях Это видно из рис. 1.1, где точка В — оптимальная, если предположить, что линия уровня функции z, проходящая через точку В, лежит между двумя линиями ограничений, пересекающимися в точке В.

Этот подход очень полезен при анализе влияния изменений в значении сj на решение задачи.

Значения базисных переменных и канонический вид ограничений остаются неизменными.

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

3) Включение дополнительных переменных Пример Пусть оказалось возможным изготовить полки типа С и пусть для изготовления одной полки этого типа необходимо 4 м2 материала и требуется 20 мин машинного времени. Если прибыль от одного изделия составляет? дол., стоит ли браться за его изготовление?

Если изготовлять x5 единиц типа С, то задача в стандартной форме превращается в следующую: найти такие х1, х2, х3., х4, xs что и минимизировать функцию т.е..

В конечной таблице первые два элемента столбца, соответствующего x5, будут согласно уравнению (3.5) иметь следующий вид:

Поскольку симплекс-множители 1 = при х5 в канонической форме для функции z Конечная таблица примет следующий вид (изменения произошли только в столбце х5):

Если -Р + 64/21 0, то решение, приведенное в таблице, оптимально; x5 остается небазисной переменной, и не надо составлять новую модель.

Если -Р + 64/21 < 0, т. е. Р> 64/21, то необходимо включить x5 в базис. С этого момента можно продолжить вычисления симплекс-методом.

4) Включение дополнительных ограничений Пример Предположим, что в период экономического кризиса торговые агенты сообщают, что рынок принимает не более 550 полок в неделю. Как это отразится на производстве? Указанное ограничение на объем продажи равносильно ограничению х1 +x2550.

Это дополнительное ограничение должно быть включено в математическую постановку задачи. Однако в данном случае оно никак не влияет на оптимальное решение. В этом решении x1 = 300 и х2 =200, так что х1 +x2 =500 удовлетворяет дополнительному ограничению.

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

3.3. ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД Пример Предположим, что недельная продажа ограничена 450 полками. Тогда должно быть включено дополнительное ограничение x1+x2450.

В виде уравнения оно записывается как x1+x2+x5=450, где x5 0 - дополнительная переменная.

Это ограничение нарушается оптимальным решением исходной задачи. Необходимо ли решать эту задачу с самого начала с новым включением? Если так поступить и повторить проведенные вычисления, то дополнительное ограничение выразится через небазисные переменные, которые можно получить из текущей канонической формы Поэтому уравнение x1+x2+x5=450 после исключения х1 и x2 принимает вид Последняя таблица будет иметь следующий вид (изменения - только вид дополнительного ограничения):

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

Переменная х5 отрицательна. Существует ли, несмотря на это, способ coxpaнить результаты проделанной к этому моменту полезной работы? Да, и соответствующая процедура носит название двойственного симплекс-метода.

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

В нашей задаче базисная переменная x5 отрицательна и является кандидатом на удаление из базиса. Какая переменная должна ее заменить? В строке Xs таблицы ищется отрицательный ведущий элемент, такой, что при последующих преобразованиях (которые снова примут вид уравнений (2.15) - (2.20)) коэффициенты целевой функции будут оставаться положительными. Перед формализацией этих правил посмотрим, как они выполняются в нашей задаче. В строке x5 имеется только один отрицательный коэффициент - коэффициент при x3, равный -3/7. Если мы разделим уравнение на -3/7, чтобы включить в базисные переменные переменную x3 (с коэффициентом 1), то получим уравнение т. е. значение x3 станет положительным. Следующим шагом мы должны исключить переменную x3 из остальных ограничений и из целевой функции. Это достигается простыми симплексными вычислениями результаты, как показано ниже, могут быть сведены в таблицу. Ведущий элемент (отрицательное значение -3/7) отмечен звездочкой.

В конечной таблице приведено оптимальное решение новой задачи:

Поскольку в этом решении x3 - базисная переменная, имеется избыток сырья, и в результате количество заказанных досок может быть сокращено.

Описанная процедура может быть обобщена. Если все коэффициенты целевой функции положительны, то процедура будет иметь следующие шаги:

1. Найти отрицательную базисную переменную. Если ее нет, то оптимальное решение найдено; если их более чем одна, надо взять из них самую отрицательную. Пусть эта переменная - базисная в r-м. ограничении. Она является переменной для исключения из базиса.

2. В r-й строке найти отрицательный коэффициент a/rj. Если его нет, то, очевидно, не существует допустимого решения задачи. Для отрицательных коэффициентов в этой строке найти Если этот минимум найден в s-м столбце, переменная s должна быть включена в базис.

3. Провести обычные симплекс-преобразования, выбрав в качестве ведущего элемент a/rj.

Из уравнения (2.19) для следующей итерации имеем и, поскольку все a/rj отрицательны, а с/j положительны, эта величина положительна, так как s выведено из соотношения Следовательно, двойственный симплекс-метод отличается от симплекс-метода только выбором переменной для исключения и включения в базис.

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

Процедура двойственного симплекс-метода включена в программу, приведенную ниже, которая может быть использована для того, чтобы применить либо симплекс- метод, если базис допустим, либо двойственный симплекс-метод, если все коэффициенты целевой функции положительны. Программа почти аналогична первой из приведенных программ, за исключением программ 1 и 2, описанных выше. Она предполагает наличие канонической формы, в которой одна из базисных переменных может быть отрицательна. Если она используется для того, чтобы ввести дополнительное ограничение в уже решенную задачу, дополнительное ограничение сначала должно быть приведено к канонической форме.

READY.

10 REM ПРОГРАММА ДЛЯ СИМПЛЕКС-МЕТОДА И ДВОЙСТВЕННОГО

15 REM СИМПЛЕКС-МЕТОДА, ИМЕЮЩЕГО В ОСНОВЕ БАЗИСНОЕ РЕЕНИЕ

20 REM ВВЕСТИ КОЛИЧЕСТВО ОГРАНИЧЕНИЙ И КОЛИЧЕСТВО ПЕРЕМЕННЫХ

30 READ M,N 40 M1=M+ 50 DIM A(M1,N),BS(M),NB(N),V(M1)

60 PRINT “ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ”

100 REM ВВЕСТИ КОЭФФИЦИЕНТЫ ДЛЯ ОГРАНИЧЕНИЙ И ЦЕЛЕВОЙ

105 REM ФУНКЦИИ ПОСТРОЧНО 110 FOR I=1 ТО M1:FOR J=1 ТО N 120 READ A(I,J) 130 NEXT J:NEXT I

150 REM ВВЕСТИ НАЧАЛЬНЬЕ ЗНАЧЕНИЯ БАЗИСНЫХ ПЕРЕМЕННЫХ И

155 REM ЦЕЛЕВОЙ ФУНКЦИИ В МАССИВ А(I,0) 160 FOR I=1 ТО M1:READ A(I,0):NEXT I

200 REM ВВЕСТИ БАЗИСНЫЕ ПЕРЕМЕННЬЕ;ВS - МЕТКA БАЗИСНОЙ

205 REM ПЕРЕМЕННОЙ В ОГРАНИЧЕНИИ I

210 FOR I=1 ТО M:READ BS(I):NEXT I

250 REM ПОМЕТИТЬ НЕБАЗИСНЬЕ ПЕРЕМЕННЫЕ;ЕСЛИ J REM НЕБАЗИСНАЯ ПЕРЕМЕННАЯ,ТО NB(J)=

260 FOR I=1 ТО M:NB(BS(I))=1:NEXT I 290 НАПЕЧАТАТЬ ТАБЛИЦУ 300 РRINT "ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА" :РRINT “ИТЕРАЦИЯ” K 310 GOSUB 3000:STOP 400 ZERO 1E-

490 REM НАЙТИ НАИМЕНЬШИЙ КОЭФФИЦИЕНТ В СТРОКЕ Z (Т.Е.

495 REM СТРОКУ M1) 500 MIN=-ZERO:S=0:PV= 510 FOR J=1 ТО N 520 IF NB(J)=1 THEN GOTO 530 IF A(M1,J)>=MIN THEN GOTO 540 MIN=A(M1,J):S=J 550 NEXT J

560 REM ЕСЛИ S=0, TO ВСЕ КОЭФФИЦИЕНТЫ ПОЛОЖИТЕЛЬНЫ И

565 REM МИНИМУМ НАЙДЕН 570 IF S=0 THEN GOTO

740 REM НАЙТИ СТРОКУ ПЕРЕМЕННЫХ,КОТОРУЮ СЛЕДУЕТ

745 REM ИСКЛЮЧИТЬ ИЗ БАЗИСА ПО УСЛОВИЮ МИНИМУМА ВI/А(IS)

750 MIN=1E20:R= 760 FOR I=0 TO М 770 IF А(I,S)=MIN THEN GOTO 800 R=I:MIN=A(I,0)/A(I,S) 810 NEXT I

890 REM ЕСЛИ R=0, TO ИМЕЕТ МЕСТО РЕЕНИЕ БЕЗ ОГРАНИЧЕНИЙ

900 IF R=0THEN GOTO 910 РRINT "ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ":R: “/СТОЛБЦА" ;S 920 PRINT"

990 REM РАЗДЕЛИТЬ ВЕДУЩУЮ СТРОКУ НА ВЕДУЩИЙ ЭЛЕМЕНТ

1000 PV=A(R,S) 1010 FOR J=0 TO N:A(R,J)=H(R,J)/PV:NEXT J

1040 REM ВЫЧИСЛИТЬ НОВУЮ КАНОНИЧЕСКУЮ ФОРМУ, ЗАПОМНИВ

1045 REM ВЕДУЩИЙ СТОЛБЕЦ ДО ЕГО ИЗМЕНЕНИЯ

1050 FOR I=1 ТО M1:V(I)=A(I,S):NEXT I 11070 FOR I=1 TO M 1080 IF I=R THEN GOTO 1090 FOR J=0 TO N 1100 A(I,J)=(I,J)-V(I)*A(R,J) 1110 NEXT J 1120 NEXT I

1150 REM ПЕРЕНАЗНАЧИТЬ И ПОВТОРНО ПОМЕТИТЬ БАЗИСНЫЕ

1155 REM И НЕБАЗИСНЫЕ ПЕРЕМЕННЫЕ 1160 NB(BS(R))=0:NB(S)=1:BS(R)=S 1170 REM СЧЕТЧИК ИТЕРАЦИЙ 1180 К=К+ 1190 REM НАПЕЧАТАТЬ НОВУЮ ТАБЛИЦУ 1200 РPINT "ИТЕРAЦИЯ"К 1210 GOSUB 3000:STOP

1240 REM ПОВТОРИТЬ ИТЕРAЦИОННЬЙ ПРОЦЕСС

1250 GOTO

1490 REM ДВОЙСТВЕННЫЙ СИМПЛЕКС-МЕТОД;СНAЧAЛA НAЙТИ

1495 REM ПЕРЕМЕННЬЕ ДЛЯ ИСКЛЮЧЕНИЯ ИЗ БAЗИСA

1500 MIN=-ZERO:R= 1510 FOR I=1 ТО М 1530 IF A(I,0)> MIN THEN GOTO 1540 МIN=A(I,0):R=I 1550 NEXT I

1560 REM ЕСЛИ R=0,TO ВСЕ БAЗИСНЬЕ ПЕРЕМЕННЬЕ ПОЛОЖИТЕЛЬНЫ

1570 IF R=0 THEN GOTO

1600 REM НAЙТИ ПЕРЕМЕННЬЕ,КОТОРЫЕ СЛЕДУЕТ ВВЕСТИ В БAЗИС

1610 MIN=1E20:S= 1620 FOR J=1 TO N 1630 IF NB(J)=1 THEN GOTO 1640 IF A(R,J)>-ZЕRО THEN GOTO 1650 RТ=ABS(A(М1,J)/A(R,J)) 1660 IF RT>= MIN THEN GOTO 1670 S=J:MIN=ABS(A(M1,J)/A(R,J)) 1680 NEXT J 1760 REM ЕСЛИ S=0,TO НЕТ ДОПУСТИМОГО РЕШЕНИЯ 1770 IF S=0 THEN GOTO 1780 GOTO 1790 REM B СТРОКЕ 1780 ОСУЩЕСТВЛЯЕТСЯ ПЕРЕХОД К

1795 REM ПРЕОБРAЗОВAНИЮ В НОВУЮ КAНОНИЧЕСКУЮ ФОРМУ

1800 PRINT "HET ДОПУСТИМОГО РЕШЕНИЯ" 1810 GOSUB 1820 GOTO 1900 РRINT "ПЕРЕМЕННAЯ "S" HE ИМЕЕТ ОГРAНИЧЕНИЙ" 1910 GOSUB 1920 GOTO 2000 РRINT "ОКОНЧAТЕЛЬНОЕ РЕШЕНИЕ" 2010 РRINT "ОГРAНИЧЕНИЕ БAЗИС ЗНAЧЕНИЕ" 2020 РВ= 2030 FOR I=1 ТО М 2040 PRINT " ";I;" ";BS(I);

2050 РA=A(I,0):GOSUB 9000:PRINT "" 2060 NEXT I 2090 РRINT "МИНИМУМ ФУНКЦИИ Z РAВЕН "; -A(М1,0) 2100 GOSUB 2500 END 3000 РRINT "БAЗИС ЗНAЧЕНИЕ", 3010 FOR J=1 ТО N:PRINT "X" J " ";:NEXT J 3020 PRINT " " 3030 PB= 3040 FOR I=1 TO M 3050 IF I=M1 THEN PRINT "-Z";:GOTO 3060 PRINT BS(I);

3080 FOR J=0 TO N 3090 РA=A(I,J):GОSUВ 3100 NEXT J 3110 PRINT " " 3120 NEXT I:PRINT " " 3200 RETURN 4000 DATA 3, 4010 DATA -1,-2,1,0, 4020 DATA -2-1,0,1, 4030 DATA 7,8,0,0, 4040 DATA 1,1,6,0, 4050 DATA -6,-6 56, 4060 DATA 3,4, 9000 PC=INT(PB/100) 9010 Р$=" 9020 IF PC=0 THEN PRINT " ": GOTO 9030 PRINT LEFT$(P$,PC);

9040 PC=PB-100*PC 9050 PD=INT(PC/10):PC=PC-10*PD 9060 IF PD=0 THEN PD= 9070 IF РA=PD THEN PRINT PA;:RETURN 9110 P$=P$+MID$(STR$(INT(PE)),2,PD) 9120 PRINT RIGHT$(P$,PD+1) 9130 IF PC=0 THEN RETURN 9140 PRINT".";

9150 PE=INT((PE-INT(PE)*10^PC) 9160 P$=" 000000000" 9170 P$=P$+MID$(STR$(PE),2,PC) 9180 PRINT RIGHT$(P$,PC);:RETURN READY.

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

Пример Найти такие неотрицательные х1, х2, что х1 + 2 х2 6, 2 х1 + х2 6, 7 х1 + 8 х2 56, и минимизировать функцию х1+х2 =z.

В стандартной форме задача формулируется следующим образом: найти такие хj 0, что и минимизировать функцию х1+х2=z.

Если базисными переменными являются x3, x4 и x5 (т. е. небазисными переменными x1, х2), то целевая функция оптимальна. Этот базис недопустим, поскольку x3= 6 и x4= -6. Если умножить эти ограничения на -1 (для получения корректного вида базиса) будем иметь х1 + х2 = z Нам удалось избежать использования искусственных переменных в первых двух ограничениях. Можно продолжить вычисления непосредственно пользуясь двойственным симплекс-методом, результаты работы которого приводятся ниже в таблице.

Это — оптимальное решение. Оптимальный вид для функции z сохраняется, и полученный базис допустим. Таким образом, минимальное значение функции z равно 4 и достигается при х1 = 2 и x2 =2. Это можно проверить графически.

Данные в строках программы 4000-4060 соответствуют рассматриваемой задаче. Ниже приведена распечатка результатов работы программы, воспроизводящей приведенные таблицы.

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

ИТЕРАЦИЯ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 2 СТОЛБЦА

ИТЕРАЦИЯ

ВЕДУЩИЙ ЭЛЕМЕНТ НАХОДИТСЯ В СТРОКЕ 1 СТОЛБЦА

ИТЕРАЦИЯ

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

ОГРАНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ

МИНИМУМ ФУНКЦИИ Z РАВЕН

3.4. УПРАЖНЕНИЯ 1. Производитель выпускает два продукта: продукт Р, продаваемый по2000дол. за 1 т, и продукт Q, продаваемый по 1000 дол. за 1 т. Продукты могут производиться из двух типов сырья: А по 600 дол. за 1 т и В по 900 дол. за 1 т. Из каждых 100 т сырья А производят 30 т Р и 50 т Q, а из 100 т сырья В производят 60 т Р и 10 т Q. Если производитель обрабатывает х т А и у т В, покажите, что его прибыль составляет (500х + 400у). Фабрика способна обработать не более 10 000 т сырья ежегодно. Поставщики сырья могут обеспечить не более 6000 т сырья А и не более 8000 т сырья В в год. Производитель может продавать ежегодно по т продукта Р и до 3200 т продукта Q. а) Определите, сколько сырья А и В должно быть заказано для максимизации его прибыли, и покажите, что эта прибыль составляет 4 дол.

Поставщики сырья А угрожают повысить цену. б) На сколько можно поднять цену, чтобы производителю пришлось изменить заказ?

2. Найдите такие хi, что и минимизируйте функцию f=10x1-111x2. Найдите оптимальную симплекс-таблицу.

Пусть необходимо дополнительное ограничение х3 + x4 5. Примените двойственный симплекс-метод для решения расширенной задачи, начиная с оптимального решения исходной.

3. Найдите Покажите, что (после введения дополнительных переменных в ограничения) симплексмножители i, связанные с оптимальным решением, должны удовлетворять условиям Замечание:

- i -коэффициент при хn+1 в оптимальном решении для функции z.

Проверьте, что условие б) выполняется, если справедливо соотношение 4. Фабрика производит три основных типа товара. Изделию типа I требуется 3 единицы сырья А и единица сырья В; оно приносит прибыль в 3 единицы. Изделию типа II требуется 4 единицы сырья А и 3 единицы сырья В; оно приносит прибыль в 6 единиц. Изделию типа III требуется единица сырья А и 2 единицы сырья В; оно приносит прибыль в 2 единицы.

Найдите оптимальный план производства, если доступны всего 20 единиц сырья А и единиц сырья В. Если окажется доступной еще одна единица сырья А (или В), какую наибольшую цену следует за нее платить?

5. Прибыль от изделий А, В, С составляет соответственно 3, 4, 5 единиц. Для каждого изделия требуется время использования станка I и II, которые доступны соответственно 12 и 15 ч в день:

Найдите оптимальный план производства. Назначьте дополнительное время использования станка 1(11).

6. Фирма специализируется на производстве буфетов. Она может производить три типа буфетов А, В, С, что требует различных затрат труда на каждой стадии производства:

В течение недели можно планировать работу на лесопилке на 360 чел-ч, в сборочном цехе на 520 чел-ч и в отделочном цехе - на 220 чел-ч. Прибыль от продажи каждого буфета типов А, В, С составляет соответственно 9, 11, 15 дол. Покажите, что задача составления оптимального плана производства может быть выражена в следующем виде:

найти такие хi 0, что и минимизировать функцию = 9 х1 + 11х2 + 15 х3. Объясните физический смысл каждой переменной и воспользуйтесь симплекс-методом, чтобы показать, что в оптимальном решении х1 = 180, х2 = 40, х3 = 0.

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

Для выполнения обязательств по организации интерьера гостиниц необходимо производить по крайней мере 10 буфетов типа С еженедельно. Как это дополнительное требование повлияет на решение?

7. Аудитории и лаборатории университета рассчитаны не более чем на 500 студентов.

Университет не принимает более 4000 студентов своей страны, но разрешает прием любого количества иностранных студентов.

Персонал университета составляет 440 человек. Для обучения 12 студентов' данной страны и 10 иностранных студентов требуется один преподаватель. Необходимо, чтобы 40 % студентов данной страны и 80 % иностранных студентов могли разместиться в аудиториях, где имеется 2800 мест. Университет получает 2000 фунтов стерлингов в год из правительственных средств на каждого студента своей страны и берет плату в размере фунтов стерлингов в год за каждого иностранного студента.

Предположив, что единственной целью университета является максимизация прибыли, определите, какой прием студентов своей страны и иностранных студентов следует планировать. Покажите, что максимальный годовой доход составляет 11 850 000 фунтов стерлингов в год.

Университет может нанять дополнительный персонал с годовым окладом 10 000 фунтов стерлингов. Выгодно ли это?

8. Фирма производит на фабрике четыре сорта изделий. Производство лимитируется временем использования станков и количеством комплектующих изделий. Известно также, что суммарное время использования станков — 90 ч в день, а комплектующих изделий может быть поставлено не более 80 в день.

Произв одственные характеристики Ежедневное производство хj изделия j является решением следующей задачи:

минимизировать функцию z = х 1 2 х2 4 х3 3х4, при ограничениях х1 + 3х2 + 8 х3 + 4 х4 90, 2 х1 + 2 х2 + х3 + 3х4 80, х j 0, j = 1,....,4.

Объясните постановку этой задачи.

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

1) Найдите симплекс-множители.

2) Найдите обращенный базис.

3) Фирма может увеличить время работы станков до 10 ч в день, арендуя оборудование, что будет стоить 40 дол. в день. Рентабельно ли это; если да, то какой нужен новый план производства?

4) Стоимость одного из видов сырья, используемого при производстве изделий 1 и 3 часто меняется. В данный момент стоимость сырья составляет 80 дол. за 10 кг. Изделию требуется 1. кг на единицу сырья, а изделию 3-2- кг на единицу сырья. Цена этого сырья включена в приведенную выше стоимость продукции. В каких пределах может колебаться цена этого вида сырья, чтобы исходное решение осталось тем же самым?

5) Беспорядки на заводе одного из потребителей приводят к тому, что дневной выпуск изделия 4 должен быть сокращен до 15 единиц. Воспользуйтесь двойственным симплексметодом для составления нового производственного плана.

9. Найдите x1 0, x2 0, удовлетворяющие условиям и минимизирующие функцию 50x1+25x2 не используя искусственных переменных.

10. Найдите x10, x20, удовлетворяющие условиям и минимизируйте функцию x1+ x2=z.

11. Покажите для общей задачи линейного программирования, что если xj зависит от bi, (считайте, что базис остается допустимым после изменений).

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

найти x1 и х2 неотрицательные и такие, что и минимизировать функцию -2x1 -5x2=z.Найдите решение этой задачи с помощью симплексметода.

Технолог, которому полученное решение было передано для реализации, выразил большое сомнение. После дальнейших обсуждений было решено, что следует ввести дополнительное ограничение х1 + 2 х2 8.

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

13. Используя программу для симплекс-метода или для двойственного симплекс-метода, напишите программу для решения задачи линейного программирования с GC ограничениями в виде неравенств со знаком и LC ограничениями в виде неравенств со знаком.

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

14. Воспользуйтесь написанной программой для решения следующей задачи:

найти такие x10, x20, x30, что и минимизировать функцию 3x1 +x2+2х3=z 15. Пусть при решении задачи линейного программирования симплекс-методом на k-й итерации каноническая форма задачи задается уравнениями (2.4) и (2.5) в матричной форме.

Пусть переменная х3 включается в базис, а базисная переменная хr в r-м ограничении исключается из базиса. Покажите, что умножение канонической формы на матрицу приводит к следующей канонической форме. Покажите, что если В-K1 - обращение базиса на k-й итерации. В-1K+1 — обращение на (k + 1) -итерации, то Вк+1 = ЕВк Выпишите матрицу Е.

ГЛАВА 4 ТРАНСПОРТНАЯ ЗАДАЧА

4.1. ПОСТАНОВКА ЗАДАЧИ И ЕЕ РЕШЕНИЕ

Пример Фирма должна отправить некоторое количество кроватей с трех складов в пять магазинов.

На складах имеется соответственно 15, 25, 20 кроватей, а для пяти магазинов требуется соответственно 20, 12, 5, 8 и 12 кроватей. Стоимость перевозки одной кровати (в долларах) со склада в магазин приведена в таблице.

Как следует спланировать перевозку кроватей для минимизации стоимости? Пусть хij количество кроватей, отправляемых со склада в магазин. Ясно, что хij0, и в силу ограничений на возможности поставки со складов (предложение) и спрос в магазинах они удовлетворяют следующим условиям:

(для предложения);

(для спроса). Стоимость, равная С = х11 0 х12 + 3 х13 + 4 х14 + 2 х15 + 5 х21 +... + 4 х34 + 3х35, должна быть минимизирована при этих ограничениях.

Эта задача является задачей линейного программирования, но специального вида. В частности, коэффициенты в ограничениях принимают значения 0 или 1, а каждая переменная входит только в два ограничения. На первый взгляд может показаться, что ограничения в виде равенств, определяющих предложение, должны быть заменены на ограничения в виде неравенств со знаком, а ограничения в виде равенств, определяющих спрос на ограничения в виде неравенств, - со знаком. Однако, поскольку суммарный спрос равен сумме поставок, во всех случаях должно выполняться равенство. Заметим также, что сумма по первым трем ограничениям дает тот же результат, что и сумма по последним пяти ограничениям.

Поскольку независимых ограничений только 7, а не 8, следовательно, базисное допустимое решение и оптимальное решение будет содержать 7 ненулевых значений хij.

Эти результаты обобщаются на транспортную задачу с т пунктами производства и объемами производства аi (i = 1, 2,..., т ), и п пунктами потребления и объемами потребления bj (j = 1,..., n), где Если с - стоимость транспортировки одного изделия из пункта производства i в пункт потребления j, то задача заключается в нахождении хij 0, удовлетворяющих соотношениям

минимизирующих функцию Короче, соотношения (4.2) можно переписать так:

найти такие хij 0, для которых справедливы неравенства и которые минимизируют функцию согласно уравнению (4.1), имеется всего т + n - 1 независимых ограничений и, следовательно, т + n - 1 базисных переменных в базисном допустимом решении.

Удобнее не рассматривать ограничения, а работать с массивом транспортных данных в виде, приведенном ниже. Следует разместить неотрицательные переменные в клетках таким образом, чтобы суммы по строкам и столбцам совпадали с указанными правыми частями ограничений в виде равенств примера 1 и чтобы сумма произведений этих переменных на стоимости (указанные в правом нижнем углу каждой клетки) была минимальна. Приведенный на рисунке массив соответствует данным примера 1:

Переход к общему случаю очевиден.

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

Поскольку задача состоит в минимизации общей стоимости, находим наименьшую стоимость во всех клетках: 0 в строке 1, столбце 2 и присваиваем переменной х12 значение (наименьшая из сумм по строке и по столбцу). Теперь столбец 2 можно удалить, уменьшив сумму по строке на 12, т. е. заменив ее на 3. Потом та же процедура применяется к полученному массиву.

Затем переменной х11 присваивается значение 3 (или переменной x33 — значение 5), удаляется строка 1, сумма по столбцу 1 заменяется на 17 и осуществляется переход к следующему массиву и т. д.

После небольшой тренировки для задач небольшого объема эту процедуру можно проводить устно. После того как последней переменной присвоено значение, суммы по всем строкам и столбцам будут равны 0. Таким образом получается решение (значения переменных находятся в левых верхних углах клеток) с семью приводимыми ниже базисными переменными. Остальные переменные равны 0. Для общего массива из т строк и п столбцов получаем т + п - 1 переменных в силу (4.1) С=3*1+12*0+2*5+8*3+15*3+15*4+5*1= 147 дол.

Попробуем теперь улучшить это решение, уменьшив стоимость С. Отметим, что полученные результаты для этого частного случая и метод их получения применимы и в случае общей транспортной задачи (см. соотношения (4.2)).

Пусть сsr имеет наименьшее значение из всех сij. Положим хsr равным наименьшей величине из аs и br. Если этой величиной будет аs, то удалим строку s, заменим br на br – аs и применим вышеописанную процедуру к оставшемуся массиву. Полученное таким образом базисное решение будет содержать т+п-1 базисных переменных, и каждая из этих переменных хij будет задаваться соотношением Можно доказать, что этот результат справедлив для всех базисных допустимых решений.

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

Теперь докажем следующие утверждения.

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

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

Для массива размерностью m * n и, если каждая строка содержит по крайней мере две базисные переменные, то количество базисных переменных не меньше 2т; если каждый столбец содержит по крайней мере две базисные переменные, то количество базисных переменных не меньше 2п. Таким образом, общее количество базисных переменных не меньше т + п. Но это невозможно, поскольку имеется всего т + п - 1 базисных переменных.

Поэтому хотя бы одна строка или хотя бы один столбец содержат лишь одну базисную переменную.

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

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

Если выполняется первое из этих равенств (т. е. аp < bp ), то удаляется строка р, а bp заменяется на bq – аq. Затем рассуждение повторяется для оставшегося массива, т. е.

полагается, что Повторив эту процедуру несколько раз, увидим, что все базисные переменные имеют вид Следствие. Заметим, что если все ai или bi — целые, значения базисных переменных в допустимом базисном решении тоже целые. Поскольку это задача линейного программирования, оптимальное решение является базисным допустимым решением и, следовательно, целым.

Это очень важное следствие; оно гарантирует, что в задачах не будет получено абсурдное решение (например, 7 4 кроватей в примере 1).

4.2. АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОГО УЛУЧШЕНИЯ ПЛАНА

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

Л. Хитчкоком. Рассмотрим задачу из примера 1 разд. 4.1 (результаты можно обобщить, используя симплекс-множители, описанные в предыдущей главе).

Для примера 1 базисное допустимое решение, полученное по правилу "самая дешевая продукция реализуется первой", было построено. При этом было показано, что результаты можно обобщить.

Предположим, что для рассмотренной задачи уже построено допустимое базисное решение, в котором некоторые из переменных xij отличны от 0, а остальные переменные — небазисные и, следовательно, равны 0.

Если – иi. и –vj - симплекс-множители для ограничении, соответствующих i-й строке и j-му столбцу в этом базисе, то после умножения i-й строки на –иi, j-го столбца на –vj, и прибавления стоимости С получаем

Уравнение (4.7) — это специальный вид уравнения (3.7) для транспортной задачи.

Коэффициент при хij равен сij – иi – vj, так как xij входит всего в два ограничения, соответствующих i-й строке и j-му столбцу.

Далее если уравнение (4.7) является канонической формой целевой функции, соответствующей базису, то коэффициенты при базисных переменных равны 0.

Таким образом, для занятых клеток массива справедливо соотношение следовательно, можно определить иi и vj.

Имеется т неизвестных и. и п неизвестных v., », поскольку базисными переменными занято т + п — 1 клеток, из уравнения (4.8) получаем т + n — 1 уравнений т + п неизвестных. Эти уравнения можно решить, положив одно из неизвестных равным 0 и решив систему относительно остальных неизвестных. Это всегда возможно. В примере 1 на первом шаге имеем следующее базисное допустимое решение:

Имеется 8 неизвестных u1, u2, u3 и v1... v5 и 7 занятых клеток. Если положить u2=0, то в трех занятых клетках этой строки получим v1 = 5, v4 = 3 и v5 =3. Поскольку v1=5, то в занятых клетках этого столбца u1=-4 и u2=-1. Наконец, так как u1=-4, u3=-1,то v2=4, v3=2. Таким образом получаются указанные в скобках значения для Теперь можно проверить, оптимально ли это решение. Если с/ij - коэффициент при хij в канонической форме для целевой функции, то из уравнений (4.7) следует, что Для базисных переменных cij=0. Для небазисных переменных отрицательное значение с/ij указывает на то, что переменная хij должна быть включена в базисные переменные, что приведет к уменьшению целевой функции. В связи с этим с'ij вычисляется для незанятых клеток; те из них, в которых значение с'ij отрицательно, помечаются. Результат указан в левых нижних углах массива. На этом этапе нулевые значения переменных указывают на то, что их введение в базис не изменит значение целевой функции.

Ясно, что для нашей задачи увеличение х22 приведет к уменьшению целевой функции.

Действительно, каждое увеличение х22 на 1 уменьшит целевую функцию на 3. При увеличении значения х22 на число w необходимо уменьшить x21 на число w, чтобы сохранить сумму в строке (2). Для того чтобы сохранить значение суммы в столбце (1), необходимо увеличить x11 на число w, а затем для сохранения суммы в строке (1) уменьшить х12 на число w. Заметим, что другой метод: положить х22 = w, уменьшить х42 на число w до значения 8 - w, поскольку невозможно сохранить сумму в столбце (4), не вводя дополнительных переменных, -приводит к некоторым трудностям и с его помощью невозможно получить базисное решение. Программа должна избегать таких "тупиковых путей".

Таким образом, максимальное значение, которое может иметь w, равно 2. В этом случае переменная х21 становится небазисной и нулевой в следующем допустимом базисном решении:

Для этого массива С=5*1+10*0+2*1+8*З+15*З+15*4+5*1=141=147-3*2= (предыдущее значение) + c/22*w.

Далее определяем ui и vj для этого решения. (Проверьте, что заключенные в скобки значения указаны верно.) Значения с/ij для небазисных переменных, равных 0 или отрицательных, указаны в левых нижних углах клеток массива. Очевидно, что в базис следует включить переменную x35. Если изменить эту величину на число w, то другие величины должны быть заменены указанным образом. (Проследите за этим.) В результате наибольшее возможное значение для w равно 10, и это приводит к тому, что в следующем массиве переменная л: станет небазисной.

Значение стоимости С уменьшается:

C=15*1+12*1+8*3+5*3+5*4+5*1+10*3=121=141-2/10= (предыдущее значение) + с/35 *w.

Для этого массива вычисляются иi и vj. Для незанятых клеток все с/ij положительны. Таким образом получено оптимальное решение, в котором Минимальное значение стоимости С равно 121 дол. Отметим, что значение стоимости С задается уравнением что непосредственно следует из уравнения (4.7), так как в его левой части все слагаемые равны 0 (поскольку либо переменная базисная, а следовательно, коэффициент при ней равен нулю, либо переменная небазисная и, значит, равна 0) Заметим, что уравнение (4.10) — просто частный случай уравнения (3.11) для транспортной задачи.

Проверьте справедливость уравнения (4.10) для каждого из массивов. Такая проверка полезна на каждом шаге итерационной процедуры.

Отметим, что в рассматриваемой задаче х12 равно 0 в оптимальном решении, несмотря на то, что стоимость, указанная в этой клетке, равна 0; результат этот неожидан но, безусловно, верен.

4.3. ДИСБАЛАНС И ВЫРОЖДЕННОСТЬ В ТРАНСПОРТНОЙ ЗАДАЧЕ

Выполнение условия (4.1) очень важно в транспортной задаче. Для массива размерностью т*п оно означает, что в базисное допустимое решение входит т*п - 1 базисная переменная.

Предположим, что этот баланс между спросом и предложением нарушен.

Пример 1 (вариант примера 1 из разд. 4.1 и 4.2) Пусть 15, 25, 20 кроватей, хранящихся на складах W1, W2, W3, должны быть распределены по четырем магазинам, где требуется 20, 12, 5 и 9 кроватей. Пусть стоимость перевозки одной кровати со складов в магазины задается таблицей Как следует планировать перевозку для минимизации стоимости? Склады располагают кроватями. Магазинам требуется лишь 46 кроватей. Для того чтобы перейти к транспортной задаче, введем фиктивный магазин, которому требуется 14 кроватей. Стоимость перевозок со склада в этот магазин полагается равной 0. Если в окончательном решении будет получено, что некоторые кровати надо будет отправить в этот магазин, то это будет проигнорировано.

Кровати останутся на складе. Таким образом, поставлена транспортная задача, для которой уравнения (4.1) выполняются.

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

исключается из базиса:

14 кроватей из клетки (3, 5) остаются на складе 3. Потребности магазинов полностью удовлетворены. Мы получили оптимальное решение Ясно, как справиться с дисбалансом, если спрос превышает предложение: надо ввести фиктивного поставщика с нулевой стоимостью перевозок. Продукция этого поставщика на самом деле поставляться не будет. Спрос на нее не будет удовлетворен.

Вырожденность в транспортной задаче возникает, если одна или более базисных переменных обращаются в 0. Из соотношения (4.6) видно, что вырожденное решение может быть получено, если частичные суммы сумм по столбцам равны частичным суммам сумм по строкам. Проблему можно решить без особых трудностей. На каждом шаге следует различать базисные переменные, которые равны 0 и стоят в соответствующих клетках, и небазисные переменные.

При построении первого базисного допустимого решения могут возникнуть трудности, если суммы и по строкам, и по столбцам равны между собой и обратились в 0. В этом случае из дальнейших рассмотрении следует исключить только одну из них. Другая сумма будет ликвидирована при присвоении базисной переменной значения 0. Поскольку на каждом шаге, кроме последнего, удаляется только одна строка или только один столбец, то в результате получается m+п-1 базисных переменных и столько заполненных клеток, сколько требуется (даже если некоторые базисные переменные обратились в 0).

Трудности могут возникнуть и при улучшении базисного допустимого решения. Применение правил может обратить в 0 более одной базисной переменной. В этом случае важно помнить, что только одна из них должна стать небазисной; остальные следует сохранить базисными, но с нулевыми значениями. Их составляют клетки с целью определения иi и vj.

Пример Правительственное учреждение получило следующие предложения от фирм F1, F2 и F3 на покупку форменных пальто трех размеров S1, S2 и S3:

Должны быть заключены контракты на продажу 1000 пальто размера S1, 1500 пальто размера S2 и 1200 пальто размера S3, однако ограниченность производственных мощностей фирм приводит к тому, что общее количество заказов не может превосходить 1000 пальто для фирмы F1, 1500 пальто для фирмы F2 и 2500 пальто для фирмы F3. Необходимо, чтобы эти контракты были заключены с минимизацией общей стоимости, однако ограничения должны быть распределены по фирмам как можно справедливее. Как следует распределить заказы для выполнения этих требований?

Заметим, что общее предложение (5000 пальто) превосходит общий спрос (3700 пальто).

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

Массив задачи принимает вид Ниже приводятся первое базисное решение, симплекс-множители иi, vj и т. д. и первая итерация вычислений:

Максимальное значение w равно 2; оно обратит в 0 и x32, и х23 (в очевидных обозначениях).

Только одна из этих переменных, предположим x23, удаляется из базиса. Ниже приведено базисное допустимое решение с симплекс-множителями иi и vj, содержащее шесть базисных переменных, одна из которой равна 0:

Максимальное значение w равно 10:

Максимальное значение w равно 3, и следующее решение не вырождено:

Максимальное значение w равно 10:

Последнее решение оптимально. Однако, поскольку с/12 = 0, эта переменная также может быть введена в базис без изменения функции С. Максимальное значение w равно 2:

Следовательно, имеется два оптимальных решения, для которых стоимость С = 410 900 дол.

Первое решение: фирма F2 поставляет 1000 пальто размера S1 и 200 пальто размера S2; фирма F3 поставляет 1300 пальто размера S2 и 1200 пальто размера S3.

Второе решение: фирма F1 поставляет 200 пальто размера S2, фирма F2 - 1000 пальто размера S1, фирма F3 - 1300 пальто размера S2 и 1200 пальто размера S3.

Второе решение кажется более приемлемым, хотя такое распределение заказов тоже несправедливо, как и в первом решении.

Вырожденности можно избежать, слегка изменив суммы по строкам так, чтобы частичные суммы сумм по строкам не совпадали с частичными суммами сумм по столбцам. Можно положить суммы по строкам равными 10,01; 15,01; 25,01; по столбцам 10; 15; 12 и 13,03. В окончательном решении можно округлить дробные значения до целых. Проведите вычисления (ясно, что они аналогичны вышеописанным вычислениям).

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

4.4. ПОСТАНОВКА ТРАНСПОРТНОЙ ЗАДАЧИ НА ЭВМ

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

Теперь приведем блок-схему определения первого допустимого базисного решения (строки 500-840) [рис. 4.18].

В конце этой процедуры все элементы массива DA(I) и DB(J) должны быть равны 0.

Переменные TR(I) и ТС(1) должны быть равны количеству переменных соответственно в 1-й строке и в J-м столбце.

В следующей процедуре (строки 1000-1585) вычисляются u и v и наименьшее значение с/ij предположим с/kl (рис. 4.19).

Процедура перехода к новому базисному допустимому решению (начиная со строки 2000 до строки 3250) заслуживает внимательного изучения. Поясним ее подробнее. Сначала находится "цепь" ± w клеток, которая не является "тупиковым путем" (строки 2050-2730).

На шаге 1 мы находимся в клетке (К, L), Т - счетчик шагов, IP - индикатор "тупикового пути", (RT(T), СТ(Т)) = (RI, CJ) - клетка, в которую мы попадаем на шаге Т. Массив D состоит из ± 1, соответствующих ±w; положим ММ = 1, если клетка используется, IU = 1 и IV = 1, если строки и столбцы входят в цикл.

В команде 2100 на шаге Т ищется строка RT(T) для столбца, содержащего базисную переменную в неиспользованном столбце (строка 2140) в неотмеченной клетке (строка 2150). Если это единственная переменная в своем столбце, то производится присваивание IP = 1 (строка 2170). Разумеется, это не делается в начальном столбце L. После того как подходящая переменная найдена в столбце CJ, поиск прекращается; при этом FC = 1.

Затем Т увеличивается для следующего шага, в переменную RT(T) заносится номер текущей строки, а в переменную СТ(Т) - номер только что найденного столбца CJ; соответствующему D присваивается значение -1, и найденная клетка помечается присвоением ММ значения (строка 2320). Если мы снова оказались в столбце L, откуда начали, то цикл завершен (строка 2400). В противном случае ищем столбец СТ(Т) [=CJ] для строки, содержащей базисную переменную в неотмеченных строке и клетке; таким образом снова помечаются "тупиковые пути". Как только искомый столбец найден, поиск прекращается присвоением FR = 1. Затем Т увеличивается для следующего шага, переменной RT (Т) присваивается номер только что найденной строки RI, а СТ(Т) - номер только что обрабатывавшегося столбца; для этой клетки осуществляются присвоения: D = +1, MM = 1, после чего программа возвращается к поиску строки в строке 2100 программы.

Заметим, что если в процессе поиска строки не удается найти столбец (CJ = 0 в строке 2190), не являющийся "тупиковым путем", то происходит возвращение (строка 2210) к строке предыдущего поиска столбца. Если в поисках столбца удается найти только строки (RI = 0 в строке 2590), соответствующие тупиковым путям, то осуществляется возвращение (строка 2610) к строке предыдущего поиска строки. Однако в силу того, что ММ сохраняет свое значение, ошибка не повторяется в дальнейшем (ММ = 1 в строках 2150 и 2550). Поскольку базис задан треугольной системой уравнений, процесс в конце концов закончится и управление будет передано из строки 2400 в строку 3000.

В строках 3000 - 3040 программы содержится наименьшая базисная переменная из клеток, в которых D= -1. Здесь определяются значение w и положение переменной (КК, LL), которая будет удалена из базиса. В строках 3100 — 3120 клетки включаются в цепь. В конечном счете переменная (К, L) определяется как базисная, переменная (КК, LL) -как небазисная и определяется количество базисных переменных во всех строках и столбцах. Затем программа возвращается к вычислению симплекс-множителей и и v.

При работе программы печать (и и v) в строках 1340- 1342 и наибольшего по модулю значения с/ij в строке 1581, а также печать в строках 2071, 2321 и 2721 могут быть подавлены.

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

Приводимые данные соответствуют примеру 1 разд. 4.1. Читателю следует проследить за шагами решения. Принятый путь не соответствует нашему полученному вручную решению, но настолько же законен. На самом деле, первые два из полученных допустимых базисных решений вырождены.

READY.

20 PRINT "PEШЕHИE ТРАНСПОРТНОЙ ЗАДАЧИ"

З0 REM В ЗАДАЧЕ РАССМАТРИВАЮТСЯ М СТРОК И N СТОЛБЦОВ

40 READ M,N

50 REM МАССИВЫ А(1) И В(J) ЯВЛЯЮТСЯ ОБЩИМ ОБОЗНАЧЕНИЕМ СТРОК

51 REM И СТОЛБЦОВ; МАССИВЫ DA(I) И DB(J) ПРЕДНАЗНАЧЕНЫ ДЛЯ

52 REM ХРАНЕНИЯ ИХ КОПИЙ; МAССИВЫ IР(I) И IC(J) УКАЗЫВАЮТ

53 REM (ЕСЛИ ИХ ЭЛЕМЕНТЫ РАВНЫ 1),ЧТО СООТВЕТСТВУЮЩИЕ СТРОКИ

54 REM И СТОЛБЦЫ БЫЛИ УДАЛЕНЫ; МАССИВЫ ТР(I) И TC(J) ЯВЛЯЮТСЯ

55 REM СЧЕТЧИКАМИ БАЗИСНЫХ ПЕРЕМЕННЫХ В СТРОКАХ И СТОЛБЦАХ 60 DIM A(M),DA(M),B(N),DB(N),IR(M),IC(N),TR(M),TC(N) 65 REM МАССИВЫ IU(I) И IV(J) УКАЗЫВАЮТ (ЕСЛИ ИХ ЭЛЕМЕНТЫ

66 REM РАВНЫ 1),ЧТО ЭЛЕМЕНТАМ МАССИВОВ U И V БЫЛИ ПРИСВОЕНЫ

67 REM ЗНАЧЕНИЯ 70 DIM U(M),V(N),IU(M),IV(N) 80 DIM RT(M+N),CT(M+N)

85 REM МАССИВ C(I,J) СОДЕРЖИТ СТОИМОСТИ,МАССИВ X(I,J) REM НЕИЗВЕСТНSЕ; МАССИВ IX(I,J) ОБОЗНАЧАЕТ БАЗИС,ЕСЛИ ЕГО

95 REM ЭЛЕМЕНТЫ РАВНЫ 100 DIM C(M,N),X(M.N),IX(M,N),D(M,N),MM(M,N)

105 REM ПРОЧИЕ МАССИВЫ ЯВЛЯЮТСЯ РАБОЧИМИ

110 REM ПОДРОБНОСТИ ОПИСАНЫ В ТЕКСТЕ КНИГИ

140 REM ВВЕСТИ СТОИМОСТИ,ОБЩИЕ СТРОКИ И СТОЛБЦЫ

150 FOR I=1 ТО М 160 EOR J=1 ТО N 170 READ C(I,J) 180 NEXT J 190 NEXT I 200 FOR I=1 TO M:READ A(I):DA(I)=A(I):NEXT I 210 FOR J=1 TO N:READ В(J):DB(J): NEXT J

490 REM НАЙТИ НАИМЕНЬШУЮ СТОИМОСТЬ В МАССИВЕ C(RI,CJ)

500 C=0:CT=0:CR= 510 RI=0:CJ=0:Y=IE 600 FOR I=1 ТО М

605 REM ПРОПУСТИТЬ УДАЛЕННЫЕ СТРОКИ

613 IF IR(I)=1 THEN GOTO 620 FOR J=1 ТО N

625 REM ПРОПУСТИТЬ УДАЛЕННЫЕ СТОЛБЦЫ

630 IF IC(J)=1 THEN GOTO 640 IF C(I,J)>Y THEN GOTO 650 Y=C(I,J):RI=I:CJ=J 660 NEXT J 670 NEXT I

680 REM МИНИМАЛЬНЫЙ ЭЛЕМЕНТ ПО ВСЕМ СТРОКАМ И СТОЛБЦАМ

681 REM ПЕРЕСЛАТЬ В МАССИВ X(RI,CJ)

685 REM ПОМЕТИТЬ БАЗИС В МАССИВЕ IX

690 REM УДАЛИТЬ СТРОКУ ИЛИ СТОЛБЕЦ И ПОМЕТИТЬ ИХ

695 REM ОПРЕДЕЛИТЬ ДРУГУЮ СУММУ, ПОДСЧИТАТЬ КОЛИЧЕСТВО

696 REM УДАЛЕНИЙ СТРОК 700 IF DA(RI)=T THEN GOTO 1550 T=D(I,J):K=I:L=J 1560 NEXT J 1570 NEXT I 1575 REM ЕСЛИ Т ВСЕ ЕЩЕ БОЛЬШЕ 0, ТО ВСЕ D(I,J) ПОЛОЖИТЕЛЬНЫ

1576 REM И ДAННОЕ РЕШЕНИЕ ОПТИМAЛЬНО

1580 IF T=0 THEN GOTO 1581 PRINT" :PRINT 'C' " KL=" T;:PRINT"K=" K;:PRINT"L=":PRINT "" 1582 PRINT"":GOSUB 1585 REM В ПОДПРОГРАММЕ, НAЧИНAЮЕЩЕЙСЯ СО СТРОКИ 5000,

1586 REM ПЕЧAТAЕТСЯ БАЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ

1990 REM НAЙТИ СЛЕДУЮЩЕЕ БAЗИСНОЕ ДОПУСТИМОЕ РЕШЕНИЕ.

1995 REM СНAЧЙЛA ВСЕ ЙНДИКAТОРЫ И СЧЕТЧИКИ ПОЛОЖИТЬ РAВНЫМИ

2000 FOR I=1 TO M:IU(I)=0:NEXT I 2010 FOR J=1 TO N:IV(I)=0:NEXT J 2015 FOR I=1 TO M+N:RT(I)=0:CT(I)=0:NEXT I 2020 FOR I=1 TO M:FOR J=1 ТО N 2030 D(I,J)=0:MM(I,J)= 2040 NEXT J:NEXT I 2050 T=1:IP= 2860 RT(T)=K:CT(T)=L 2070 D(K,L)=1:MM(K,L)=1:IU(K)= 2071 PRINT T,K;L 2100 FR=0:FC=0:RI=RT(T):CJ= 2110 FOR J=1 TO N 2120 IF FC=1 THEN GOTO 2130 IF IX(RI,J)=0 THEN GOTO 2140 IF IV(J)=1 THEN GOTO 2150 IF MM(RI,J)=1 THEN GOTO 2155 IF TC(J)=1 AND J=L THEN GOTO 2160 IF ТС(J)=1 THEN IP=1 :GOTO 2170 FС=1:СJ=J:IV(J)=1:J=N 2180 NEXT J 2190 IF CJ0 THEN GOTO 2200 IF IP >0 THEN IP= 2210 D(RT(T),CT(T))=0:T=T- 2220 GOTO 2300 T=T+ 2310 RT(T)=RI:CT(T)=CJ 2320 D(RI,CJ)=-1:MM(RI,CJ)= 2321 PRINT T,RI;CJ 2400 IF CT(T)=L AND T>2 THEN GOTO 2500 FR=0:FC=0:RI=0:CJ=CT(T) 2510 FOR I=1 TO M 2520 IF FR=1 THEN GOTO 2530 IF IX(I,CJ)=0 THEN GOTO 2540 IF IU(I)=I THEN GOTO 2550 IF MM(I,CJ)=0 THEN GOTO 2560 IF TR(I) AND IP=0 THEN IP=1 :GOTO 257B FR=1:RI=I:IU(I)=1:I=M 2580 NEXT I 2590 IF RI0 THEN GOTO 2600 IF IP>0 THEN IP= 2610 D(RT(T),CT(T)=0:T=T- 2620 GOTO 2700 T=T-1:IP= 2710 RT(T)=RI:CT(T)=CJ 2720 D(RT(T),CT(T)=0:MM(RI,CJ)= 2721 PRINT T,RI;CJ 2730 GOTO 3000 W=1E10:L=0:KK= 3010 FOR I=2 TO T STEP 3020 IF X(RT(I),CR(I))>W THEN GOTO 3030 W=X(RT(I),CT(I)):KK=RT(I):LL=CT(I) 3040 NEXT I 3100 FOR I=1 TO Т 3110 X(RT(I),CT(I))=X(RT(I),CT(I))+W*D(RT(I),CT(I) 3120 NEXT I 3200 IX(K,L)=1:IX(KK,LL)= 3210 TR(K)=TR(K)+1:TR(KK)=TR(KK)- 3220 TC(L)=TC(L)+1:TC(LL)=TC(LL)- 3221 PRINT "W="W;: PRINT"KK="KK;:PRINT"LL="LL 3222 PRINT "ПPEOБPA3ОBAHИE ЗАКОНЧЕНО УСПЕШНО" 3250 GOTO 4000 PRINT "OKOHЧATEЛЬHOE РЕШЕНИЕ" 4010 GOSUB 4500 END 5000 СС= 5010 PRINT " I J XIJ CIJ СТОИМОСТЬ" 5020 FOR I=1 TO M 5030 FOR J=1 TO N 5040 IF IX(I,J)=0 THEN GOTO 5058 PP=C(I,J)*X(I,J) 5060 CC=CC+PP 5070 PRINT I;J;

5080 РВ=430:PA=X(I,J):GOSUB 5090 PA=C(I,J):GOSUB 9000:PA=PP:GOSUB 5100 PRINT "" 5110 NEXT J:NEXT I 5200 PRINT "СТОИМОСТЬ РАВНА ";CC 5250 RETURN 9000 PC=INT(PB/100) 9010 P$=" 9020 IF PC=0 THEN PRINT"": GOTO 9030 PRINT LEFT$(P$,PC);

9040 PC=PB-100*PC 9050 PD=INT(PC/10):PC=PC-10*PD 9060 IF PD=0 THEN PD=l 9070 IF PA=10^PD THEN PRINT PA;:RETURN 9110 P$=P$+MID$(STR$(INT(PE)),2,PD) 9120 PRINT RIGHT$(P$,PD+1) 9130 IF PC=0 THEN RETURN 9140 PRINT".";

9150 PE=INT((PE-INT(PE))*10^PC) 9160 P$="000000000" 9170 P$=P$+MID$(STR$(PE),2,PC) 9180 PRINT RIGHT$(P$,PC);:RETURN 0000 DATA 3,5 10010 DATA 1,0,3,4, 10020 DATA 5,1,2,3, 10030 DATA 4,8.1,4, 10040 DATA 15,25, 10050 DATA 20,12,5,8, READY.

РЕШЕНИЕ ТРAНСПОРТНОЙ ЗAДAЧИ

ДОПОЛНИТЕЛЬНЬЕ СТОИМОСТИ

C'KL=-3 К= 2 L=

СТОИМОСТЬ

I J XI CIJ

ОБШAЯ СТОИМОСТЬ РAВНA W= 12 KK= 1 LL=

ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО

ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ

C'KL=-l К= 3 L=

СТОИМОСТЬ

I J XIJ CIJ

ОБЩАЯМ СТОИМОСТЬ РАВНА W= 5 КК= 2 LL=

ПРЕОБРАЗОВАНИЕ ЗАКОНЧЕНО УСПЕШНО

ДОПОЛНИТЕЛЬНЫЕ СТОИМОСТИ

I J XIJ CIJ СТОИМОСТЬ

ОБЩАЯ СТОИМОСТЬ РАВНА 4.5. УПРАЖНЕНИЯ 1. Решите следующую транспортную задачу:

2. Решите следующую транспортную задачу:

3. Сталеплавильная компания располагает тремя заводами М1, М2, М3, способными произвести за некоторый промежуток времени 50, 30 и 20 тыс. т стали соответственно. Свою продукцию компания поставляет четырем потребителям С1, С2, С3 и С4, потребности которых составляют соответственно 12, 15, 25 и 36 тыс. т стали. Стоимости производства и транспортировки 1 тыс. т стали с различных заводов различным потребителям приведены ниже:

Определите минимальные общую стоимость, объемы производства на каждом заводе и планы перевозок.

4. Компания запланировала перемещения многих служащих на новые должности в соответствии с пересмотренным штатным расписанием. Служащие, которых эта реформа затрагивает, могут быть по квалификации и опыту разделены на пять групп S1, S2, S3, S4 и S5, содержащих соответственно 2, 5, 4, 8 и 6 служащих. Аналогичным образом каждую должность можно отнести к одной из следующих четырех групп: Р1, Р2, Р3 и Р4 - по 8, 3, 9 и должностей соответственно. В приведенной ниже таблице указывается, какие группы служащих обладают достаточной квалификацией для занятия соответствующих должностей:

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

5. Компания контролирует три фабрики F1, F2, и F3, способные произвести 50, 25 и 25 тыс.

изделий еженедельно. Она заключила договоры с четырьмя заказчиками С1, С2, С3 и С4, которым требуется еженедельно 15, 20, 20 и 30 тыс. изделий. Стоимости производства и транспортировки 1 тыс. изделий заказчикам с фабрик приведены ниже:

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

6. Компания владеет двумя фабриками F1 и F2, производящими электронное оборудование.

Фабрики в течение некоторого периода выпускает 16 и 12 тыс. изделий соответственно при нормальных темпах производства. При сверхурочной работе эти показатели могут быть повышены соответственно до 20 и 14 тыс. изделий. Дополнительная стоимость производства 1000 изделий в сверхурочное время на F1 и на F2 составляет 8 единиц. Компания снабжает трех потребителей С1, С2 и С3, потребности которых в течение одного и того же периода составляют соответственно 10, 13 и 7 тыс. изделий. Стоимости перевозок 1 тыс. изделий потребителю с фабрик приведены в таблице:

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

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

Авиалиния Сидней Калькутта Бейрут Даллас Сан-Паулу Администрация фирмы решила, что индивидуальные контракты на перевозку будут заключаться с владельцами авиалинии I, II, III в отношении 2:3:2, и уведомила об этом управляющего транспортными перевозками, а также известила его о том, что из намеченных на следующий год перевозок 10 - в Сидней, 15 - в Калькутту, 20 - в Бейрут, 10 в Даллас и 15 - в Сан-Паулу.

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

8. Четыре сталелитейных завода I, II, III и IV производят еженедельно соответственно 950, 300, 1350 и 450 т стали определенного сорта. Стальные болванки должны быть переданы потребителям А, В, С, D, Е, еженедельные запросы которых составляют соответственно 250, 1000, 700, 650 и 450 т стали.

Стоимость транспортировки от заводов к потребителям в тоннах приведена в таблице:

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

9. Некоторый продукт производится на двух заводах и распределяется между двумя пользователями. Их потребности на ближайшие два месяца приведены в таблице:

Стоимость транспортировки продукта с заводов потребителям приведена в таблице:

Стоимость производства единицы продукта и объем производства по плану за два месяца приведены в таблице:

При этом возможно производить продукт в течение месяца, хранить его лишь в течение месяца, а затем отправлять пользователю. Стоимость хранения составляет 0,5 на заводе 1 и 0,6 на заводе 2.

Требуются оптимальные планы производства и распределения. Сформулируйте задачу как транспортную и найдите оптимальное решение. 10. Компания владеет тремя заводами А, В, С. Соответствующие стоимости производства равны 26, 23 и 22 на единицу, объем производства 6000, 3000 и 3000 единиц. Компания обязалась поставлять соответственно 1500, 2500, 2700 и 3300 единиц в города W, X, Y, Z. При заданных стоимостях перевозок составьте оптимальные планы производства и распределения.

11. Решите задачи, приведенные в этой главе, и задачи приведенные в упражнениях, с помощью симплекс-метода. Как эффективнее решить эти задачи на ЭВМ - симплексметодом или как транспортные задачи?

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

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

Решите с помощью полученной программы задачи этой главы и задачи из упражнений.

Заметны ли выигрыш или потеря эффективности?

ГЛАВА 5 ЗАДАЧА О НАЗНАЧЕНИЯХ

5.1. ВВЕДЕНИЕ Пример Пять человек с номерами М1,М2,….М5 способны выполнить пять заданий с номерами Т1,Т2,…Т5. В силу разной квалификации на выполнение этих заданий им потребуется различное время. Как следует распределить людей по заданиям, чтобы минимизировать время выполнения? Время выполнения (в часах) приведено в таблице Пусть хij— время участия i-го человека в выполнении j-го задания. Все величины хij— неотрицательны, и, поскольку каждый человек должен быть полностью задействован, а каждое задание полностью выполнено, величина xij должна удовлетворять следующим ограничениям:

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

С другой стороны, в матрице времени размерностью 5*5 надо найти пять элементов — по одному в каждой строке и каждом столбце, таких, что сумма выбранных элементов минимальна. Условие равенства хij 0 или 1 в некоторых случаях необходимо, чтобы придать смысл формулировке задачи (см., например, первую фразу рассматриваемого примера). Это постулат.

Задача может быть обобщена для матриц размерностью п*п. Для каждой такой матрицы задача состоит в выборе п элементов — по одному в каждой строке и по одному в каждом столбце, таких, что их сумма минимальна. Обозначим выбранные элементы х1j, х2j, …., хnt, где i, j, t -некоторая перестановка элементов 1, 2,..., п. Таких перестановок - n!, так что даже при минимальном количестве п решение полным перебором является недопустимо длинным.

Эту задачу называют также задачей выбора. — Прим. ред.

5.2. МЕТОД РЕШЕНИЯ МАКА До настоящего момента было предложено два метода решения задачи о назначениях. Оба метода основаны на том факте что положения оптимального выбора не меняются, если к каждому элементу некоторой строки или столбца добавить одно и то же значение или вычесть его.

Венгерский метод основан на некоторых довольно трудных и нетривиальных комбинаторных свойствах матриц. Его довольно трудно программировать; поэтому сообщим лишь о том, что описание соответствующей процедуры можно найти во многих монографиях по исследованию операций и по математическому программированию.

Метод Мака имеет преимущество более простого интуитивного обоснования. Это — логический процесс. Сначала опишем шаги этого итеративного процесса,, а программу для ЭВМ приведем в разд. 5.3. Этот метод основан на идее выбора в каждой строке минимального элемента. Вообще говоря, минимальные элементы строк не распределены по всем п столбцам матрицы. Здесь используется идея сложения (или вычитания) одного и того же значения со всеми элементами строки или столбца, чтобы распределить минимальные элементы строк по столбцам (тогда они образуют оптимальный выбор). Метод Мака для задачи выбора Основатель метода К. Мак очень хорошо описал его в [15].

Рассматривается задача выбора размерностью п*п.

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

Начало Разделим множество столбцов на два множества А и А', А - выбранное множество, А' — невыбранное множество. В начале (и при последующих возвращениях к Началу) выбранных столбцов нет, так что множество А пусто, а множество А' содержит все столбцы.

Шаг 1. Выбрать из множества А' столбец, содержащий более одного подчеркнутого элемента. Перевести этот столбец из множества А' в множество А.

Шаг 2. Пусть элемент множества А из строки i равен bj, а минимальный элемент множества А' из строки i равен аi. Пусть Шаг 3. Увеличить все элементы множества А на а/r-br.

Шаг 4. Отметить а/r точками внизу. Теперь а/r - "отмеченный точками элемент".

Шаг 5. Пусть С - столбец, содержащий а/r. Если в С более двух подчеркнутых элементов, перевести С из множества А' в множество А и перейти к шагу 2. В противном случае перейти к следующему шагу.

Теперь можно подчеркнуть элементы в еще одном столбце.

Шаг 6. Подчеркнуть последний элемент а/r полностью. Это — новый подчеркнутый элемент.

Шаг 7. Найти исходный подчеркнутый элемент в той же строке, что а/r. Убрать подчеркивание. Обозначить столбец, в котором находится этот элемент, D.

Шаг 8. Если D не содержит других элементов, он должен содержать элемент, отмеченный точками. Обозначить этот элемент а/r и вернуться к шагу 6.

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

Если остался еще столбец без подчеркнутых элементов, вернуться к Началу.

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

Элементы, соответствующие оптимальному выбору, могут быть отмечены, и может быть вычислена соответствующая стоимость.

Вычисления могут быть сокращены, если на шаге 3 увеличить на а/r - в/r только подчеркнутые элементы множества А, отложив до шага 8 увеличение остальных элементов множества А. В этом случае все оставшиеся элементы столбца увеличиваются на то же значение, на которое увеличились подчеркнутые элементы.

Ниже приводится полное описание этого метода для решения примера 1 разд. 5.1.

Начало Шаг 1. Столбец 2 переходит в множество А Шаг 2 Строка 1: подчеркнут элемент 5, минимум найден в точке А' = 9, 10 5 9 разность равна 4. Строка 3: подчеркнут элемент 2, минимум найден в 13 19 6 точке А' = 3, разность равна 1. Строка 4: подчеркнут элемент 9, минимум найден в точке А' = 12, разность равна 3. Строка 5: подчеркнут элемент 6 3 2 4 минимум найден в точке А' = 10, разность равна 4. Минимум (а/r -вi) равен 1 в строке Шаг 4. Подчеркнуть штрихом элемент 3 в строке 3, столбце Шаг 5. С (столбец 1) не содержит подчеркиваний, так что перейти к 10 6 9 Шаг 6. Полностью подчеркнуть элемент 3 в строке 3 столбца Шаг 7. Убрать подчеркивание элемента 3 в строке 3 столбца Шаг 8. D (столбец 2) содержит другие подчеркнутые элементы, поэтому 18 10 12 следует вернуться к началу, так как имеются столбцы без подчеркнутых Начало Шаг 2. Min (а/r - вi) =12-10=2 в строке Шаг 3. Увеличить на 2 все элементы в столбце Шаг 4. Отметить точками элемент 12 в строке 4 столбца Шаг 5. С (столбец 3) содержит другой подчеркнутый элемент, так что перевести столбец 3 в множество А и перейти к шагу Шаг 2. Множество А состоит теперь из столбцов 2 и 3 Минимум а i -вi 11 9 14 равен 10-9=1 в строке Шаг 3. Увеличить все элементы в столбцах 2 и 3 на Шаг 5. С (столбец 5) не содержит других подчеркнутых элементов, так что Шаг 6. Полностью подчеркнуть элемент 10 в строке 5 столбца Шаг 7. Убрать подчеркивание элемента 10 в строке 5 столбца Шаг 8. D (столбец 2) содержит другие подчеркнутые элементы, так что 11 10 15 перейти к началу, так как в столбце 4 нет подчеркнутых элементов Шаг 2. Минимум (а/i -вi) равен 13-13= Шаг 3. Ничего не меняется Шаг 4. Отметить точками элемент 13 в строке 4 столбца Шаг 5. С - это столбец 3; содержит подчеркнутый элемент, перейти к 11 10 15 следующему шагу Шаг 2. Столбец 2 и столбец 3 содержатся в множестве A; Min(а/i -вi) равен 10 10 11 10-9= Шаг 4. Отметить тремя точками снизу элемент 10 в строке 1 столбца Шаг 5. С (столбец 1) содержит другой подчеркнутый элемент, так что Шаг 2. А — это столбцы 1, 2 и 3; Min(а i -вi) равен 11-10=4-3=15-14=1 11 11 16 Шаг 5. С (столбец 4) не содержит подчеркнутых элементов, так что перейти к следующему шагу Шаг 6. Полностью подчеркнуть элемент 4 в строке 3 столбца 4 19 15 15 Шаг 8. D (столбец 1) содержит подчеркнутый элемент в строке 1, так что перейти к следующему шагу Шаг 7. Снять подчеркивание элемента 11 в строке 1 столбца 2 19 15 15 Шаг 8. D (столбец 2) содержит другой подчеркнутый элемент, новое 12 12 17 множество подчеркнутых элементов приведено ниже Теперь в каждом столбце находится ровно по одному подчеркнутому элементу, так что окончательное решение найдено Человек № 1 выполняет задание № 1, человек № 2 - задание № 3, человек № 3 - задание № 4, человек № 4 - задание № 2, человек № 5 - задание № В исходном массиве назначения и времена следующие:

Минимальное время составляет 39 чел-ч.

Пример Ежедневно авиалиния, которая принадлежит некоторой компании, осуществляет следующие перелеты между городами Х и Y:

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

Используйте технику решения задачи выбора.

Напишите расписание полетов, совершаемых каждым из самолетов.

Представьте найденное решение в виде диаграммы. Сколько самолетов требуется для полетов по составленному расписанию? Время простоя в каждом случае приведено в таблице.

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

Расписание полетов в город Х: 115, 123, 134,144,152.

Расписание полетов в город Y: 115, 213, 314, 411, 512. Так что последовательность в целом имеет следующий вид:

1152134115123141 и т. д.

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

5.3. РЕАЛИЗАЦИЯ МЕТОДА МАКА НА ЭВМ Программа для ЭВМ следует только что описанному итерационному процессу, но, разумеется, не буквально — с помощью ЭВМ нельзя подчеркнуть переменную. Программа нетривиальна и заслуживает внимательного изучения. Она написана так, чтобы по желанию минимизировать или максимизировать функцию. Матрица R сохраняется. Рабочая матрица Р(= ± R, + min., -max.) меняется в процессе вычисления.

В строках 250—310 программы минимальным элементом строки I является IM из столбца L.

В строках 320-360 пусть NM(L) - количество минимумов в столбце L, MA(I) - значение минимума в 1-й строке, 1С (L, К) — строка К-го минимума в столбце L, JR (I) — столбец МА (I) из строки I. Началу и шагу 1 соответствуют строки программы 400-470, где находится столбец с двумя и более минимумами; строки, в которых находятся эти минимумы, запоминаются в переменных 1Р(1), 1Р(2) и т. д. В строке 480 NC - количество столбцов, в которых производились одновременные увеличения (в начале NC = 1); LR(1), LR(2) и т. д. список номеров столбцов из множества A, a JK(J) для таких столбцов равна 1; MB(J) значение, на которое увеличены элементы столбца J.

Шаг 2 — строки программы 520—640; IZ — разность между элементом в строке 1(=1Р(К)) столбца JD и минимумом в строке I. Столбцы множества А, для которых JK(JD) = 1, исключаются. Наименьшее значение IZ присваивается IV, и это - наименьшее значение, нужное для соответствия одному из минимумов по строкам в множестве A; JC - столбец соответствующего элемента, a IR — номер его строки, MB (LR(JX)) — общее значение, на которое увеличиваются элементы в столбце LR(JX) (строки 650—670). В данный момент на IV увеличиваются только значения минимумов в строке IP (К). Это — модифицированный шаг 3 (680—700).

В строке 720 столбец JC добавляется к множеству А, т. е. LR(1), LR(2),..., LR(NC) и LR(NC + 1) полагаются равными JC. В строке 750 IM(JC) указывает строку минимума в столбце JC, a JM(IR) - столбец минимума в строке IR(=IM (JC)). Строка 770: в столбце JC имеется JY минимумов. Если в столбце JC нет минимумов, минимумы в строке располагаются так, чтобы покрыть один лишний столбец (переход от строки 780 к строке 840). В противном случае эти минимумы прибавляются к JU минимумам из предыдущих столбцов, JU соответственно увеличивается, а строки минимумов из IC(JC, JX) запоминаются в IP(JU).

Это — шаг 5, и в строке программы 520 происходит возвращение к шагу 2.

Если после шага 5 осуществляется переход к строке 840, то необходимо переместить минимум (шаг 6). В строке 850 программы LS = LR(JX) представляет собой столбец с номером JX матрицы А. Вновь обнуляем JK, т. е. исключаем его из множества А. Элемент MB (LS) является тем значением, на которое был номинально увеличен столбец LS. Теперь все элементы столбца LS фактически увеличены на это значение (строка 880 программы).

В строке 910 программы находится один минимум в столбце JC. Новый минимум находится в строке IP столбца JC (шаг 6); JP = JP(IR) в строке 930 — столбец предыдущего минимума в строке IR, так что в строке 940 полагаем JR(IR) = JC. Количество минимумов в этом столбце JQ = NM (JP), где JP равно исходному значению JR (IR). В строках 970-1020 программы определяется, какой из минимумов столбца JP находится в строке JR. Он исключается или заменяется. В строке 1030 программы происходит следующее: если в столбце JP находится более одного минимума, перераспределение минимумов закончено, NM(JP) приравнивается 1, управление возвращается к строке 400 (старт) для нахождения столбцов с более чем одним минимумом. Если программа дойдет до строки 1040, то в столбце JP будет найден всего один минимум;

IM(JP) - номер его строки, так что новое значение JC равно JP, a JC(JP, JQ) (строка одного минимума в столбце JP) и есть новое значение IR. Таким образом, процесс повторяется с новым столбцом JP в строке 930 программы.

В строку 1500 управление передается из строки 420, где обнаруживается отсутствие столбцов с более чем одним минимумом. Теперь минимумы в строках распределены по столбцам, и оптимальный выбор найден. Строка первого (и единственного) минимума в столбце J есть 1С (см. строку 1520), так что оптимальные выборы извлекаются из элементов строки I столбца JV(I) (см. строку 1550). Они распечатываются, и оптимальная сумма заносится в Т.

Пример Для матрицы найдите 1) минимальный; 2) максимальный выбор. Данные в строке 2000 пригодны для случая 1). Распечатка результатов в обоих случаях следующая:

READY.

20 PRINT-РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИИ МЕТОДОМ МДКЙ

30 READ N:REM N-РАЗМЕРНОСТЬ МАТРИЦЫ

40 REflD MZ: REM ЕСЛИ MZ=+1,TO В ЗАДАЧЕ ИЩЕТСЯ МАКСИМУМ;

45 REM ЕСЛИ MZ=-l.TO В ЗАДАЧЕ ИЩЕТСЯ МИНИМУМ

50 REM ЗАДАТЬ МЙССИВЫ.ПОДРОБНОСТИ ОПИСАНЫ В ТЕКСТЕ КНИГИ

70 DIM R(N,N),P(N,N),IC(N,N) 80 DIM MA(N), IP(N),MB(N),JV(N),LR(N) 90 DIMJR(N),JU(N),IU(N),JK(N),NM(N)

95 REM ВВЕСТИ МАТРИЦУ В МАССИВ R

100 FOR I=1 ТО N:FOR М TO N 110 READ R(I,J) 120 NEXT J:NEXT I

190 REM В ПРОГРАММЕ МИНИМИЗИРУЕТСЯ РАБОЧАЯ МАТРИЦА Р

200 FOR I=1 ТО N:NM(I) 210 FOR J=1 TO N:P(I,J)=-MZ+R(I,J) 220 NEXT J:NEXT I 230 M-1E10:REM ЗНАЧЕНИЕ М БОДЬЕ ЛЮБОГО ЭЛЕМЕНТА МАТРИЦЫ R 250 FOR I=1 ТО N:IM=M 270 FOR J=1 ТО N 280 IZ=P(l.J) 290 IF IZ>IM THEN GOTO 300 IM=IZ:L=J 310 NEXT J 320 NM(L)=NM(L)+1:K=NM(L) 330 IC(L,K)=I 340 MA(I)-IM 350 JR(I)=L 360 NEXT I 400 J= 410 J=J+ 420 IF J>N THEN GOTO 430 IF NM(J)IV THEN GOTO 590 IV=IZ 600 JC=JD 610 IR=I 630 NEXT JD 640 NEXT К 650 FOR JX=1l TO NC 660 MB(LR(JX))=MB(LR(JX))+IV 670 NEXT JX 680 FOR K=1 TO JW 690 MA(IP(K))=MA(IP(K))+IV 700 NEXT К 710 МВ(JC)= 720 JK(JC)= 730 NC=NC+ 740 LR(NC)=JC 750 IM(JC)=IR 760 JM(JR)=JC 770 JY=NM(JC) 780 IF JY=0 THEN GOTO 790 FOR JX=1 TO JY 800 JU=JU+ 810 IP(JU)=IC(JC,JX) 820 NEXT JX 830 GOTO 840 FOR JX=1 TO NC 850 LS=LR(JX) 860 JK(LS)= 870 FOR I=1 TO N 880 P(I,LS)=P(I,LS)+MB(LS) 890 NEXT I 900 NEXT JX 910 NM(JC)= 920 IC(JC,1)=IR 930 JP=JR(lR) 940 JR(IR)=JC 950 IW= 960 JQ=NM(JP) 970 FOR IL=1TO 980 IZ=IC(JP,IL) 990 IF IZ=IR THEN GOTO 1000 IW=IW+ 1010 IC(JP,IW)=IC(JP,IL) 1020 NEXT IL 1030 IF JQ>1 THEN GOTO 1040 IR=IM(JP) 1050 JC=JP 1060 IC(JP,JQ)=IR 1070 GOTO 1080 NM(JP)=JQ- 1090 GOTO 1500 T=0:PRINT " I J R(I,J)" 1510 FOR J=1 TO N 1520 JV(IC(J,1))=J 1530 NEXT J 1540 FOR I=1 TO N 1550 J=JV(I) 1560 T=T+R(I,J) 1570 PRINT I;,R(I,J) 1580 NEXT I 1600 IF MZ=1 THEN PRINT "Максимум равен";Т 1610 IF MZ=1 THEN РRINT "Минимум равен";Т 1700 END 2000 DATA 8,- 2010 DATA 93,93,91 94,99 99,90, 2020 DATA 96,93,90 94,98 96,97, 2030 DATA 96,90,91 90,92 90,93, 2040 DATA 93,94,95 96,97 10,92, 2050 DATA 94,93,95 91,90 97,96, 2060 DATA 94,93,96 90,93 89,88, 2070 DATA 94,96,91 90,95 93.92, 2080 DATA 93,94,6,95,91,99,91, READY.

РЕШЕНИЕ ЗАДАЧИ 0 НАЗНАЧЕНИИ МЕТОДОМ МАКА

МИНИМУМ PАBEH 558 РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИИ МЕТОДОМ МАКА

86 99 МАКСИМУМ РАВЕН 5.4. УПРАЖНЕНИЯ 1) Решите задачи методом минимального выбора:

2) Решите задачи минимального выбора 3) В определенный день компания по перевозке грузов должна забрать пять грузов в точках А, В, С, D, Е и доставить их в пункты а, b, с, d, e. Расстояния (в милях) между точками загрузки и пунктами назначений грузов приведены ниже:

Фирма располагает пятью грузовиками двух типов Х и Y в точках S, Т, U, V, W; типы грузовиков: Х в S, Y в Т, Х в U, Х в V и Y в W. Грузовики типа Х новее и экономичнее грузовиков типа Y, и стоимости перевозки на них ниже. Стоимости пробега одной мили (в центах) для грузовиков обоих типов (включающие горючее, страховку, поддержку оборудования и т. д.) приведены ниже:

Как следует группе распределить время (по 2 2 дня) по пяти городам, чтобы максимизировать ожидаемое количество успешных опросов?

6. Авиалиния связывает три города А, В, С. Полеты происходят днем семь дней в неделю.

Стоимость стоянки самолетов во всех трех аэропортах составляет kT2, где Т - время стоянки.

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

7. Используйте метод Мака для решения задачи выбора, в которой должно быть минимизировано суммарное время выполнения всех заданий.

8. Компания реализует продукцию в пяти географических областях. Покупательные способности жителей этих областей оцениваются следующим образом:

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

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

9. Решите задачи настоящей главы и задачи, приведенные в упражнениях, используя программу решения транспортной задачи. Заметна ли потеря эффективности по сравнению с методом Мака?

10. Решите задачи настоящей главы и задачи, приведенные в упражнениях, используя программу, реализующую симплекс-метод. Заметна ли потеря эффективности по сравнению с методом Мака?

ГЛАВА 6 УЛУЧШЕННЫЙ СИМПЛЕКС-МЕТОД

6.1. УЛУЧШЕННЫЙ СИМПЛЕКС-АЛГОРИТМ Симплекс-метод решения задач линейного программирования — не очень эффективная в вычислительном отношении процедура. Преобразования из одной канонической формы в другую производятся во всех столбцах коэффициентов. Однако, если переменная хk в продолжение всех вычислений не входит в базис, преобразования соответствующего ей столбца бессмысленны. Разумеется, заранее не известно, какие переменные в процессе вычислений станут базисными.

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

Рассмотрим для начала случай, в котором в задачу входят ограничения в виде неравенств со знаком =MIN THEN GOTO 560 MIN =C(J):S=J 570 NEXT J

580 REM ЕСЛИ S=0, TO ВСЕ КОЭФФИЦИЕНТЫ ПОЛОЖИТЕЛЬНЫ И

585 REM МИНИМУМ НAЙДЕН 590 IF S=0 THEN GOTO

740 REM НAЙТИ СТРОКУ ПЕРЕМЕННЫХ, КОТОРУЮ СЛЕДУЕТ

745 REM ИСКЛЮЧИТЬ ИЗ БАЗИСА ПО УСЛОВИЮ МИНИМУМА BI/А'(IS)

750 MIN =1E20:R= 755 REM ВЫЧИСЛИТЬ А'(IS) И ПОМЕСТИТЬ В СТОЛБЕЦ V 760 FOR I=1 ТО М1:V(I)= 770 FOR K=1 TO M1:V(I)=V(I)+B(I,K)*A(K,S):NEXT K:NEXT I 780 V(ML)=C(S) 790 FOR I=1 ТО М 800 IFV(I)=0 THEN GOTO 850 R=I:MIN=B(I,0)/V(I) 860 GOTO 870 IF DF0 THEN GOTO 880 K=K+ 890 MIN=B(R,K)/V(R) 900 GOTO 1000 NEXT I

1010 REM ЕСЛИ R=0, TO ИМЕЕТ МЕСТО РЕШЕНИЕ БЕЗ ОГРАНИЧЕНИЙ

1020 IF R=0 THEN GOTO 1050 IF ZZ>=0 THEN GOSUB

1100 REM ОБНОВИТЬ ОБРAТНЫЙ И СИМПЛЕКС- МНОЖИТЕЛИ

1120 PV=V(R) 1130 FOR J=0 TO M1:B(R,J)=B(RJ)/PV:NEXT J

1180 REM ПЕРЕНАЗНАЧИТЬ В ПОВТОРНО ПОМЕТИТЬ БАЗИСНЫЕ

1185 REM И НЕБАЗИСНЬЕ ПЕРЕМЕННЫЕ 1190 NB(BS(R))=0:NB(S)=1:BS(R)=S:NI=NI+ 1200 GOTO 1800 РRINT "ПЕРЕМЕННAЯ "S" HE ИМЕЕТ ОГРAНИЧЕНИЙ 1810 GOSUB 3500:STOP 1820 GOTO 1900 IF L=0 THEN GOTO

1905 REM ДЛЯ ЭТАПА 2 ЭТА ТОЧКA ЯВЛЯЕТСЯ ТОЧКОЙ МИНИМУМА. ЕСЛИ

1908 REM МЫ НAХОДИМСЯ НA ЭТАПЕ 1, ТО ПЕРЕЙТИ К ЭТАПУ 1910 REM ПРОВЕРИТЬ,ЧТО W СТАЛО РАВНО 1920 IF ABS(B(ML,0))>=1E-08 THEN GOTO 1930 PRINT "ЭТАП 1 УСПЕШНО ЗАВЕРШЕН" 1940 L=0:N0=N1:REM ЗАДАТЬ L И НОМЕР СТОЛБЦА ДЛЯ ЭТАПА 1950 GOTO

1960 РRINT "ОГРАНИЧЕНИЯ НЕ ИМЕЮТ ДОПУСТИМОГО РЕШЕНИЯ"

1970 PRINT "СУММA ИСКУССТВЕННЫХ ПЕРЕМЕННЫХ PABHA";:PRINT -B(ML,0) 1980 GOSUB 3500:STOP 2000 PRINT"OKOH4ATEAbHOE РЕШЕНИЕ" 2010 PRINT "ОГРAНИЧЕНИЕ БАЗИС ЗНАЧЕНИЕ" 2020 РВ= 2030 FOR I=1 ТО M:SL(BS(I))=B(I,0) 2040 PRINT " ",I," ";BS(I);

2050 PA=B(I,0):GOSUB 9000:PRINT "" 2060 NEXT I 2090 PRINT "MИHИMУM ФУНКЦИИ Z РФВЕН ";-В(М1,0)

2100 РRINT "ОГРАНИЧЕНИЕ СОСТОЯНИЕ ДОПОЛНИТЕЛЬНЫЫЕ ПЕРЕМЕННЫЕ"

2120 FOR I=1 ТО М 2130 PRINT " ";I, " ";

2140 IF IMM THEN GOTO 2150 PRINT "УPABHEHИE HE РЕШЕНО":GOTO 2160 IF NB(N+I)=1 THEN РRINT "ДОПОЛ.ПЕРЕМ";

2165 PA=SL(N+I):GOSUB 9000:PRINT " ":GOTO 2170 РRINT "ОГРАНИЧЕНИЕ 0" 2180 NEXT I 2300 SS=1:GOSUB 2500 END 3000 РRINT "БАЗИС ЗНАЧЕНИЕ";

3010 FOR J=1 TO N:PRINT " X J ";:NEXT J 3020 PRINT "" 3030 PB= 3040 FOR I=1 TO ML 3050 IF I=M1 THEN PRINT "ЦЕЛЕВАЯ ФУНКЦИЯ";: GOTO 3060 IF I=M2 THEN РRINT "ИСКУССТ.ФУНКЦИЯ";: GОТО 3070 PRINT I;:PA=A(I,0):GOSUB 3080 FOR J=0 TO N 3090 РA=A(I,J):GOSUB 3100 NEXT J 3110 PRINT "" 3120 NEXT I:PRINT" " 3200 RETURN 3500 IF L=1 THEN РRINT "ПЕРВЫЙ ЭТАП ВСЕ ЕЩЕ ПРОДОЛЖАЕТСЯ" 3510 РВ= 3520 FOR J=1 ТО N0:PRINT " C"J" ";:NEXT J 3530 PRINT" " 3540 FOR J=1 TO N0:PA=C(J):GOSUB 9000:NEXT J: PRINT" " 3550 IF SS=1 THEN GOTO 3560 PRINT "X";S; "ВВОДИТ B,X",BS(R);"B УСЛОВИИ";R;"ВЫВЕДЕН ИЗ БАЗИСА" 3600 PRINT "БА3ИC ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА";:IF SS=1 THEN PRINT" " 3605 GOTO 3610 PRINT " A' lS" 3620 FOR I=1 TO ML 3630 IF I=M1 THEN PRINT "PEШEHИE ДЛЯ ЦЕЛЕВОЙ ФУНКЦИИ";: GOTO 3640 IF I=M2 THEN PRINT "РЕШЕНИЕ ДЛЯ ИСКУССТ.ФУНКЦИИ";:GOTO 3650 PRINT BS(I);

3670 FOR J=0 ТО М 3680 РA=В(I,J):GOSUB 3690 NEXT J 3700 IF SS=1 THEN GOTO 3710 PA=V(I):GOSUB 3720 PRINT"" 3730 NEXT I:PRINT" " 3750 RETURN 4000 DATA 4010 DATA 0,0,3, 4020 DATA 0.25,-8,-1,9,0.5,-12,-0.5,3,0,0,1,0,-0.75,20,-0.5, 4030 DATA 0,0, 9000 PC=INT(PB/100) 9010 Р$=" 9020 IF PC=0 THEN PRINT"":GOTO 9030 PRINT LEFT$(P$,PC);

9040 PC=PB-100*PC 9050 P0=INT(PC/10):PC=PC-10*PD 9060 IF PD=0 THEN PD= 9070 IF PA=10^PD THEN PRINT PA;:RETURN 9110 P$=P$+MID$(STR$(INT(PE)),2,PD) 9120 PRINT RIGHT$(P$,PD+1) 9130 IF PC=0 THEN RETURN 9140 PRINT".";

9150 PE=INT((PE-INT(PE))*10^'PC) 9160 P$=" 000000000" 9170 P$=P$+MID$(STR$(PE),2,PC) 9180 PRINT RIGHT$(P$,PC);:RETURN READY.

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

МОДИФИЦИРОВАННЫМ СИМПЛЕКС-МЕТОДОМ

ОТСУТСТВУЕТ ЭТАП 1 РЕШЕНИЯ ЗАДАЧИ

ПЕРВОНАЧАЛЬНАЯ ТАБЛИЦА

Х3 ВХОДИТ В, Х4 В УСЛОВИИ 1 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИ ОБРАЩЕНИЕ БАЗИСА A'lS

РЕШЕНИЕ ДЛЯ ЦЕЛЕВОЙ 0.00 0.00 0.00 0.00 -15.

ФУНКЦИИ

Х1 ВХОДИТ В Х6 В УСЛОВИИ 3 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'lS

ФУНКЦИИ

Х2 ВХОДИТ В Х5 В УСЛОВИИ 2 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'lS

ФУНКЦИИ

Х4 ВХОДИТ В Х3 В УСЛОВИИ 1 ВЫВЕДЕН ИЗ БАЗИСА

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА A'lS

ФУНКЦИИ

ОКОНЧАТЕЛЬНОЕ РЕШЕНИЕ

МИНИМУМ ФУНКЦИИ РАВЕН -

БАЗИС ЗНАЧЕНИЕ ОБРАЩЕНИЕ БАЗИСА

ФУНКЦИИ

6.5. УПРАЖНЕНИЯ 1. Используя улучшенный симплекс-метод, решите следующую задачу:

найти такие х1 0, х2 0, что и функция 2 х1 4 х2 = z принимает минимальное значение.

2. Используя улучшенный симплекс-метод, решите следующую задачу:

найти такие хi0, где i = 1, 2, что и функция 3 х1 + 4 х2 = z принимает максимальное значение.

3. Используя улучшенный симплекс-метод, решите следующую задачу:

найти такие х1 0, х2 0, что и функция 50 х1 + 25 х2 = z принимает минимальное значение.

4. Используя улучшенный симплекс-метод, решите следующую задачу:

найти такие y1 0, y2 0, y3 0, что и функция 8y1 + 19 y 2 + 7 y 3 = w принимает максимальное значение.

5. Воспользуйтесь улучшенным симплекс-методом для решения задачи Била:

найти такие х1 0, х2 0, х3 0, х4 0 что и функция 3 / 4 х1 + 20 х2 1 / 2 х3 + 6 х4 = z 1 принимает минимальное значение.

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

6. Компания производит различные виды мебели для кабинетов. Она производит столы трех типов (1, 2 и 3). Объем работы, необходимой для каждой операции, приводится в таблице Максимум объема работ в неделю составляет З60 чел.-ч. на изготовление частей стола, чел.-ч. на сборку и 180 чел.-ч. на полировку. Рынок сбыта расширяется, но он недолговечен, а возможности хранения ограничивают производство 170 столами в неделю.

Прибыль от продажи столов типов 1, 2 3 составляет соответственно 15, 22 и 19 дол.

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

найти такие хi 0, что и функция = 15 х1 22 х2 19 х3 принимает минимальное значение.

Объясните физический смысл всех переменных модели и, используя улучшенный симплексметод, произведите вычисления, необходимые для получения решения.

Решение задачи на ЭВМ было выдано в виде таблицы Ограничение базис Значение Обращение базиса Симплекс множители Используйте этот результат, чтобы построить полную симплекс-таблицу, соответствующую оптимальному решению.

Стоимость сверхурочных работ на каждом этапе производства составляет 4 дол. на 1 чел.-ч.

1. В каких производственных процессах целесообразно использовать сверхурочные работы?

2. В течение некоторого времени для удовлетворения потребностей ценного клиента необходимо увеличить выпуск столов типа 3 по крайней мере до 30 столов в неделю. Как это повлияет на оптимальный план производства?

7. Компания производит сверлильные станки трех видов D1, D2, D3. Каждый вид приносит соответственно 10, 10 и 30 дол. прибыли. Количество станков, которое может быть произведено в течение недели/ограничено поставками комплектующих изделий F1, F2; и F где для D1 требуется 1 штука F1, 4 штуки F2 и 2 штуки F3; для D2 - 2 штуки F1 3 штуки F2 и штуки F3, а для D3 - 10 штук F1, 10 штук F2 и 8 штук F3. Каждую неделю количество доступных изделий F1, F2; и F3 составляет соответственно 650, 850 и 650 штук. Определите максимальную прибыль, которую можно получать каждую неделю, и покажите, что выгоднее всего производить одинаковое количество станков D1, D2, D3. Компания обращается в комиссию по ценам за разрешением повысить цены до такой степени, чтобы они давали 20 %-ное увеличение прибылей от всех моделей. Рассмотрев вопрос, комиссия разрешает увеличение цен на станки D1 и D2, но настаивает на таком ограничении цены на станок D3, при котором прибыль от продажи станка D3 уменьшилась бы на 10 %. Покажите, что оптимальный план производства, основанный на этих данных о прибыли, приведет к %-ному увеличению общей прибыли.

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

Если возможности производства позволяют одному рабочему в течении недели произвести станок D1 или один станок D2, а пяти рабочим - один станок D3 то как это соглашение повлияет на новое решение? Покажите, что максимальное увеличение прибыли составляет 11 % от исходной прибыли. 8. Была предложена следующая простая модель сельскохозяйственного производства на Нарвских островах для внешнего рынка. Имеется три основные культуры, растущие в этом климате, и выращиваться они могут на одном из двух типов пахотных земель. В настоящее время для обработки пригодны 14 * 10 акров земли типа I и 12 * 10 акров земли типа II. Разные типы культур по-разному растут на разных землях, и подсчитано, что чистый урожай культуры i с земли типа j составляет Rij.

Все культуры требуют дополнительного орошения (ирригационного). Имеющаяся ирригационная система обеспечивает 56 * 10 м3 воды в год. Для одного акра культуры i, выращенной на земле типа j, требуется Wij м3 воды в год:

Население, занятое в сельском хозяйстве, составляет 7 * 10 человек. Чтобы получить урожаи 1, 2, 3 с каждых 10 акров земли, для выполнения различных работ по выращиванию культур в течение 1 года требуется соответственно 2, 1, 3 человека. Описанная модель приводит к следующей задаче линейного программирования:

пусть все переменные неотрицательны и удовлетворяют условиям Минимизируйте функцию R = -6 х11 8 х21 4 х31 6 х12 5 х22 5 х Объясните физический смысл всех переменных, входящих в задачу. Найдите базис, обращение базиса, симплекс-множители этого базиса, решите эту задачу улучшенным симплекс-методом.

Задача была решена на ЭВМ; решение было выдано в виде таблицы x x Значение целевой функции равно 152.

а) Прокомментируйте это решение.

б) Рассматриваются план вырубки лесов, реализация которого даст дополнительные земли типа I, и пути принципиального улучшения ирригационной системы. Каково значение этих перемен с точки зрения экономики сельского хозяйства?

в) Предложена четвертая культура, которая может выращиваться только на земле типа II.