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

Посмотреть архив целиком

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

Чернігівський державний технологічний університет

Кафедра вищої математики










Контрольна робота

з дисципліни: Математичне програмування

Варіант 06















Чернігів 2009


Зміст


Завдання №1

Завдання №2

Завдання №3

Завдання №4

Завдання №5

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



Завдання №1


Звести до канонічної форми задачу лінійного програмування:



Дана задача лінійного програмування задана в симетричній формі запису: умови, при яких функція F буде максимальною, задані у вигляді нерівностей. Для того, щоб отримати канонічну форму задачі лінійного програмування необхідно нерівності перетворити у рівності, використовуючи теорему, за якою нерівність



еквівалентна рівнянню


і нерівності


а нерівність вигляду



еквівалентна рівнянню


, в якому


Враховуючи наведене вище дану задачу запишемо у наступній канонічній формі:



Завдання №2


Визначити оптимальний план задачі лінійного програмування графічним методом (знайти максимум і мінімум функції):



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



Потім знаходимо напівплощини, в яких виконуються задані нерівності (рисунок1).



Рисунок1– Графічне визначення максимального і мінімального значення функції


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



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


.


Завдання №3


Побудувати двоїсту задачу. Симплексним методом знайти оптимальний план початкової задачі. Використовуючи першу теорему двоїстості, визначити план другої задачі.



Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х3, х4 і х5. Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х6 і х7 та отримаємо одиничні матриці А6 і А7. Де


і


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



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

Запишемо задачу у векторній формі:



де



В якості базису вибираємо одиничні вектори А6, А4, А7. Вільні невідомі прирівнюємо нулю . В результаті отримаємо початковий опорний план розширеної задачі


,


якому відповідає розкладення



Для перевірки початкового опорного плану складаємо першу симплексну таблицю (таблиця1) і підраховуємо значення функції і оцінок Маємо:



тобто оскільки М попередньо не фіксовано, то оцінки є лінійними функціями величини М, причому функція складається з двох доданків, одне з яких залежить від М, інше не залежить. Для зручності розрахунків в (F-C) рядок запишемо доданок, незалежний від М, а в (М) рядок – тільки коефіцієнти при М, які і дозволяють порівняти оцінки між собою. Для векторів базису оцінки дорівнюють нулю.


Таблиця1– Перша симплексна таблиця

Базис

С базису

А0

х1

х2

х3

х4

х5

х6

х7

х6

М

8

1

-1

0

0

1

0

х4

0

20

3

4

0

1

0

0

0

х7

М

6

3

1

0

0

-1

0

1

F-C

0

-5

-2

0

0

0

0

0

М

14

4

4

-1

0

-1

0

0


В (М) рядку є додатні оцінки, тому опорний план Х0 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Оскільки у нас максимальне значення 4 належить двом векторам, то в базис включаємо вектор, якому відповідає мінімальне Сj. Розв’язувальним рядком вибирається той, в якому найменше відношення Серед коефіцієнтів розкладання векторів А1 і А2 по базису є додатні, тому хоча б один з векторів існує.. Знайдемо ці значення:


;


Таким чином підтвердилося, що розв’язувальним стовпчиком буде другий, і визначилося, що розв’язувальним рядком буде перший. Тобто розв’язувальний елемент – число 3. Тоді вектор А2 включаємо в базис, а вектор А6 виключаємо з нього.

Складаємо другу симплексну таблицю (таблиця2). При цьому елементи першого (розв’язувального) рядка ділимо на 3. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.


Таблиця2– Друга симплексна таблиця

Базис

С базису

А0

х1

х2

х3

х4

х5

х6

х7

х2

2

2,67

0,33

1

-0,33

0

0

0,33

0

х4

0

9,33

1,67

0

1,33

1

0

-1,33

0

х7

М

3,33

0

0,33

0

-1

-0,33

1

F-C

5,33

-4,33

0

-0,67

0

0

0,67

0

М

3,33

2,67

0

0,33

0

-1

-1,33

0


В (М) рядку є додатні оцінки, тому план, зображений в таблиці2 не є оптимальним і його можна покращити, включивши в базис вектор, якому відповідає . Тобто за розв’язувальний стовпчик вибираємо перший. Мінімальне відношення



