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


Придбати:23.70 грн.*

Ціна "Знижена". (Для України )

SMS: завантажити матеріал, 30грн.


з урахуванням ПДВ Додатково утримується збір в Пенсійний фонд у розмірі 7,5% від вартості послуги з урахуванням ПДВ
 online для України

SMS: скачать материал 

 online для Российской Федерации

Зміст :

1.Теоретичні відомості
1.1 Транспортні задачі
Класична транспортна задача. Нехай задано m пунктів виробництва деякого однорідного продукту та n пунктів споживання цього продукту. Відомо запаси продукту в кожному пункті виробнику, а також попит кожного пункту споживача, витрати на перевезення Cij одиниці продукції від і-того виробника до j-того споживача. Складемо план перевезень продукції при якому запаси кожного постачальника були б вивезені, а попит кожного споживача був би задоволений і затрати на перевезення були б мінімальні.
Побудуємо модель цієї задачі.
j
i
1
2
...
n
а
1

...


2

...


... ... ... ... ... ...

m

...


b

...



Xij – шуканий об’єм перевезення від постачальника до споживача. Елементи Xij які будуть визначати план перевезень будемо розглядати, як компоненти матриці розмірності m x n.
Дану матрицю назвемо матрицею перевезень. Витрати які пов’язані з певним перевезенням складатимуть величину Cij Xij .
Загальна вартість перевезень від постачальників до споживачів визначається виразом
Згідно постановки задачі план перевезень повинен бути складений таким чином, щоб об’єм вивезення від кожного постачальника дорівнював б запасу продукції.
Характер змінних висуває на них умову невід’ємності. В результаті отримаємо математичну модель транспортної задачі. Для перевірки сумісності просумуємо рівність Xij = по індексу, а Xij = по „j”. Отримаємо, що = . Сумарні запаси повинні дорівнювати сумарному попиту. Задачі для яких виконується умова = називаються задачами з правильним балансом або закритою транспортною задачею, якщо ця умова порушена то транспортна задача називається відкритою. Тут можливі два випадки, коли сумарні запаси > сумарний попит та коли сумарний попит > сумарні запаси.
Властивості:
1. транспортна задача завжди має оптимальний план.
2. у транспортній задачі завжди існує допустимі плани які містять не більше m+n-1 додатних компонентів.
3. якщо в транспортній задачі елементи та цілі то вона має оптимальний цілочисельний план.


1.2 Методи пошуку початкового опорного плану.
Існує чотири методи пошуку початкового опорного плану:
1. Діагональний метод
2. Метод найменшої вартості
3. Метод усереднених коефіцієнтів
4. Метод потенціалів
Розглянемо два методи пошуку початкового опорного плану, ті які ми використаємо в практичній частині лабораторної роботи, метод найменшої вартості та метод потенціалів.
Метод найменшої вартості.
Даний метод відрізняється від діагонального методу лише послідовністю заповнення клітинок. Клітинки починають заповнювати з тієї де вартість на перевезення мінімальна, тобто найменша, далі рухаємося поступово збільшуючи її.
Метод потенціалів
Алгоритм методу потенціалів:
Крок 1. В кожному стовпцю і кожному рядку таблиці транспортної задачі надають деяких чисел (потенціалів) виходячи з цін Cij, - потенціали для рядків, - потенціали для стовпців. + = Cij .
Потенціали згідно рівності + = Cij визначаються лише по заповненим клітинкам. Оскільки заповнених клітинок є n+m-1, а потенціалів m+n то один з потенціалів визначаємо довільно, а решту знаходять за рівністю + = Cij .
Крок 2. Для порожніх клітинок (які відповідають вільним змінним) обчислюють умовні ціни . Умовну ціну визначають у верхньому лівому куті відповідної клітинки.
Крок 3. Для порожніх клітинок знаходимо оцінки, які різницю між дійсними та умовними числами . За допомогою вказаних оцінок визначаємо оптимальність плану перевезень оптимальної задачі. Якщо всі оцінки додатні то план є оптимальним – задача розв’язана. Якщо хоча б одна оцінка від’ємна – план необхідно покращувати далі.
Крок 4. Якщо в плані є від’ємні оцінки вибираємо найменшу з них і для відповідної клітинки виконуємо цикл перерахунку. Такий цикл матиме вигляд замкнутої ламаної в одному з кутів якої знаходиться клітинка з найменшою оцінкою, а в іншому заповнені клітинки які приймають участь у перерозподілі. При побудові циклу виходять із заповненої клітинки і повертаються до неї по ламаній, при чому поворот можна робити тільки у заповнених клітинках. Нехай у несприятливу клітинку необхідно помістити k – одиниць продукції. Для уникнення дисбалансу в таблиці при циклічних переходах в заповнених клітинках почергово додають та віднімають відповідний об’єм продукції (k) . Оскільки цикл міститиме парну кількість кутів то половина клітинок буде з знаком „+” , а половина з знаком „-” .
Крок 5. Після перерахунку по циклу повертаємося до кроку 1. Так триває до тих пір доки всі оцінки виявляться додатними.
Висновок:
Виконуючи лабораторну роботу №3 при виконані транспортної задачі методом найменшої вартості у мене вийшло, що Z=1520. Але при розв’язані задачі методом потенціалів у мене виходили від’ємні оцінки, тому я мусив робити цикл перерахунків. В результаті за методом потенціалів Z=1760, що на 240 більше ніж за методом найменшої вартості.

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

-

Код матеріалу (ID)
2445
Цей номер ми використовуємо для того щоб швидко знайти матеріал по архіву. В багатьох випадках під час спілкування з вами ми будемо просити назвати код матеріалу, а не назву.
В базі від
11 декабря 2009
Ми періодично доповнюємо наш архів. Ця дата вказує не те, коли ми почали публікувати матеріал на сайті.
Популярність

Кількість переглядів даної сторінки
Об'єм
12 стр.
Ми вказуємо кількість сторінок, на яких розміщений матеріал. У випадках, якщо матеріал знаходиться в декількох електроних файлах( doc, rtf, xls), ми вказуємо сумарну кількість.
Розділ
Математичне програмування / Доклад

* - Ціна актуальна для наступних видів оплати: банківскі платежі, електронні платіжні системи в Інтернет. При оплаті з допомогою SMS та мобільних переказів діють різні тарифи в залежності від розміру матеріалів (див. в посиланні на GSM операторів)

Вкажіть першу літеру для швидкого переходу:

А  Б  В  Г  Д  Е  З  І  К  Л  М  О  П  Р  С  Т  У  Ф  Х  Ц  Н