Xreferat.com » Рефераты по математике » Розв'язок задачі лінійного програмування

Розв'язок задачі лінійного програмування

перевищуватимуть суму, яку можливо було б отримати за реалізацію продукції виготовленої з тієї самої кількості ресурсів, тобто


Розв'язок задачі лінійного програмування.


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


Розв'язок задачі лінійного програмування.


Отже в результаті маємо двоїсту задачу:


Розв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмування


Визначити, які мінімальні ціни можливо встановити для одиниці кожного і-го виду ресурсу Розв'язок задачі лінійного програмування, щоб продаж ресурсів був більш доцільним ніж виробництво продукції. Причому відомі: загальна кількість ресурсів – Розв'язок задачі лінійного програмування, нормативи використання кожного і-го виду ресурсу на кожен j-ий вид продукції – Розв'язок задачі лінійного програмування, а також Розв'язок задачі лінійного програмування – ціна реалізації одиниці продукції.

Для побудови двоїстої задачі необхідно звести початкову до стандартного виду. Задача лінійного програмування подана у стандартному вигляді, якщо для відшукання максимального значення цільової функції всі нерівності системи обмежень приведені до вигляду «Розв'язок задачі лінійного програмування», а для задачі відшукання мінімального значення – до вигляду «Розв'язок задачі лінійного програмування».

Якщо пряма задача лінійного програмування подана в стандартному вигляді, то двоїста задача утворюється за такими правилами:

1. Кожному обмеженню прямої задачі відповідає змінна двоїстої задачі. Кількість невідомих двоїстої задачі дорівнює кількості обмежень прямої задачі.

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

3. Якщо цільова функція прямої задачі задається на пошук найбільшого значення (max), то цільова функція двоїстої задачі — на визначення найменшого значення (min), і навпаки.

4. Коефіцієнтами при змінних в цільовій функції двоїстої задачі є вільні члени системи обмежень прямої задачі.

5. Правими частинами системи обмежень двоїстої задачі є коефіцієнти при змінних в цільовій функції прямої задачі.

6. Матриця


Розв'язок задачі лінійного програмування,

що складається з коефіцієнтів при змінних у системі обмежень прямої задачі, і матриця коефіцієнтів в системі обмежень двоїстої задачі


Розв'язок задачі лінійного програмування


утворюються одна з одної транспонуванням, тобто заміною рядків стовпчиками, а стовпчиків — рядками.

Теорема (перша теорема двоїстості). Якщо одна з пари спряжених задач має оптимальний план, то і інша також має розв’язок, причому для оптимальних розв’язків значення цільових функцій співпадають Розв'язок задачі лінійного програмування.

Якщо цільова функція однієї із задач не обмежена, то інша задача також не має розв’язку.

Між розв’язками спряжених задач крім рівності значень цільових функцій, існує більш тісний взаємозв’язок. Для його дослідження розглянемо дві симетричні задачі лінійного програмування.

Пряма задача: Двоїста задача:


Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування

Для розв’язування задач симплексним методом необхідно привести їх до канонічної форми, для чого в систему обмежень задачі необхідно ввести m невід’ємних змінних, а в систему обмежень – n невід’ємних змінних. Поставимо обмеженням кожної задачі у відповідність змінні двоїстої.


Розв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмуванняАналогічно:


Розв'язок задачі лінійного програмування


Отримали наступну відповідність між змінними спряжених задач:


Основні змінні прямої задачі Додаткові змінні прямої задачі


Розв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування

Розв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмуванняРозв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування Розв'язок задачі лінійного програмування

Розв'язок задачі лінійного програмування

Додаткові змінні двоїстої задачі Основні змінні двоїстої задачі


Наступна теорема в літературі як правило має назву теореми про доповнюючу нежорсткість.

Теорема (друга теорема двоїстості для симетричних задач). Для того, щоб плани Розв'язок задачі лінійного програмування та Розв'язок задачі лінійного програмування відповідних спряжених задач були оптимальними, необхідно і достатньо щоб виконувалися умови доповнюючої нежорсткості:


Розв'язок задачі лінійного програмування


Розв'язок задачі лінійного програмування.


Більш очевидно взаємозв’язок між оптимальними планами прямої та двоїстої задач встановлює наслідок другої теореми двоїстості.

Наслідок. Якщо в результаті підстановки оптимального плану однієї із задач (прямої чи двоїстої) в систему обмежень цієї задачі і-те обмеження виконується як строга нерівність, то відповідний і-ий компонент оптимального плану спряженої задачі дорівнює нулю.