тому розв’язувальним рядком є третій. Таким чином розв’язувальний елемент – число 2,67. Тоді вектор А1 включаємо в базис, а вектор А7 виключаємо з нього.

Складаємо другу симплексну таблицю (таблиця3). При цьому елементи третього (розв’язувального) рядка ділимо на 2,67. Елементи інших рядків визначаємо використовуючи формули повного виключення Йордана-Гауса.



Таблиця3– Третя симплексна таблиця

Базис

С базису

А0

х1

х2

х3

х4

х5

х6

х7

х2

2

2,25

0

1

-0,375

0

0,125

0,375

-0,125

х4

0

7,25

0

0

1,125

1

0,625

-1,125

-0,625

х1

5

1,25

1

0

0,125

0

-0,375

-0,125

0,375

F-C

10,75

0

0

-0,125

0

-1,625

0,125

1,625

М

0

0

0

0

0

0

-1

-1


В результаті проведеної ітерації з базису виключено штучні елементи, тому в рядку (М) всі оцінки, крім оцінки штучного вектору, перетворилися на нуль. Оскільки в рядках (F-C) і (М) не має додатних значень, то знайдене рішення


()


є оптимальним. Функція при цьому



Перевірка



Кожній задачі лінійного програмування можна поставити у відповідність двоїсту задачу. Для цього першим кроком необхідно впорядкувати запис вихідної задачі. Оскільки у нас функція мінімізується, то всі умови-нерівності повинні бути вигляду . Виконання цієї умови досягаємо множенням відповідних умов на (1-). В результаті система обмежень матиме наступний вигляд:



Оскільки вихідна задача є задачею мінімізації, то двоїста буде задачею максимізації. Двоїста задача буде мати три змінні , оскільки вихідна задача має три обмеження. При цьому вектор, отриманий із коефіцієнтів при невідомих цільової функції вихідної задачі , співпадає з вектором констант у правих частинах обмежень двоїстої задачі. Аналогічно пов’язані між собою вектори, утворені з коефіцієнтів при невідомих цільової функції двоїстої задачі , і константи в правих частинах обмежень вихідної задачі. Кожній змінній двоїстої задачі відповідає і-те обмеження вихідної задачі, і, навпаки, кожній змінній прямої задачі відповідає j-те обмеження двоїстої задачі. Матриця з коефіцієнтів при невідомих двоїстої задачі утворюється транспортуванням матриці А, складеної з коефіцієнтів при невідомих вихідної задачі. Якщо на j-ту змінну вихідної задачі накладена умова невід’ємності, то j-те обмеження двоїстої задачі буде нерівністю, в іншому випадку j-те обмеження буде рівністю; аналогічно пов’язані між собою обмеження вихідної задачі і змінні двоїстої.

Складаємо матрицю при невідомих вихідної задачі:


,


тоді матриця при невідомих двоїстої задачі матиме наступний вигляд:



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

Враховуючи все наведене, двоїста задача матиме наступний вигляд:



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



Завдання №4


Визначити оптимальний план транспортної задачі:

а) побудувати початковий опорний план методом "північно-західного" напрямку;

б) побудувати оптимальний план методом потенціалів:



Нехай в матриці А міститься інформація про кількість продукту в кожному місці виробництва, який необхідно доставити споживачам в кількості записаній в матриці В. Транспортні витрати, пов’язані з перевезенням одиниці продукту із одного місця виробництва одному споживачеві, записані в матриці С. Задані матриці і сказане вище для спрощення сприйняття узагальнимо в таблиці4.


Таблиця4–Поставка продукту із різних місць виробництва різним споживачам і пов’язані з цим витрати

Виробник

Споживач

Запаси продукту

8

3

3

4

60

5

2

7

5

20

5

4

8

2

30

7

1

5

7

20

Потреба в продукті

40

30

30

15

130

115


