Линейное программирование

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

Microsoft Excel

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

Microsoft Word

Microsoft Word – это текстовый процессор предназначен для создания просмотра и редактирования текстовых документов, с локальным применением простейших форм таблично - матричных алгоритмов, относящийся к семейству Microsoft.

При работе с Ms Word мной были использованы следующие функции:

• колонтитулы
• форматирование шрифтов
• межстрочный интервал
• создание оглавление
• списки
• панель рисования (для создания алгоритмов)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.4. Алгоритм  нахождения оптимального решения  задач линейного программирования

Для того чтобы решить задачу симплексным  методом (методом последовательного  улучшения плана), необходимо выполнить  следующее:

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

 

2. СПЕЦИАЛЬНАЯ  ЧАСТЬ

2.1. Задание для курсового проекта

 

Данный курсовой проект был разработан на основе следующей системы уравнений-ограничений:

2x₁+3x₂-2x₃+5x₄+3x₅<=3

5x1+x₂+4x₃-3x₄-4x₅<=3

-7x₁+10x₂-22x₃-x₄+34x₅+3x₆+3x₇<=25

 

 и значения целевой функции:

 

 F(x) = x₁-5x₂-6x3-4x₄-3x₅+2x₆-4x₇→ max

 

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

 

2.1.1.Приведение задачи к каноническому  виду

 

Приведем задачу к каноническому  виду. Для этого в левую часть  первого ограничения-неравенства  типа “<=” вводим дополнительную переменную x₈ с коэффициентом “+1”. В целевую функцию переменная x₈ входит с коэффициентом 0 (то есть не входит). По аналогии вводим дополнительные переменные в остальные два ограничения-неравенства. Получаем:

 

2x₁+3x₂-2x₃+5x₄+3x₅+0x₆₊0x₇+x₈+0x₉+0x₁₀=3

5x₁+1x₂+4x₃-3x₄-4x₅+0x₆+0x₇+0x₈+0x₉+0x₁₀=3

-7x₁+10x₂-22x₃-1x₄+34x₅+3x₆+3x₇+0x₈+0x₉+0x₁₀ =25

 

F(x) = 1x₁-5x₂-6x3-4x₄-3x₅+2x₆-4x₇+0x₈+0x₉+0x₁₀ → max

 

 

 

2.2. Нахождение начального опорного решения (НОР)

Исходя из канонического вида задачи, можно найти начальное опорное  решение для неё:

 

2x₁+3x₂-2x₃+5x₄+3x₅+0x₆₊0x₇+x₈+0x₉+0x₁₀=3

5x₁+1x₂+4x₃-3x₄-4x₅+0x₆+0x₇+0x₈+0x₉+0x₁₀=3

-7x₁+10x₂-22x₃-1x₄+34x₅+3x₆+3x₇+0x₈+0x₉+0x₁₀ =25

 

F(x) = 1x₁-5x₂-6x3-4x₄-3x₅+2x₆-4x₇+0x₈+0x₉+0x₁₀ → max

 

Xij>0

 

НОР:  х₁,х_2,х_3,х₄,х₅,х_6,x₇=0

х₈=3     

х₉=3

х₁₀=25

F (x) =0

 

2.3. Нахождение оптимального решения

Для проверки правильности автоматического расчета в приложении необходимо произвести ручной расчет. В начале мы заполняем симплексную  таблицу (см. Таблицу 1) исходными данными: С_б, Х_б, А₀ и показатели критерия оптимальности.

Затем рассчитываем:

1. Значение целевой функции по формуле:

F = A₀₁*С_б1+ A₀₂*С_б2+ ..А_0n*C_бn

F=3*0+3*0+25*0=0

   2. Значения элементов целевой  строки по формуле.

Y_n=A_n1*C_бn+A_n2*C_бn+…A_nm*C_бn

Y₁ = 2*0+3*0+2*0+1*0=0 ????

Таким же способом рассчитываем остальные  элементы.

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

Высчитываем его по формуле:

K₁=0-1=-1  K₂=0+5=5  K₃=0+6=6  K₄=0+4=4  K₅=0+3=3 K₆=0-2=-2  и т.д.

   4. Выбираем столбец А₆ так как он по модулю больше всех остальных отрицательных чисел

   5. Теперь мы выбираем строку, по  следующим формулам:

Q₁=3/2=1.5

Q₂=3/5=0.6

Q₃=25/-7=3.57

   6. Выбираем строку с минимальным  значением по Q.

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

 

 

Итерация 1
Cбаз	Базис план	План X0	1,00	-5,00	-6,00	-4,00	-3,00	2,00	-4,00	0,00	0,00	0,00
			A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
0,00	A8	3,00	2,00	3,00	-2,00	5,00	3,00	0,00	0,00	1,00	0,00	0,00
0,00	A9	3,00	5,00	1,00	4,00	-3,00	-4,00	0,00	0,00	0,00	1,00	0,00
0,00	A10	25,00	-7,00	10,00	-22,00	-1,00	34,00	3,00	3,00	0,00	0,00	1,00
Zk		0,00	0,00	0,00	0,00	0,00	0,00	0,00	0,00	0,00	0,00	0,00
dk			-1,00	5,00	6,00	4,00	3,00	-2,00	4,00	0,00	0,00	0,00

Таб 1 Первый шаг расчета

Итерация 2
Cбаз	Базис план	План X1	1	-5	-6	-4	-3	2	-4	0	0	0
			A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
0	A8	3	2	3	-2	5	3	0	0	1	0	0
0	A9	3	5	1	4	-3	-4	0	0	0	1	0
2	A6	8,333	-2,33	3,333	-7,33	-0,33	11,33	1	1	0	0	0,333
Zk		23.17	16,67	-4,67	6,667	-14,7	-0,67	22,67	2	2	0	0
dk			0,29	-3,14	-5,67	11,67	-8,67	3,333	25,67	0	6	0

 

Таб 2 Второй шаг расчета

Итерация 2
Cбаз	Базис план	План X1	1	-5	-6	-4	-3	2	-4	0	0	0
			A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
0	A8	4,5	4,5	3,5	0	3,5	1	0	0	1	0,5	0
-6	A3	0,75	1,25	0,25	1	-0,75	-1	0	0	0	0,25	0
2	A6	13,83	6,833	5,167	0	-5,83	4	1	1	0	1,83	0,333
Zk		23,17	6,167	8,833	-6	-7,17	14	2	2	0	2,17	0,667
dk			5,167	13,83	0	-3,17	17	0	6	0	2,17	0,667

 

Таб 3 Третий шаг расчета

 

Итерация 3
Cбаз	Базис план	План X3	1	-5	-6	-4	-3	2	-4	0	0	0
			A1	A2	A3	A4	A5	A6	A7	A8	A9	A10
-4	a4	1,286	1,286	1	0	1	0,286	0	0	0,286	0,14	0
-6	a3	1,714	2,214	1	1	0	-0,79	0	0	0,214	0,36	0
2	a6	21,33	14,33	11	0	0	5,667	1	1	1,667	2,67	0,333
Zk		27,24	10,24	12	-6	-4	14,9	2	2	0,905	2,62	0,667
dk			9,238	17	0	0	17,9	0	6	0,905	2,62	0,667

 

Таб 4 Четвертый шаг расчета