Якщо і-ий компонент оптимального плану однієї із задач додатний, то відповідне і-те обмеження спряженої задачі виконується для оптимального плану як рівняння.

Побудуємо двоїсту:


Розв'язок задачі лінійного програмування


Побудуємо симплекс таблиці для прямої задачі:


1 3 0 0 0



x1 x2 x3 x4 x5 B T
x3 4 3 1 0 0 12 4
x4 -1 2 0 1 0 4 2 **
x5 2 -1 0 0 1 4 ###
F -1 -3 0 0 0 0 0


**















1 3 0 0 0



x1 x2 x3 x4 x5 B T
x3 5,5 0 1 -1,5 0 6 1,09 **
x2 -0,5 1 0 0,5 0 2 ###
x5 1,5 0 0 0,5 1 6 4
F -2,5 0 0 1,5 0 6 0

**
















1 3 0 0 0



x1 x2 x3 x4 x5 B T
x1 1 0 0,18 -0,27 0 1,09 1,09
x2 0 1 0,09 0,36 0 2,55 ###
x5 0 0 -0,27 0,91 1 4,36 4
F 0 0 0,45 0,82 0 8,73 0

Отже, максимум F дорівнює 8,73 в точці (1,09, 2,55).

Тоді мінімум К(у) дорівнює також 8,73. у* = (0, 2,33, 1,67)Т.


Задача 4


Методом потенціалів розв’язати ТЗ.


Розв’язання:


Q1 Q2 Q3 Q4 Q5 a
P1 7 3 1 5 4 30
P2 7 5 8 3 2 25
P3 6 4 8 3 2 45
P4 3 1 7 6 2 20
b 10 35 15 25 35

10 +35+15+25+35 = 120

30+ 25+ 45+ 20 = 120.

Отже, ТЗ є закритою.


Знайдемо початковий план методом пн-зх кута.


Q1 Q2 Q3 Q4 Q5 a
P1 7


3


1


5


4


5


10


20








P2 7


5


8


2


2


25




15


10






P3 6


4


8


2


2


10






5


25


15
P4 3


1


7


2


2


20










20
b 10 10 15 25 10

Поетапно проведемо методом потенціалів розв’язок задачі:


Q1 Q2 Q3 Q4 Q5 u
P1 7


3 - 1 + 5


4


4


10


20 -5


5


4



P2 7


5 + 8 - 2


2


6

-2



15


10 0


0



P3 6


4


8


2


2


6

-3


-1



5


25


15
P4 3


1


7


2


2



0


2


5


6



20
v 3 -1 2 -4 -4













Q1 Q2 Q3 Q4 Q5 u
P1 7 - 3


1 + 5


4


4


10


10


10 10


9



P2 7


5


8


2


2


6

-2



25 5


5


5



P3 6


4


8 - 2


2 + 11

-8


-6



5


25


15
P4 3 + 1


7


2


2 - 11

-11


-9


-1


0



20
v 3 -1 -3 -9 -9













Q1 Q2 Q3 Q4 Q5 u
P1 7


3


1


5


4


5


5


10


15 7


7



P2 7


5


8


2


2


7

2



25 7


7


7



P3 6


4


8


2


2


1

7


7


7



25


20
P4 3


1


7


2


2


1


5 7


7


7



15
v 2 -2 -4 1 1

Всі оцінки Сij – vi – uj на 3 етапі невід’ємні, тому оптимальний розв’язок знайдено.


5 10 15 0 0
X = 0 25 0 0 0

0 0 0 25 20

5 0 0 0 15

Вартість перевезень дорівнює: 7 * 5 + 3 * 10 + 1 * 15 + 5 * 25 + 3 * 5 + 2 * 25 + 2 * 20 + 2 * 15 = 340.

Список використаних джерел


Бурий В.В., Шевченко І.В. Математичне програмування. — К.: НАУ, 2007. — 168с.

Єгоршин О.О., Малярець Л.М. Математичне програмування. — Х.: ВД "ІНЖЕК", 2006. — 383с.

Жильцов О.Б., Кулян В.Р., Юнькова О.О. Математичне програмування (з елементами інформаційних технологій) / Міжрегіональна академія управління персоналом / Олена Олександрівна Юнькова (ред.). — К.: МАУП, 2006. — 184с.

Зеленський К.Х. Математичне програмування. — К.: Університет "Україна", 2007. — 241c.

Лебідь М.Т., Синявіна ЮВ. Математичне програмування. — Х., 2007. — 72с.

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: