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

Розв’язання лінійних задач методами лінійного програмування

align="BOTTOM" border="0" />

5 2 7 5 0 20

10 10


Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30


20 10

Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20



5 15
Потреба в продукті 40 30 30 15 15 130

Таким чином, в таблиці5 отримали початковий опорний план, транспортні витрати за яким складають:


Розв’язання лінійних задач методами лінійного програмування


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

Для визначення оптимального плану перевезень використаємо метод потенціалів. Для цього кожному виробнику Аі (кожному рядку) ставимо у відповідність деяке число Розв’язання лінійних задач методами лінійного програмування а кожному споживачу Ві (кожному стовпчику)– деяке число Розв’язання лінійних задач методами лінійного програмування На основі таблиці5 складемо таблицю6, в якій додамо один стовпчик і один рядок для написання величини параметрів Розв’язання лінійних задач методами лінійного програмуванняі Розв’язання лінійних задач методами лінійного програмування. Їх знаходимо використовуючи першу умову оптимальності транспортної задачі: Розв’язання лінійних задач методами лінійного програмування (для кожної зайнятої клітини сума потенціалів повинна дорівнювати вартості одиниці перевезення, що записана в цій клітині).


Таблиця6– Перевірка оптимальності опорного плану

Виробник Споживач Запаси продукту

Розв’язання лінійних задач методами лінійного програмування


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування



Розв’язання лінійних задач методами лінійного програмування

8 3 3 4 0 60 0

40 20




Розв’язання лінійних задач методами лінійного програмування

5 2 7 5 0 20 -1


10 10



Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30 0



20 10


Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20 5




5 15

Потреба в продукті 40 30 30 15 15 130 Ч

Розв’язання лінійних задач методами лінійного програмування

8 3 8 2 -5 Ч Ч

Систему потенціалів можна побудувати лише для невирожденого опорного плану. Такий план містить m+n-1 лінійно незалежних рівнянь виду Розв’язання лінійних задач методами лінійного програмування з m+n невідомими (де m– кількість постачальників, n– кількість споживачів). Рівнянь на одне менше, ніж невідомих, тому система є невизначеною і для її розв’язку одному невідомому (нехай ним буде u1) придамо нульове значення.

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


Розв’язання лінійних задач методами лінійного програмування


З розрахунків бачимо, що умова оптимальності не виконується для клітин, А1В3, А2В1, А3В1, А4В1, А4В2, і А4В3. Клітину, в якій додатне число отримали максимальним (А2В3, оскільки max(5;2;3;6;7;8)=8) зробимо зайнятою, для цього побудуємо цикл і отримуємо таблицю7.


Таблиця7– Другий крок пошуку оптимального рішення

Виробник Споживач Запаси продукту

Розв’язання лінійних задач методами лінійного програмування


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування



Розв’язання лінійних задач методами лінійного програмування

8 3 3 4 0 60 0

40 20




Розв’язання лінійних задач методами лінійного програмування

5 2 7 5 0 20 -1


10 10



Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30 0



15 15


Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20 -3



5
15

Потреба в продукті 40 30 30 15 15 130 Ч

Розв’язання лінійних задач методами лінійного програмування

8 3 8 2 3 Ч Ч

Транспортні витрати при такому плані перевезення складають:


Розв’язання лінійних задач методами лінійного програмування


Перевірка всіх вільних клітин:


Розв’язання лінійних задач методами лінійного програмування


Отримали від’ємні значення у всіх клітинах окрім А1В3 (5), А1В5 (3), А2В1 (2), А2В5 (2), А3В1 (3) і А3В5 (3). Максимальне значення max(5;3;2;2;3;3)=5 в клітині А1В3, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці7, результат дій в таблиці8).


Таблиця8– Третій крок пошуку оптимального рішення

Виробник Споживач Запаси продукту

Розв’язання лінійних задач методами лінійного програмування


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування



Розв’язання лінійних задач методами лінійного програмування

8 3 3 4 0 60 -

40 10 10



Розв’язання лінійних задач методами лінійного програмування

5 2 7 5 0 20 -1


20




Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30 5



15 15


Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20 2



5
15

Потреба в продукті 40 30 30 15 15 130 Ч

Розв’язання лінійних задач методами лінійного програмування

8 3 3 -3 -2 Ч Ч

Транспортні витрати:


Розв’язання лінійних задач методами лінійного програмування


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

Перевірку всіх вільних клітин зобразимо в таблиці9, в якій для всіх вільних клітин запишемо різницю між сумою потенціалів і транспортними витратами в клітині.


Таблиця9– Перевірка плану отриманого в результаті третього кроку пошуку оптимального рішення задачі


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

- - - -7 -2

Розв’язання лінійних задач методами лінійного програмування

2 - -5 -9 -3

Розв’язання лінійних задач методами лінійного програмування

8 4 - - 3

