Симплекс метод

 

Элементы  целевой строки рассчитывают по обычным  правилам и получают отрицательные знаки.

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

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

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

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

Столбцы х₁, х₂, х₃ будут иметь следующие отношения:

Наименьшее  отношение имеет столбец х₁, он и будет являться ключевым.

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

1-я итерация

cj	p0	x0	18	15	24	0	0	0	0
			x1	х2	х3	х4	х5	х6	х7
0	х4	-15	0	-0.75	0.75	1	-0.25	0	0
8	х1	35	1	0.25	0.75	0	-0.25	0	0
0	х6	-92	0	-3.75	-0.25	0	-0.25	1	0
0	х7	-80	0	-3	-2	0	0	0	1
Zj - Cj		280	0	-10	-4	0	-2	0	0

 

После преобразования элементов в итоговом столбце  осталось еще три отрицательных числа в строке х₄, х₆ и х₇. Наибольшим по абсолютной величине является число в строке х₆. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х₂. Вводим этот вид сырья в программу вместо неизвестного х₆. По общим правилам преобразуем элементы матрицы.

2-я итерация

cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	3.4	0	0	0.8	1	-0.2	-0.2	0
8	х1	28.9	1.0	0.0	0.7	0.0	-0.3	0.1	0.0
15	х2	24.5	0.0	1.0	0.1	0.0	0.1	-0.3	0.0
0	х7	-6.4	0.0	0.0	-1.8	0.0	0.2	-0.8	1.0
Zj - Cj		525.3	0.0	0.0	-3.3	0.0	-1.3	-2.7	0.0

 

После преобразования элементов в итоговом столбце  осталось еще одно отрицательное  число в строке х₇. Эта строка будет принята за ключевую для последующего расчета. Ключевой столбец определяется по наименьшему отношению элементов целевой строки к элементам ключевой строки. Им будет столбец х₃. Вводим этот вид сырья в программу вместо неизвестного х₇. По общим правилам преобразуем элементы матрицы.

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

3-я итерация

cj	p0	x0	x1	х2	х3	х4	х5	х6	х7
0	х4	0.6	0.0	0.0	0.0	1.0	-0.1	-0.6	0.4
8	х1	26.3	1.0	0.0	0.0	0.0	-0.2	-0.3	0.4
15	х2	24.3	0.0	1.0	0.0	0.0	0.1	-0.3	0.0
10	х3	3.6	0.0	0.0	1.0	0.0	-0.1	0.4	-0.6
Zj - Cj		537.2	0.0	0.0	0.0	0.0	-1.7	-1.2	-1.9

Подставив значения неизвестных в исходные неравенства, получаем:

1 * 26,3 + 1 * 24,3 + 0 * 3,6 ≥ 50

4 * 26,3 + 1 * 24,3 + 3 * 3,6 ≥ 140

1 * 26,3 + 4 * 24,3 + 1 * 3,6 ≥ 127

0 * 26,3 + 3 * 24,3 + 2 * 3,6 ≥ 80

Стоимость сырья при этом будет минимальной  и составит:

F = 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

В курсовой работе проделана работа по изучению следующих вопросов:

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

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

Программа имеет ограничения: количество рассмотренных  уравнений и вводимых элементов  уравнения не должно превышать 10.

Программа не рассчитана на неправильный ввод формата  вводимых данных.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Список использованной литературы

1. Б.Я. Советов – «АСУ. Внедрение в специальность» (1989г.)
2. Е.С. Вентцель – «Исследование операций» (1972г.)
3. Конспекты по «АСУ»
4. Конспекты по «Компьютерному моделированию»
5. Г. Жимерин, В.А. Мясников – «Автоматизированные и автоматические системы уравнения» (1975г.)
6. Б.Я. Советов – «АСУ. Внедрение в специальность» (1989г.)
7. Е.С. Венцель – «Исследование операций» (1972г.)
8. http://www.reshmat.ru
9. http://www.matburo.ru
10. http://www.grandars.ru
11. http://1cov-edu.ru