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

СОДЕРЖАНИЕ: Методи зведення до канонічної форми задач лінійного програмування. Визначення шляхів знаходження екстремумів функцій графічним способом. Побудова початкового опорного плану методом північно-західного напрямку. Складання двоїстої системи матриць.

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

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

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

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

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

Варіант 06

Чернігів 2009

Зміст

Завдання №1

Завдання №2

Завдання №3

Завдання №4

Завдання №5

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

Завдання №1

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

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

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

і нерівності

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

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

, в якому

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

Завдання №2

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

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

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

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

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

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

Завдання №3

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

Для перетворення нерівностей в рівності вводимо змінні одиничні матриці х₃ , х₄ і х₅ . Для розв’язку задачі симплексним методом необхідно мати три одиничних матриці при невід’ємних правих частинах рівнянь. Для отримання одиничної матриці в першій і третій нерівностях вводимо введемо штучні змінну х₆ і х₇ та отримаємо одиничні матриці А₆ і А₇ . Де

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

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

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

де

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

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

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

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

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

Базис	С базису	А₀
Базис	С базису	А₀	х₁	х₂	х₃	х₄	х₅	х₆	х₇
х₆	М	8	1		-1	0	0	1	0
х₄	0	20	3	4	0	1	0	0	0
х₇	М	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

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

;

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

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

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

Базис	С базису	А₀
Базис	С базису	А₀	х₁	х₂	х₃	х₄	х₅	х₆	х₇
х₂	2	2,67	0,33	1	-0,33	0	0	0,33	0
х₄	0	9,33	1,67	0	1,33	1	0	-1,33	0
х₇	М	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. Тоді вектор А₁ включаємо в базис, а вектор А₇ виключаємо з нього.

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

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

Базис	С базису	А₀
Базис	С базису	А₀	х₁	х₂	х₃	х₄	х₅	х₆	х₇
х₂	2	2,25	0	1	-0,375	0	0,125	0,375	-0,125
х₄	0	7,25	0	0	1,125	1	0,625	-1,125	-0,625
х₁	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				60
	5	2	7	5	0	20
	10	10				20
	5	4	8	2	0	30
	20	10				30
	7	1	5	7	0	20
	5	15				20
Потреба в продукті	40	30	30	15	15	130

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

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

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

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	40	20				60	0
	5	2	7	5	0	20	-1
	10	10				20	-1
	5	4	8	2	0	30	0
	20	10				30	0
	7	1	5	7	0	20	5
	5	15				20	5
Потреба в продукті	40	30	30	15	15	130
	8	3	8	2	-5

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

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

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

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	40	20				60	0
	5	2	7	5	0	20	-1
	10	10				20	-1
	5	4	8	2	0	30	0
	15	15				30	0
	7	1	5	7	0	20	-3
	5	15				20	-3
Потреба в продукті	40	30	30	15	15	130
	8	3	8	2	3

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

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

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

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	-
	40	10	10			60	-
	5	2	7	5	0	20	-1
	20					20	-1
	5	4	8	2	0	30	5
	15	15				30	5
	7	1	5	7	0	20	2
	5	15				20	2
Потреба в продукті	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), А₃ В₁ (8), А₃ В₂ (4), А₃ В₅ (3), А₄ В₁ (3) і А₄ В₂ (4). Максимальне значення max(2;8;4;3;3;4)=8в клітині А₃ В₁ , тому заповнюємо і цикл будуємо для неї (цикл показано в таблиці8, результат дій в таблиці10).

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	25	10	25			60	0
	5	2	7	5	0	20	-1
	20					20	-1
	5	4	8	2	0	30	-3
	15	15				30	-3
	7	1	5	7	0	20	2
	5	15				20	2
Потреба в продукті	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), А₂ В₁ (2), А₄ В₁ (3), А₄ В₂ (4). Заповнюємо клітину А₄ В₂ і будуємо опорний план (таблиця12).

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	25	5	30			60	0
	5	2	7	5	0	20	-1
	20					20	-1
	5	4	8	2	0	30	-3
	15	15				30	-3
	7	1	5	7	0	20	-2
	5	15				20	-2
Потреба в продукті	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	-

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

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

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	25	30	5			60	0
	5	2	7	5	0	20	-1
	20					20	-1
	5	4	8	2	0	30	-3
	15	15				30	-3
	7	1	5	7	0	20	0
	10	10				20	0
Потреба в продукті	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 видно, що максимальне додатне значення отримали для клітини А₂ В₁ , тому заповнюємо її будуючи для неї цикл, який показано в таблиці14. Результат дій в таблиці16.

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	15	30	15			60	0
	5	2	7	5	0	20	-3
	10	10				20	-3
	5	4	8	2	0	30	-3
	15	15				30	-3
	7	1	5	7	0	20	-4
	20					20	-4
Потреба в продукті	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 не є оптимальним, оскільки отримали додатні значення в клітинах А₁ В₂ (2) і А₁ В₄ (1). Заповнюємо клітину А₁ В₂ і будуємо опорний план (таблиця18).

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	5	10	30	15		60	0
	5	2	7	5	0	20	-3
	20					20	-3
	5	4	8	2	0	30	-3
	15	15				30	-3
	7	1	5	7	0	20	-2
	20					20	-2
Потреба в продукті	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

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

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

Виробник	Споживач					Запаси продукту
Виробник						Запаси продукту
	8	3	3	4	0	60	0
	10	30	5	15		60	0
	5	2	7	5	0	20	-2
	20					20	-2
	5	4	8	2	0	30	-2
	20	10				30	-2
	7	1	5	7	0	20	-2
	20					20	-2
Потреба в продукті	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с.

Скачать архив с текстом документа