Розв’язання лінійних задач методами лінійного програмування

3 4 - -8 -

З таблиці9 видно, що додатне значення отримали для клітин А2В1 (2), А3В1 (8), А3В2 (4), А3В5 (3), А4В1 (3) і А4В2 (4). Максимальне значення max(2;8;4;3;3;4)=8 в клітині А3В1, тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці8, результат дій в таблиці10).

Таблиця1– Четвертий крок пошуку оптимального рішення задачі

Виробник Споживач Запаси продукту

Розв’язання лінійних задач методами лінійного програмування


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування



Розв’язання лінійних задач методами лінійного програмування

8 3 3 4 0 60 0

25 10 25



Розв’язання лінійних задач методами лінійного програмування

5 2 7 5 0 20 -1


20




Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30 -3

15

15


Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20 2



5
15

Потреба в продукті 40 30 30 15 15 130 Ч

Розв’язання лінійних задач методами лінійного програмування

8 3 3 5 -2 Ч Ч

Транспортні витрати:


Розв’язання лінійних задач методами лінійного програмування


що на 120грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.

Перевірка всіх вільних клітин наведена в таблиці11.


Таблиця11– Різниця між сумою потенціалів і транспортними витратами для вільних клітин


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

- - - 1 -2

Розв’язання лінійних задач методами лінійного програмування

2 - -5 -1 -3

Розв’язання лінійних задач методами лінійного програмування

- -4 -8 - -5

Розв’язання лінійних задач методами лінійного програмування

3 4 - 0 -

План, зображений в таблиці10 не є оптимальним, оскільки отримали додатні значення в клітинах А1В4 (1), А2В1 (2), А4В1 (3), А4В2 (4). Заповнюємо клітину А4В2 і будуємо опорний план (таблиця12).


Таблиця12– П’ятий крок пошуку оптимального рішення задачі

Виробник Споживач Запаси продукту

Розв’язання лінійних задач методами лінійного програмування


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування



Розв’язання лінійних задач методами лінійного програмування

8 3 3 4 0 60 0

25 5 30



Розв’язання лінійних задач методами лінійного програмування

5 2 7 5 0 20 -1


20




Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30 -3

15

15


Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20 -2


5

15

Потреба в продукті 40 30 30 15 15 130 Ч

Розв’язання лінійних задач методами лінійного програмування

8 3 3 5 2 Ч Ч

Транспортні витрати за отриманим планом перевезень складають:


Розв’язання лінійних задач методами лінійного програмування


що на 20грн. економніше попереднього варіанту розвезення продукції від постачальників до споживачів.

Перевірка всіх вільних клітин здійснена в таблиці 13.


Таблиця13– Різниця між сумою потенціалів і транспортними витратами для вільних клітин


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

- - - 1 2

Розв’язання лінійних задач методами лінійного програмування

2 - -5 -1 1

Розв’язання лінійних задач методами лінійного програмування

- -4 -8 - -1

Розв’язання лінійних задач методами лінійного програмування

-1 - -4 -4 -

Оскільки в результаті розрахунків отримали додатні значення, то знову будуємо цикл і заповнюємо необхідну клітину. В даному випадку це буде або клітина А2В1 або клітина А1В5. Вибираємо останню, оскільки транспортні витрати на перевезення в ній менші. На від’ємних кутах циклу об’єм перевезень становить 10 і 0. Оскільки min(10;0)=0, то всі клітини залишаються незмінними і лише клітина з нульовим перевезенням переходить з А4В5 на А1В5.

Новий план зображено в таблиці14.


Таблиця14– Шостий крок пошуку оптимального рішення задачі

Виробник Споживач Запаси продукту

Розв’язання лінійних задач методами лінійного програмування


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування



Розв’язання лінійних задач методами лінійного програмування

8 3 3 4 0 60 0

25
30
5

Розв’язання лінійних задач методами лінійного програмування

5 2 7 5 0 20 -1


20




Розв’язання лінійних задач методами лінійного програмування

5 4 8 2 0 30 -3

15

15


Розв’язання лінійних задач методами лінійного програмування

7 1 5 7 0 20 0


10

10

Потреба в продукті 40 30 30 15 15 130 Ч

Розв’язання лінійних задач методами лінійного програмування

8 1 3 5 0 Ч Ч

Транспортні витрати за отриманим планом перевезень складають:


Розв’язання лінійних задач методами лінійного програмування


Розрахунки для перевірка всіх вільних клітин здійснені в таблиці 15:

Таблиця15– Різниця між сумою потенціалів і транспортними витратами для вільних клітин


Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

Розв’язання лінійних задач методами лінійного програмування

- -2 - 1 -

Розв’язання лінійних задач методами лінійного програмування

4 - -3 1 1

Розв’язання лінійних задач методами лінійного програмування

- -6 -8 - -3

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

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

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

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