Сформулируем алгоритм симплекс-метода применительно к данным, внесенным в табл. 7.12.
1. Выяснить, имеются ли в последней строке таблицы положительные числа (0не принимается во внимание). Если все числа отрицательны, то процесс закончен; базисное решение (b1, b2, ..., br, 0, ..., 0) является оптимальным; соответствующее значение целевой функцииf= 0. Если в последней строке имеются положительные числа, перейти к п. 2.
2. Просмотреть столбец, соответствующий положительному числу из последней строки, и выяснить, имеются ли в нем положительные числа. Если ни в одном из таких столбцов положительных чисел нет, то оптимального решения не существует. Если найден столбец, содержащий хотя бы один положительный элемент (если таких столбцов несколько, взять любой из них), пометить этот столбец и перейти к п. 3.
3. Разделить свободные члены на соответствующие положительные числа из выделенного столбца и выбрать наименьшее частное. Отметить строку таблицы, соответствующую наименьшему частному. Выделить разрешающий элемент, стоящий на пересечении отмеченных строки и столбца. Перейти к п. 4.
4. Разделить элементы выделенной строки исходной таблицы на разрешающий элемент (на месте разрешающего элемента появится единица). Полученная таким образом новая строка пишется на месте прежней в новой таблице. Перейти к п. 5.
5. Каждая следующая строка новой таблицы образуется сложением соответствующей строки исходной таблицы и строки, записанной в п. 4, которая предварительно умножается на такое число, чтобы в клетках выделенного столбца при сложении появились нули. На этом процесс заполнения новой таблицы заканчивается, и происходит переход к п. 1.
Таким образом, используя алгоритм симплекс-метода применительно к симплекс-таблице, мы можем найти оптимальное решение или показать, что его не существует. Результативность комплекс-метода гарантируется следующей теоремой (приведем ее без доказательства):если существует оптимальное решение задачи линейного программирования, то существует и базисное оптимальное решение. Это решение может быть получено через конечное число шагов симплекс-методом, причем начинать можно с любого исходного базиса.
Ранее мы предполагали, что если система ограничений задана в виде (7.85), то перед первым шагом она уже приведена к виду(7.86), где bi0 (I=1,2, …, r). Последнее условие необходимо для использования симплекс-метода. Рассмотрим вопрос об отыскании начального базиса.
Один из методов его получения – метод симплексного преобразования.
Прежде всего проверяем, есть ли среди свободных членов отрицательные. Если свободные члены не являются числами неотрицательными, то добиться их неотрицательности можно несколькими способами:
1) умножить уравнения, содержащие отрицательные свободные члены, на –1;
2) найти среди уравнений, содержащих отрицательные свободные члены, уравнение с максимальным по абсолютной величине отрицательным свободным членом и затем сложить это уравнение со всеми остальными, содержащими отрицательные свободные члены, предварительно умножив его на –1.
Затем, используя действия, аналогичные указанным в пп. 3-5 алгоритма симплекс-метода, совершаем преобразования исходной таблицы до тех пор, пока не получим неотрицательное базисное решение.
Пример 2.Найти исходное неотрицательное базисное решение системы ограничений.
Так как условие неотрицательности свободных членов соблюдается, приступим к преобразованиям исходной системы, записывая результаты в таблицу. Согласно алгоритму просматриваем первый столбец. В этом столбце имеется единственный положительный элемент а31. Делим на 8,654 все коэффициенты и свободный член третьей строки, после чего умножаем каждый коэффициент на 8,704 и складываем с соответствующими коэффициентами второй строки. Первая строка преобразований не требует, так как коэффициент при неизвестном x1равен нулю. В результате получаем
0,00000 -5,87100 6,54300 -9,99600 7,61800 0,86400
0,00000 0,68512 17,46384 8,57990 -3,19062 9,79929
1,00000 -0,77756 0,97677 0,89808 0,62769 1,11584
Продолжая просматривать второй столбец и совершая аналогичные преобразования, имеем
0,00000 0,00000 156,19554 63,52761 -19,72328 84,83688
0,00000 1,00000 25,49013 12,52318 -4,65701 14,30299
1,00000 0,00000 20,79687 10,63560 -2,99341 12,24727
И, наконец, на третьем шаге находим исходный базис. Его образуют неизвестные x1, х2, х3. Неизвестные х4, х5являются свободными:
0,00000 0,00000 1,00000 0,40672 -0,12627 0,54315
0,00000 1,00000 0,00000 2,15588 -1,43829 0,45815
1,00000 0,00000 0,00000 2,17713 -0,36733 0,95155
Контрольные вопросы и задания
1. Приведите примеры задач, приводящих к общей постановке задачи линейного программирования.
2. Сформулируйте задачу линейного программирования.
3. Сколько решений может иметь задача линейного программирования?
4. По каким причинам может отсутствовать решение задачи линейного программирования?
5. Каким образом неравенства из системы ограничений можно заменить уравнениями? Как задачу отыскания максимума линейной формы свести к задаче отыскания минимума?
6. Необходимо ли учитывать при записи решения дополнительные неизвестные, вводимые при переходе от неравенств к уравнениям?
7. Как найти начальный базис?
8. Сформулируйте алгоритм симплекс-метода.
9. Сформулируйте теорему о конечности алгоритма симплекс-метода.
10. Найдите максимум функции z = 4xl+ 3х2(xi 0) при условии
x1-x2 -2,
5x1+3x215,
x2 2,5,
2x1-x2 -2,
x1-2x2 2.
11. Для откорма крупного рогатого скота используется два вида кормов b1и b2, в которые входят питательные вещества а1, а2, а3и a4. Содержание количеств единиц питательных веществ в одном килограмме каждого корма, стоимость одного килограмма корма и норма содержания питательных веществ в дневном рационе животного представлены в таблице. Составьте рацион при условии минимальной стоимости.
| Питательные вещества |
Вид кормов |
Норма содержания питательного вещества |
| | B1
|
B2 |
|
A1
|
3 |
4 |
24 |
A2
|
1 |
2 |
18 |
A3
|
4 |
0 |
20 |
A4 |
0 |
1 |
6 |
Стоимость 1 кг корма, руб. |
2 |
1 |
|
12. Трикотажная фабрика использует для производства свитеров и кофточек чистую шерсть, силон и нитрон, запасы которых составляют, соответственно, 800, 400 и 300 кг.
Вид сырья в пряже |
Затраты пряжи на 10 шт., |
| | Свитер |
Кофточка |
Шерсть |
4 |
2 |
Силон |
2 |
I |
Нитрон |
1 |
1 |
Прибыль, руб. |
6 |
5 |
Количество пряжи (кг), необходимое для изготовления 10 изделий, а также прибыль, получаемая от их реализации, приведены в таблице. Составьте план производства изделий, обеспечивающий получение максимальной прибыли.
13. При подкормке посевов необходимо внести на 1 га почвы не менее 8 единиц химического вещества А, не менее 21 единиц химического вещества В и не менее 16 единиц химического вещества С. Фермер закупает комбинированные удобрения двух видов I и П. В таблице указано содержание количества единиц химического вещества в 1 кг каждого вида удобрений и цена 1 кг удобрений. Определите потребность фермера в удобрениях I и II вида на 1 га посевной площади при минимальных затратах на их приобретение.
Химические вещества |
Содержание химических веществ в I кг удобрения |
| | I |
II |
А |
1 |
5 |
В |
12 |
3 |
С |
4 |
4 |
Цена 1 кг удобрения, руб |
5 |
2 |
Заключение.
При решении задачи линейного программирования целесообразно использование компьютера. В этом случае можно составить программу, решающую задачу. Учитывая, что программирование довольно трудоемко, можно посоветовать воспользоваться для оформления результатов расчетов табличным процессором. Кроме того, если получившаяся модель задачи слишком громоздка, можно воспользоваться математическими пакетами, которые позволяют получить решение задачи линейного программирования. И, наконец, еще один возможный вариант применения компьютеров - комбинирование всех вышеуказанных способов.
Литература:
А.В.Могилев, Н.И.Пак, Е.К.Хеннер, Информатика,
М., Академия, 2003.-816 с.
- 1 -
|
400
|
48 |
48 |
76 |
101 |
118 |
|
|
| |
|
500
|
53 |
53 |
81 |
106 |
|
|
| | |
|
600
|
56 |
56 |
84 |
|
|
| | | |
|
700
|
58 |
58 |
|
|
| | | | |
|
m
|
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
F4(m) |
0 |
28 |
53 |
73 |
90 |
110 |
126 |
141 |
z4(m) |
0 |
0 |
0 |
0 |
0 |
100 |
100 |
100 |
Сведем результаты в таблицу №7.
|
m
|
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
F1(m)=f1(x1) |
0 |
28 |
45 |
65 |
78 |
90 |
102 |
113 |
z1=x1 |
0 |
100 |
200 |
300 |
400 |
500 |
600 |
700 |
|
|
|
| | | | | | |
|
F2(m)
|
0 |
28 |
53 |
70 |
90 |
106 |
120 |
133 |
z2(m) |
0 |
0 |
100 |
100 |
100 |
200 |
300 |
300 |
|
|
|
| | | | | | |
|
F3(m)
|
0 |
28 |
53 |
70 |
90 |
106 |
121 |
135 |
z3(m) |
0 |
0 |
0 |
0 |
0 |
0 |
100 |
100 |
|
|
|
| | | | | | |
|
F4(m)
|
0 |
28 |
53 |
73 |
90 |
110 |
126 |
141 |
z4(m) |
0 |
0 |
0 |
0 |
0 |
100 |
100 |
100 |
Теперь F4(700)=141 показывает максимальный суммарный эффект по всем 4-м фирмам, а z4(700)=100 - размер инвестиций в 4-ю фирму для достижения этого максимального эффекта. После этого на долю первых 3-х фирм осталось (700-100) и для достижения максимального суммарного эффекта по первым 3-м фирмам в 3-ю надо вложить 100 и т.д. Голубым цветом отмечены оптимальные значения инвестиций по фирмам и значения эффектов от них.
Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям: х1*=300; х2*=200; х3*=100; х4*=100. Оно обеспечивает производственному объединению наибольший возможный прирост прибыли 141 тыс.руб.
2. Анализ финансовых операций и инструментов.
2.1 Принятие решений в условиях неопределенности.
Предположим, что ЛПР (Лицо, Принимающее Решения) обдумывает четыре возможных решения. Но ситуация на рынке неопределенна, она может быть одной из четырех. С помощью экспертов ЛПР составляет матрицу доходов Q. Элемент этой матрицы q[i,j] показывает доход, полученный ЛПР, если им принято i-е решение, а ситуация оказалась j-я. В этой ситуации полной неопределенности могут быть высказаны лишь некоторые соображения о том, какое решение принять. Сначала построим матрицу рисков. Строится эта матрица так: в каждом столбце матрицы доходов находим максимальный элемент d[j] , после чего элементы r[i,j]=d[j]-q[i,j] и образуют матрицу рисков.
Смысл рисков таков: если бы ЛПР знал что в реальности имеет место j-я ситуация, то он выбрал бы решение с наибольшим доходом, но он не знает, поэтому, принимая i-е решение он рискует недобрать d[j]-q[i,j] - что и есть риск.
матрица доходов
|
Варианты (ситуации)
|
max |
min |
Вальд |
Гурвиц:l*max+ +(1-l)*min;l=1/3 |
|
Решения
|
0 |
1 |
2 |
8 |
8 |
0 |
|
2,67
|
|
|
2
|
3 |
4 |
10 |
10 |
2 |
2 |
4,67 |
|
|
0
|
4 |
6 |
10 |
10 |
0 |
|
3,32
|
|
|
2
|
6 |
8 |
12 |
12 |
2 |
2 |
5,32 |