З таблиці4 видно, що запаси продукту у виробника на складах на 15 одиниць більші ніж необхідно споживачу, тобто маємо транспортну задачу з відкритою моделлю. Для розв’язку такої задачі введемо фіктивного споживача, якому необхідно отримати одиниць продукту. Всі тарифи на доставку продукту цьому споживачеві будемо вважати рівними нулю, і весь продукт потрібний цьому споживачеві залишаємо у місці виробництва. Для побудови початкового плану перевезень (таблиця5) використаємо метод "північно-західного" напрямку: заповнювати таблицю починаємо з лівого верхнього кута, рухаючись вниз по стовбцю або вправо по рядку (тарифи перевезень напишемо в правому верхньому куту кожної клітини, кількість продукту – в нижньому лівому). В першу клітину заносимо менше з чисел (min(40;60): 40. Тобто потреба в продукті першого споживача повністю задовільнено і інші клітини першого стовпця заповнювати не будемо. Рухаємося далі по першому рядку в другий стовпчик. В цю клітину записуємо менше з 30 і (60-40), тобто пишемо 20. Таким чином перший рядок заповнювати далі не будемо, оскільки запаси першого місця виробництва остаточно вичерпано: з нього ми повністю задовольняємо потребу у продукті першого споживача і частково (20 одиниць, а не 30) другого. Рухаємося по другому стовпчику на другий рядок. Сюди записуємо менше з (30-20) або 20: маємо 10, тобто другому споживачеві ми веземо 20одиниць продукту з першого місця виробництва і 10– з другого. Аналогічно заповнюємо інші клітини.


Таблиця5– Розподіл продукту по споживачам

Виробник

Споживач

Запаси продукту


8

3

3

4

0

60

40

20




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

1

-

-2

-2

-


З таблиці15 видно, що максимальне додатне значення отримали для клітини А2В1, тому заповнюємо її будуючи для неї цикл, який показано в таблиці14. Результат дій в таблиці16.


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

Виробник

Споживач

Запаси продукту



8

-

+

-

+

3

3

4

0

60

0

15


30


15

5

2

7

5

0

20

-3

10

10




5

4

8

2

0

30

-3

15



15


7

1

5

7

0

20

-4


20




Потреба в продукті

40

30

30

15

15

130

×

8

5

3

5

0

×

×


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




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

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


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


-

2

-

1

-

-

-

-7

-3

-3

-

-2

-8

-

-3

-3

-

-6

-6

-4


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


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

Виробник

Споживач

Запаси продукту



8

+

-

+

-

3

3

4

0

60

0

5

10

30


15

5

2

7

5

0

20

-3

20





5

4

8

2

0

30

-3

15



15


7

1

5

7

0

20

-2


20




Потреба в продукті

40

30

30

15

15

130

×

8

3

3

5

0

×

×



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



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


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


-

-

-

1

-

-

-2

-7

-3

-3

-

-4

-8

-

-3

-1

-

-4

-4

-2


Оскільки в результаті розрахунків отримали додатне значення в єдиній клітині А1В4, то будуємо цикл і заповнюємо її. Новий план зображено в таблиці20.


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

Виробник

Споживач

Запаси продукту



8

3

3

4

0

60

0


10

30

5

15

5

2

7

5

0

20

-2

20





5

4

8

2

0

30

-2

20



10


7

1

5

7

0

20

-2


20




Потреба в продукті

40

30

30

15

15

130

×

7

3

3

4

0

×

×


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


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


-1

-

-

-

-

-

-1

-6

-3

-2

-

-3

-7

-

-2

-2

-

-4

-5

-2


Рішення, зображене в таблиці20 є оптимальним, оскільки для кожної незайнятої клітини сума потенціалів менша вартості перевезень, що знаходиться у відповідній клітинці. Транспортні витрати по оптимальному плану перевезень становлять:



Знайдений оптимальний план покращив результат діяльності у порівнянні з початковим (зменшив транспортні витрати) на 685-380=305гривень.



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


  1. Кузнецов Ю.Н. Математическое программирование. Учебное пособие для вузов– М.: Высшая школа, 1976.– 352с.

  2. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программированию.– Мн.: Высш. школа, 1978.– 256с.



Случайные файлы

Файл
poligraf.doc
91485.rtf
28858.rtf
10372-1.rtf
104192.rtf




Чтобы не видеть здесь видео-рекламу достаточно стать зарегистрированным пользователем.
Чтобы не видеть никакую рекламу на сайте, нужно стать VIP-пользователем.
Это можно сделать совершенно бесплатно. Читайте подробности тут.