Рефетека.ру / Математика

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

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

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

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


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

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

Варіант 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гривень.


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


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

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

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

  1. • Розв"язання задач лінійного програмування
  2. • Математичне програмування в економіці
  3. • Стандартна задача лінійного програмування
  4. • Економічні задачі лінійного програмування і методи їх ...
  5. • Побудова та реалізація економіко-математичної ...
  6. • Аналіз чутливості використання методу Якобі для ...
  7. • Чисельні методи розв"язування крайових задач для ...
  8. • Побудова математичної моделі задачі лінійного ...
  9. • Моделювання теплових процесіів в елементах енергетичного ...
  10. • Особливості емоційної регуляції процесу розв"язування ...
  11. • Будування математичної моделі економічної задачі ...
  12. • Чисельне розв"язання задач оптимального керування
  13. • Метод динамічного програмування
  14. • Розв'язання задач графічним методом, методом ...
  15. • Розв"язання задачі Коші для звичайного ...
  16. • Розвиток умінь розв"язувати задач на пропорційне ...
  17. • Розв'язок задач лінійного програмування ...
  18. • Розв'язування систем лінійних рівнянь методом Гауса
  19. • Метод "Стрілянини"
Рефетека ру refoteka@gmail.com