WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Загальна задача лінійного програмування та деякі з методів її розв’язування - Реферат

Загальна задача лінійного програмування та деякі з методів її розв’язування - Реферат


Реферат на тему:
Загальна задача лінійного програмування та деякі з методів її розв'язування.
План.
1. Приклади розв'язування задач модифікованим симплекс-методом.
2. Література
Розв'язування задач модифікованим симплекс-методом.
1. Обчислюють компоненти вектора Рs в кінцевому балансі. Якщо серед компонентів вектора Рs немає додатніх, то цільова функція задачі не можлива на багато планів. Якщо ж серед компонентів вектора Рs знаходяться додатні, то переходять до нового опорного плану.
2. По відомим правилам симплекс-метода знаходять розв'язаний рядок і обчислюють додатні компоненти нового опорного плану, а також матрицю В-1,обернену матрицю В, складеної із компонентів вектора нового базису.
3. Перевіряють новий опорний план на оптимальність і в випадку необхідності проводять обчислення спочатку з елемента 3.
1). Розв'язати модифікованим симплексним методом задачу 1, в визначенні максимального значення функції F= 9x1+10x2+16x3 при умовах
, ( )
Розв'язок: Дана задача має опорний план х=(0;0;0;360;192;180), який визначається базисом, утворений векторами Р4, Р5 і Р6 . Компоненти цих векторів визначають одиничну матрицю В, обернена до В-1 також являється одиничним.
і Базис Сб Р0 9 10 16 0 0 0
Р1 Р2 Р3 Р4 Р5 Р6
1 Р4 0 360 18 15 12 1 0 0 0 0 2/9
2 Р5 0 192 6 4 8 0 1 0 0 2 5/3
3 Р6 0 180 5 3 3 0 0 1 0 0 0
4
-9 -10 -16 0 0 0
5
3 -2 0 0 2 0
6
5 0 0 2/9 5/3 0
і Базис Сб Р0 А1 А2 А3 Р3
1 Р4 0 360 1 0 0 12
2 Р5 0 192 0 1 0 8
3 Р6 0 180 0 0 1 3
4 0 0 0 0 -16
Складам допоміжну і основну таблицю ( табл. 1 і 2).Спочатку в табл.1 на основі кінцевих даних заповнюємо перші три рядки стовпців векторів , ,..., , а в табл. 2 - перші три рядки стовпців векторів , , , (елементи стовпців векторів , , представляють собою відповідні стовпці матриці ). Після цього знаходимо вектор , компоненти якого записуємо в 4-му рядку табл. 1. Ці числа визначаємо по формулі, одержуємо в результаті скалярних утворень вектора на відповідні вектори :
В 4-му рядку табл.2 в стовпці вектора записано так її значення цільної функції задачі при кінцевому опорному плані, який одержано як результат скалярного утворення вектора на вектор :
Після заповнення 4-го рядка табл. 2 знайдені компоненти вектора записуємо у табл. 1 .На основі даних цієї таблиці по формулі знаходимо числа :
Так як серед чисел існують від'ємні, то кінцевий опорний план не являється оптимальним. Перейдемо до нового опорного плану. Вектор, який при цьому слідує ввести в базис, визначають по найбільшій абсолютній величині від'ємних чисел . В данному випадку це число -16 , знаходиться в стовпці вектора Р3 табл. 1. Тому останній стовпець таблиці для вектора Р3. В цьому стовпці записуємо компоненти розміщення вектора Р3 по векторам даного базису. Вони визначаються в результаті множення матриць В-1 (записаної в табл.2) на матрицю - стовпець, елементами якої являються компоненти вектора Р3 (записані втабл.1):
Якщо би серед знайдених чисел не було додатних, то задача не мала би оптимального плану. Оскільки додатні числа є, переходимо до нового опорного плану. Для цього введемо в базис вектор Р3, а виключимо із нього вектор Р5 обумовлений тим, що досягається при і = 5.
Рахуючи тепер число 8 розв'язаним елементом, а 2-й рядок і стовпець вектора Р3 таблиці 2 - направляючим, переходимо до табл.3, в якій елементи перших трьох рядків стовпціввекторів Р0, А1, А2 і А3 знайдені з допомогою відомих правил переходу від однієї симплекс-таблиці до другої.
Таблиця 3
і Базис Сб Р0 А1 А2 А3 Р2
1 Р4 0 72 1 -3/2 0 9
2 Р3 16 24 0 1/8 0 2
3 Р6 0 108 0 -3/8 1 3/2
4 384 0 2 0 -2
Після цього знаходимо компоненти вектора . Їх значення одержуються в результаті скалярного утворення вектора Сб і відповідних векторів А1,А2 і А3, компоненти яких записані в табл.3:
Одержані компоненти вектора записуємо в 4-му рядку табл.3 і відповідному стовпці табл.1. Після цього знаходимо числа і записуємо їх в 5-му рядку таблиці. Так як серед чисел є від'ємне (-2), то знайдений опорний план X=(0; 0; 24; 72; 0; 108) на являться оптимальним. Тому в таблиці 3 відводимо останній стовпець для вектора Р2. Його компоненти в новому базисі визначається в результаті множення матриці В-1 (елементами якої являються числа таблиці 3 стоять в стовпцях векторів А1, А2, А3) на матрицю -стовпець, елементами якої являються компоненти вектора Р2(записані в таблиці 1):
Зайдений опорний план Х=(0; 0; 5; 2; 34; 0)перевіряємо на оптимальність. Для цього знаходимо вектор і вибираємо число . Так як серед цих чисел є від'ємні (-4), то в таблиці 7 заповнюємо стовпець вектора Р6 і переходимо до нового опорного плану табл. 8
Таблиця 8
і Базис Сб Р0 А1 А2 А3
1 Р4 1 35 1 1/2 0
2 Р6 0 1 0 1/2 -1
3 Р3 6 11/2 0 1/4 0
4 68 1 2 0
Знаходимо вектор , записуємо його компоненти в 4-му рядку табл. 8 і відповідному стовпцю табл. 5. Так як серед вказаних чисел немає від'ємних, то знайдений опорний план Х*=(0; 0; 11/2; 35; 0; 1;) являється оптимальним планом кінцевою задачі. При цьому плані цільова функція приймає своє максимальне значення Fmax = 68. Порівнюючи процеси знаходження розв'язку приведених вище задач симплексним методом і модифікованим симплексним методом, закінчуємо, що при використанні останнього метода знадобилося проводити менше обчислень. Це характерно і для знаходження розв'язку других задач лінійного програмування, завчасно всього таких, для деяких число т звичайно менше ніж п. Тому в багатьох випадках при виборі метода розв'язку конкретних задач перевага віддається модифікованому симплексному методові. При цьому для різних форм цього методу розроблені стандартні програми його використання при розв'язку конкретних задач.
Використана література.
1. Наконечний С.І., Савіна С.С. Математичне програмування: Навч. посіб. - К.:
КНЕУ, 2003.- 452 с.
2. Барвінський А.Ф та ін. Математичне програмування: Навчальний посібник / А.Ф. Барвінський, І.Я. Олексів, З.І. Крупка, І.О. Бобик, І.І. Демків, Р.І. Квіт, В.В. Кісілевич - Львів: Національний університет "Львівська політехніка" (Інформаційно-видавничий центр "Інтелект+" Інститут післядипломної освіти)
"Інтелект - Захід", 2004. - 448 с.
3. Акулич М.Л.Математичиское програмирование в примерах и задачах: Учебное пособие для студентов экономических специальних вузов. - Вища школа, 1985-319с.,ст.36-47.
4. Вітлінський В.В., Наконечний С.І., Терещенко Т.О. Математичне програмування: Навч. - метод. посібник для самост. вивч. дисц. - К.: КНЕУ, 2001. - 248 с.
5. Математичне програмування (методичний посібник для студентів економічних спеціальностей)/Укладачі: Лавренчук В.П., Веренич І.І., Готинчан Т.І., Дронь В.С., Кондур О.С., - Чернівці: "Рута", 1998.-168 с
Loading...

 
 

Цікаве