Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
МІНІСТЕРСТВО АГРАРНОЇ ПОЛІТИКИ УКРАЇНИ
Білоцерківський державний аграрний університет
ЕКОНОМІЧНИЙ ФАКУЛЬТЕТ
Кафедра інформаційних систем і технологій
МАТЕМАТИЧНЕ
ПРОГРАМУВАННЯ
(Модуль 1)
Робочий зошит для вивчення дисципліни студентами економічного факультету за модульно-рейтинговою системою навчення
Біла Церква
2006
УДК 681.3.06 Затверджено
методичною комісією економічного факультету
(Протокол № 4 від 22.12.2005 р.)
Укладачі: О.С. Бондар – к.е.н., М.І. Трофимчук – к.е.н., А.Ф Чеборака, О.Ю Углова, С.І. Романенко, О.В. Савчук, О.В. Лісовий, О.Б. Яломистий, В.І. Кармазін - асистенти
Анотація
Математичне програмування: Робочий зошит для вивчення дисципліни студентами економічного факультету за модульно-рейтинговою системою навчання. Модуль 1/
, О.С. Бондар, М.І. Трофимчук – к.е.н., А.Ф Чеборака, О.Ю Углова. – Біла Церква, 2006. – 44
Рецензент канд. екон. наук А.А. Ільєнко
© БДАУ, 2006
Предметом вивчення курсу "Математичне програмування" є способи математичної формалізації економічних систем і методи знаходження оптимальних планів їх діяльності. Мета курсу - дати студентам математичну підготовку, яка дозволяє будувати математичні моделі і обирати оптимальні рішення для організації управління економічними процесами.
При вивченні математичного програмування передбачається модульно-рейтингова оцінка знань студентів за 100 бальною шкалою, в основі якої лежить структурно-модульна схема. Набрана студентом кількість балів є відповідним еквівалентом для одержання підсумкової оцінки з навчального предмета:
|
№ п/п |
Назва теми |
Кількість годин |
|
|
Лекції |
Лаб.-практичні |
||
|
1 |
2 |
3 |
4 |
|
І. |
Модуль 1. Задачі дослідження операцій та їх класифікація. Геометрична інтерпритація загальної задачі лінійного програмування. Симплексний метод розв'язування задач лінійного програмування. Симплексний метод з штучним базисом (М - метод.) Теорія двоїстості в лінійному програмуванні. |
12 |
8 |
|
Тема 2. Задачі дослідження операцій та їх класифікація. Місце математичного програмування в розв’язуванні задач дослідження операцій. Основна задача ЛП. Загальні відомості про лінійне програмування. Загальна задача лінійного програмування. Основна задача лінійного програмування. Основні поняття. Економічна постановка задачі лінійного програмування. Математичне формулювання задачі лінійного програмування.. |
2 |
||
|
1 |
2 |
3 |
4 |
|
Тема 3. Геометрична інтерпритація загальної задачі лінійного програмування. ОЗЛП. Поняття симплекса. Графічний спосіб розв'язування ОЗЛП з двома змінними. Особливості розв'язування задач лінійного програмування з великою кількістю змінних Визначення області допустимих розв'язків Побудова вектора-нормалі і визначення оптимального розв’язку у області допустимих розв’язків Економічна інтерпретація геометричного розв’язку задачі лінійного програмування |
2 |
2 |
|
|
Тема 4. Симплексний метод розв'язування задач лінійного програмування. Ідея методу, область визначення. Алгоритм простого (прямого) симплекс -методу. Побудова опорного (базисного) розв'язку задачі. Ознаки оптимальності опорних планів Ознаки необмеженості цільових функцій в допустимій області Ознаки наявності нескінченної множини оптимальних планів Ознаки оптимальності розв'язку. Вироджені плани задачі лінійного програмування та проблеми зациклення Алгоритм симплексного методу розв’язання не вироджених задач лінійного програмування Особливі випадки застосування симплекс-метода. Методика інтерпретації симплекс - таблиць. Аналіз моделі на стійкість. |
2 |
2 |
|
|
1 |
2 |
3 |
4 |
|
Тема 5. Симплексний метод з штучним базисом (М - метод.) Метод з штучним базисом. Ідея методу, область визначення. Алгоритм М - методу (методу великих штрафів). Ознаки оптимальності розвитку ОЗЛП М -методом. Практичне застосування. |
2 |
2 |
|
Тема 6. Теорія двоїстості в лінійному програмуванні. Постановка прямої та двоїстої задач лінійного програмування. Правила побудови математичних моделей прямої та двоїстої (симетричної) задач лінійного програмування. Симетричні та несиметричні двоїсті задачі. Теореми двоїстості та їх економічний зміст. Інтерпретація двоїстих оцінок в ЗЛП. Постоптимальний аналіз лінійних моделей. |
2 |
2 |
|
Форма контролю |
К-ть заходів |
Оцінка |
Сума балів |
||
|
max |
min |
max |
min |
||
|
Модуль 1 |
|||||
|
1. Семінари |
4 |
5 |
3 |
20 |
12 |
|
2. Реферати |
1 |
5 |
3 |
5 |
3 |
|
3. Контрольна робота |
2 |
5 |
3 |
10 |
6 |
|
4. Виступ |
1 |
5 |
3 |
5 |
3 |
|
Всього: |
40 |
24 |
МОДУЛЬ 1
Всього навчальних годин – 28
з них: лекційних – 12
практичних – 8
самостійна робота – 10
Порядок опрацювання завдань
Місце проведення: аудиторії згідно з розкладом.
Місце опрацювання: бібліотека, комп’ютерні аудиторії, ресурсний цент.
Місце та час отримання консультацій: за графіком здачі модуля.
Забезпечення занять: комп’ютерні програми, пакет прикладних програм МS Office, мережа Інтернет.
РЕКОМЕНДОВАНА ЛІТЕРАТУРА
Основна
1.Аллен Рой. Математическая экономия. - М.: Мир, 1964.
2.Бадевиц 3. Математическая оптимизация в социалистическом сельском хозяйстве / Пер. с нем. Н.А. Чупеева; под ред. и с предисл. Р.Г. Кравченко.- М.: Колос, 1982.
3.Гасс С. Линейное программирование (методы и приложения). -М.: Госуд. изд-во физ. - мат. лит-ры, 1961.
5.Гатаулін А.М., Гаврилов Г.В., Харитонова Л.А. Економіко -матиматичні методи в плануванні сільськогосподарського виробництва. - К.: Вища шк., 1989.
6.Гатулин А.М., Гаврилов Г.В., Харитонова Л.А. Экономикс -математические методы в планировании сельскохозяйственного производства. - М.: агропромиздат,1986.
9.Канторович Л.Г., Горстко А.Б. Оптимальные решения в економике. - М.: наука, 1972.
10.Лотов А.В. Введение в экономике - математическое моделирование. - М.: Наука, 1984.
11.Кузнецов Ю.Н., Кузнецов В.И., Волощенко А.Б. Математическое программирование. - М.: Высш. шк., 1976.
12.Математическое моделирование экономических процессов в сельском хозяйстве / Гатаулин А.М., Гаврилов Г.В., Сорокина Т.М. и др., Под ред. А.М. Гатаулина. - М.: Агропромиздат,1990.
17. Практикум по математическому моделированию экономических процессов в сельском хозяйстве / Под ред. А.Ф. Карпенко. - М.:Агропромиздат, 1985.
18.Степанюк В.В. Методи математичного програмування. - К.: Вища шк., 1984.
19.Тунеев М.М., Сухачов В.Ф. Экономико - математические методы в организации и планировании сельскохозяйственного производства. – М.: Колос, 1986.
Додаткова
Вагнер Г. Основы исследования операций. Том 2 и 3. - М.:
Мир.1973.
Ермаков С.М., Жиглявский А.А. Математическая теория оптимального експеримента. - М.: Наука, 1987. - 320 с.
3айченко Ю.П. Исследование операций. - Киев: Высш.шк., 1988-552 с.
Графічний метод застосовують, як правило, для розв'язання задач лінійного програмування з двома змінними. Він спирається на геометричну інтерпретацію загальної задачі лінійного програмування та властивості її розв'язку:
1) оптимальний розв'язок, якщо він існує, лежить на границі області припустимих розв'язків;
2) щоб знайти оптимальний розв'язок, необхідно рухатись від однієї точки до іншої у напрямі зменшення (мінімуму), та зростання (максимуму) функції мети.
Задача лінійного програмування має такий вигляд:
,
,
. . . . . . . . . . . . . . . . . . .
,
Тоді схему алгоритму графічного методу послідовно можна подати таким чином:
1) побудувати область припустимих розв'язків R, виходячи з обмежень задачі;
2) побудувати вектори нормалі і функції Z;
3) зміщувати пряму паралельно самій собі у напрямі вектора (в іншому напрямі, якщо шукаємо мінімум Z) доти, поки вона не буде проходити через крайню точку області R, найбільш віддалену (найменш віддалену – у випадку ) від початку координат.
При цьому можуть бути три випадки:
a) вектор-функція Z та одна із сторін області припустимих розв'язків R паралельні; в цьому випадку цільова функція досягає оптимального значення в будь-якій точці цієї сторони, тобто існує нескінченна множина оптимальних розв'язків задачі;
б) вектор-функція Z та область R мають одну крайню точку, координати якої визначають єдиний оптимальний розв'язок;
в) у напрямі вектора область припустимих розв'язків не обмежена; в цьому випадку задача не має розв'язку;
4. Обчислення координат крайньої точки та значення цільової функції.
Практичні завдання
Задача №1
Компанія виробляє продукцію двох видів А і В. Обидві потребують роботи
двох цехів: збирального і оздоблювального. Відомості про виробництво:
|
Цех |
Продукція |
Разом необхідно робочих годин |
|
|
А |
В |
||
|
Збиральний |
3 |
5 |
15 |
|
Оздоблювальний |
5 |
2 |
10 |
|
Валовий прибуток на одиницю |
5 |
32 |
Компанія зацікавлена в найбільшій прибутковості цих комбінацій продукції. Знайти скільки треба виробляти продукції А і В, щоб валовий прибуток був максимальний. (кількість робочих годин збільшується на номер варіанту).
Задача № 2
Для виробництва товарів А і В підприємство використовує два види сировини І і ІІ. Витрати сировини на виробництво товарів наведені в таблиці.
|
Сировина |
Витрати сировини на виробництво товару |
|
|
А |
В |
|
|
І |
1 |
а |
|
ІІ |
b |
1 |
Кількість на складі кожного виду сировини: І – a ( b+1) одиниць; ІІ – b (a+1) одиниць. При реалізації одиниця товару А приносить прибуток b+2 грн., одиниця товару В – а грн.. Спланувати виробництво таким чином, щоб сумарний прибуток був максимально можливим. ( a =№ варіанту + 3, b = № варіанту + 7 )
Задача № 3
Знайти графічним методом мінімум і максимум лінійної функції
F(x1,x2)=a x1 + b x2
в області, що визначена системою обмежень
x1 + a x2 < a + ab,
b x1 + x2< b + ab
x1 0 ; x2 0. ( a =№ варіанту + 7 , b = =№ варіанту + 9 )
Задачі для самостійного розв’язання
Задачі
Розв’язати графічним методом задачі лінійного програмування:
|
1 |
2 |
3 |
|||
|
4 |
5 |
6 |
|||
|
7 |
8 |
9 |
|||
|
10 |
11 |
max Z = 8x1+6x2 3x1+5x211 4x1+x28 x10 , x20 |
12 |
max Z = 3x1+4x2 3x1+2x28 x1+4x210 x10 , x20 |
Питання для самоконтролю
Ідея методу, область визначення. Алгоритм методу. Побудова опорного плану. Ознаки оптимальності опорного плану. Особливі випадки застосування симплекс-методу. Інтерпретація симплекс-таблиці – аналізу моделі на стійкість.
Ідея методу, область визначення. Алгоритм методу. Ознаки оптимальності. Практичне застосування.
Приклад
Підприємство виробляє однорідну продукцію, при цьому використовує три технологічні засоби. Витрати ресурсів за одиницю часу при відповідній технології та продуктивності кожної технології в гривнях за одиницю часу наведено в таблиці:
|
РЕСУРСИ |
ТЕХНОЛОГІЧНІ ЗАСОБИ |
ОБСЯГ РЕСУРСІВ |
|||
|
№ |
Т1 |
Т2 |
Т3 |
||
|
1 |
Робоча сила, людино-год. |
15 |
20 |
100 |
1500 |
|
2 |
Попит, т |
1 |
2 |
3 |
200 |
|
3 |
Електроенергія, квт/год |
10 |
20 |
10 |
2000 |
|
4 |
Продуктивність технологічних засобів, грн. |
500 |
400 |
300 |
Необхідно визначити інтенсивність використання технологічних засобів.
Рішення:
Економіко математична модель задачі матиме такий вигляд:
Цільова функція:
Z = 500 x1 + 400 x2 + 300 x3 max,
Обмеження:
(хj 0 ; j = 1,3 )
Зведемо систему обмежень до канонічного вигляду:
15х1 + 20х2 + 100х3 + х4 = 1500
х1 + 2х2 + 3х3 + х5 = 200
10х1 + 20х2 + 10х3 + х6 = 200
Z = 500х1 + 400х2 +300х3 + 0х4 + 0х5 + 0х6 max
Опорний план:
х4 = 1500
х5 = 200
х6 = 200
Z = 0
Ресурси є, але виробництво не ведеться. Тому прибуток дорівнює нулю.
Виходячи з опорною плану побудуємо першу симплексну таблицю:
|
№ |
Базисні змінні |
Сі |
Вільні члкни |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
Симплексні відношення |
|
1 |
х4 |
0 |
1500 |
15 |
20 |
100 |
1 |
0 |
0 |
100 |
|
2 |
х5 |
0 |
200 |
1 |
2 |
3 |
0 |
1 |
0 |
200 |
|
3 |
х6 |
0 |
2000 |
10 |
20 |
10 |
0 |
0 |
1 |
200 |
|
Z |
0 |
-500 |
-400 |
-300 |
0 |
0 |
0 |
Друга симплексна таблиця:
|
№ п/п |
Базисні змінні |
Сі |
Вільні члени |
Х1 |
Х2 |
Х3 |
Х4 |
Х5 |
Х6 |
|
1 |
Х1 |
500 |
100 |
1 |
1,33 |
6,67 |
0,067 |
0 |
0 |
|
2 |
Х5 |
0 |
100 |
0 |
0,67 |
-3,67 |
-0,067 |
1 |
0 |
|
3 |
Х6 |
0 |
1000 |
0 |
6,67 |
-56,67 |
-0,67 |
0 |
1 |
|
Z |
50000 |
0 |
266,67 |
3033,33 |
33,33 |
0 |
0 |
Так як в Z – рядку усі елементи невід’ємні, то в другій таблиці отримано оптимальний розв’язок.
Технологічні засоби Т2 і Т3 використовувати недоцільно. Найбільший прибуток 50000 грн. дасть використання 100 одиниць технологічних засобів Т1
Попит залишиться недовикористаним у кількості 100 т.
Електроенергія залишиться недовикористаною у кількості 1000 квт / год.
Аналіз останньої симплексної таблиці.
Якщо до оптимального п лану ввести одну одиницю технологічного засобу Т2 , то доцільно зменшити використання технологічного засобу Т1 на 1,33 одиниці. Попит зменшиться на 0,67 т, а використання електроенергії зменшиться на 6,67 квт / год. Прибуток збільшиться на 266,67 грн.
Якщо до оптимального плану ввести одиницю технологічного засобу Т3, то доцільно зменшити використання технологічного засобу Т1 на 6,67 одиниць.
При цьому попит збільшиться на 3,67 т, а використання електроенергії збільшиться на 56,67 квт / год. Прибуток при цьому зросте на 3033,33 грн.
Якщо ресурси робочої сили збільшити на 1 людино-год., то доцільно збільшити використання технологічного засобу Т1 на 0,067 одиниць. При цьому попит збільшиться на 0,067 т, а використання електроенергії збільшиться на 0,67 квт / год. Прибуток зросте на 33,33 грн.
Практичні завдання
Скласти математичну модель і розв’язати відповідну оптимізацій ну задачу.
1. Для пошиття спідниці і сукань швейний цех має 96м тканини. На пошиття однієї сукні витрачають 3м тканини і 1,8 год роботи устаткування, а на пошиття однієї спідниці – 2м тканини і 0,6 год роботи устаткування. Час роботи устаткування обмежений 45 год на тиждень. Прибуток від продажу однієї сукні становить 18 грн, а однієї спідниці – 10 грн. Визначити щотижневий план виробництва, який забезпечує найбільший прибуток від реалізації торгових виробів, якщо суконь потрібно виготовити щонайбільше 20, а спідниць – щонайбільше 30.
2. Відомо, що відгодівля худоби економічно вигідна, якщо кожна тварина отримує на день щонайменше 6 одиниць споживчої речовини А, 12 одиниць речовини В і 4 одиниці речовини С. Для відгодівлі худоби використовують два види кормів. Споживчу цінність 1 кг кожного виду корму наведено в таблиці.
|
Вид корму |
Споживча цінність 1 кг споживчої речовини |
||
|
А |
В |
С |
|
|
І |
2 |
2 |
0 |
|
ІІ |
1 |
4 |
4 |
Вартість 1 кг корму І становить 50 коп., корму ІІ – 60 коп. Скільки необхідно використати кожного виду корму, щоб витрати були найменшими?
3. Підприємство виробляє два види продукції, для чого використовується три види ресурсів. Для виготовлення одиниці продукції першого виду необхідно витратити 3 одиниці ресурсу А, 2 одиниці ресурсу В і 1 одиницю ресурсу С, а для виготовлення одиниці продукції другого виду – 2 одиниці ресурсу А, 3 одиниці ресурсу В і 1 одиниця ресурсу С . Запаси ресурсів А, В і С становлять відповідно 101, 99 і 37 одиниць. визначити, скільки одиниць продукції кожного виду потрібно виробити, щоб отримати максимальний прибуток, якщо кожна одиниця продукції першого виду має прибуток 27 грн, другого виду – 24 грн.
4. Для відгодівлі худоби використовують два види кормів. у кожному кілограмі корму І міститься 5 одиниць споживчої речовини А і 2,5 одиниці споживчої речовини В, а у кожному кілограмі корму ІІ – по 3 одиниці споживчих речовин А і В. Встановлено, що відгодовувати тварин вигідно лише тоді, коли їх денний раціон становитиме щонайменше 30 одиниць споживчої речовини А і 22,5 одиниці споживчої речовини В. Відомо, що вартість (споживча цінність 1 кг) кожного виду корму – 1 грн. Визначити, скільки корму кожного виду треба використовувати щоденно, щоб витрати були щонайменшими за зазначених умов відгодовування?
5. Для збереження здоров’я і працездатності людини повинна споживати щодня таку норму поживних речовин: - А щонайменше 4 мг, В і D – по 6 мг, С – 9 мг. У щоденному раціоні є два види продуктів. Вміст у 1 кг кожного виду продукту поживних речовин такий: А – відповідно 2 і 1 мг, В – 0 і 3 мг, С – 1 і 3 мг, D – 3 і 2 мг. Необхідно організувати щоденне харчування так, щоб його вартість була найменшою, а людина одержувала за добу зазначену норму поживних речовин.
6. На виробництво двох видів продукції потрібні чотири групи устаткування (див. таблицю). Необхідно організувати випуск продукції так. щоб прибуток від її реалізації був найбільшим.
|
Група виробничого устаткування |
Необхідна кількість устаткування для випуску одиниці продукції |
Кількість устаткування у групі |
|
|
І |
ІІ |
||
|
А В С Д |
2 1 4 0 |
3 2 0 4 |
12 8 16 12 |
|
Прибуток від реалізації |
2 |
3 |
7. Мале підприємство виготовляє два види виробів, які мають бути оброблені за певний час на кожному з верстатів І, ІІ і ІІІ (див. таблицю).
|
Виріб |
Час обробки виробу на верстаті, год |
||
|
І |
ІІ |
ІІІ |
|
|
А В |
0,5 0,25 |
0,4 0,3 |
0,2 0,4 |
Час роботи верстатів І, ІІ і ІІІ - відповідно до 40, 36 і 36 год на тиждень. Прибуток від реалізації одного виробу А і В – відповідно 5 і 3 грн. Визначити тижневі норми виробництва виробів А і В, при яких прибуток буде максимальний.
8. Для виробництва двох видів продукції використовують токарне, фрезерне та шліфувальне устаткування. Норми витрат часу на обробку одного виробу продукції та фонд робочого часу для кожного типу устаткування наведено в таблиці.
|
Тип виробничого устаткування |
Витрати часу на обробку одного виробу продукції, год |
Фонд робочого часу устаткування, год |
|
|
Фрезерне Токарне Шліфувальне |
10 5 6 |
8 10 12 |
168 180 144 |
|
Прибуток від реалізації одиниці продукції, грн |
14 |
18 |
Визначити план випуску продукції, що забезпечить найбільший прибуток.
Задачі для самостійного розв’язання
9. На меблевій фабриці зі стандартних листів фанери необхідно вирізати заготовки трьох видів у кількості відповідно 24, 31 і 18 шт. Кожний лист фанери можна розрізати для заготовки двома способами. Кількість отриманих заготовок при кожному способі розрізування, а також залишки фанери після розрізування наведено у таблиці.
|
Вид заготовки |
Кількість заготовок при розрізування за способом, шт |
|
|
першим |
другим |
|
|
I ІІ ІІІ |
2 5 2 |
6 4 3 |
|
Залишки фанери, см2 |
12 |
16 |
Визначити, яку кількість фанери і яким способом потрібно розрізати, щоб отримати бажану кількість заготовок з найменшими залишками.
10. У фермерському господарстві вирощують лисиць і нутрій. Для забезпечення нормальних умов відгодування використовують три види кормів. Кількість одиниць кормів, яку повинні отримувати лисиці та нутрії, і загальну кількість корму кожного виду наведено в таблиці.
|
Вид корму |
Кількість одиниць кормів для щоденного споживання |
Загальна кількість корму |
|
|
І |
2 4 6 |
3 1 7 |
180 240 426 |
|
Прибуток від реалізації однієї шкури, у.о. |
16 |
12 |
Визначити, скільки лисиць і нутрій треба вирощувати, щоб прибуток від реалізації хутра був найбільшим.
Задача 11.
Підприємство виготовляє письмові столи типів А, В, і С. Для одного столу типу А необхідно 2 м2 деревини, для столу типу В – 3 м2, а для столу типу С – 5 м2. Підприємство може отримати до 400 м2 деревини за тиждень. Для виготовлення одного столу типу А потрібно 12 хвилин роботи обладнання, для моделі типу В – 30 хв. Та для моделі типу С – 40 хв. Обладнання може використовуватися 3000 хв. На тиждень. Оцінено, що за тиждень може бути реалізовано до 550 столів.
Відомо, що прибуток від реалізації одного письмового столу типу А становить 30 дол., типу В – 40 дол., та типу С – 60 дол. Визначити, скільки столів кожного типу необхідно виготовляти за тиждень.
Необхідно:
Питання для самоконтролю
Правила побудови двоїстої задачі лінійного програмування:
Кожній задачі лінійного програмування можна поставити у відповідність іншу, пов’язану певним чином з початковою задачею. Такі задачі називають двоїстими, або спряженими. Спільний розгляд двоїстих пар задач дуже важливий в економічному аналізі оптимального плану. Відповідність між вихідною та двоїстою задачами полягає в побудові на основі першої задачі двоїстої до неї /як вихідна може розглядатися будь-яка зі спряженої пари задач/. Двоїсті задачі бувають симетричні і несиметричні.
Симетричні задачі
Початкова задача Двоїста задача
/1.10/ /1.10а/
/1.11/ /1.11а/
/1.12/ /1.12а/
Якщо обмеження вихідної задачі записано у вигляді рівнянь, то побудована до неї двоїста задача називається несиметричною. Водночас змінні можуть бути як додатні, так і від’ємні, тобто не виконується умова , а саме:
Розглянемо правила побудови двоїстої задачі.
Оптимальні розв’язки двоїстих задач тісно пов’язані між собою. Основою для їх аналізу є наведені далі теореми двоїстості.
Теорема 1.1. /Перша теорема двоїстості/. Якщо одна зі спряжених задач має оптимальний план, то його має й друга задача, причому значення цільових функцій збігаються, тобто .
Якщо цільова функція однієї із задач не обмежена на множині змінних, то друга задача розв’язку не має.
Оптимальний розв’язок двоїстої задачі знаходять за даними останьої симплексної таблиці вихідної задачі за формулою
, де - матриця-рядок двоїстих змінних ;
- матриця-рядок, складена з коефіцієнтів цільової функції для базисних змінних останньої симплексної таблиці вихідної задачі;
- матриця обернена до матриці В, складеної з компонентів базисних векторів останньої симплексної таблиці вихідної задачі.
Зауважимо, що для оптимального плану вихідної задачі матриця утворюється в останній таблиці відповідно стовпцям одиничної матриці першої симплексної таблиці. Змінні оптимального плану двоїстої задачі можна також дістати в рядку (m+1) останньої симплексної таблиці, де містяться оцінки вихідної задачі. Змінні оптимального плану двоїстої задачі розміщуються під відповідними одиничними векторами в рядку (m+1), причому їх значення дорівнюють .
Зауважимо, що визначається додаванням до відповідної оцінки коефіцієнтів . Вважаємо, що одинична матриця в початковій задачі утворена векторами .
Теорема 1.2. /Друга теорема двоїстості/. Якщо при підстановці компонентів оптимального плану в і - те або j - те обмеження вихідної /двоїстої/ задачі це обмеження виконується як рівняння, то відповідна змінна спряженої задачі буде строго більша від нуля, а коли воно виконується як строга нерівність, то відповідна змінна спряженої задачі дорівнює нулю.
Наведемо формальний запис цієї теореми для задач /1.10/ - /1.12/ і /1.10а/ - /1.12а/.
Нехай дано оптимальний план вихідної задачі у вигляді .
Тоді маємо:
якщо , то ;
якщо , то .
У разі, коли дано оптимальний план двоїстої задачі дістаємо:
якщо , то ;
якщо , то .
Теорема 1.3. /Третя теорема двоїстості./ Двоїсті оцінки показують приріст цільової функції, який зумовлюється малою зміною вільного члена відповідного обмеження:
або .
Приклад 1.1. Розв’язати двоїсту задачу, використовуючи розв’язок вихідної
Записуємо двоїсту задачу
Здобута пара задач несиметрична, оскільки обмеження вихідної задачі записані в канонічній формі. Отже, двоїсті змінні У - довільні /можуть бути як додатними, так і від’ємними або такими, що дорівнюють нулю/.
Задачі для самостійного розв’язання
Розв’язати задачу лінійного програмування, записати і розв’язати двоїсту до неї задачу.
|
1 |
2 |
3 |
|||
|
4 |
5 |
6 |
|||
|
7 |
8 |
9 |
|||
|
10 |
11 |
12 |
Питання для самоконтролю
Економічний сенс задачі, спряженої до задачі планування обсягів виробництва.
За яких умов спряжені задачі називаються симетричними?
Якими правилами необхідно користуватися, формулюючи спряжену симетричну задачу?
Як пов’язані оптимальні розв’язки спряжених задач?
Як пов’язані змінні вихідної та спряженої задач?
Як побудувати оптимальний план спряженої задачі за наявності такого плану вихідної задачі?
Що стверджують основні теореми спряженості?
Однорідний вантаж зосереджений у m постачальників в об'ємах . Даний вантаж необхідно доставити n споживачам в об'ємах . Відомі , i=1,2,,…,m, j=1,2,…,n- вартості перевезення одиниці вантажу від кожного I-го постачальника кожному j-му споживачу. Вимагається скласти такий план перевезень, при якому запаси всіх споживачів повністю задоволені і сумарні витрати на перевезення всіх вантажів мінімальні.
Початкові дані транспортної задачі звичайно записуються в таблиці (таб1.1).
|
|
… |
Початкові дані задачі можуть бути представлені також у вигляді вектора запасів постачальників А=((), вектора запитів споживачів
В=(() і матриці вартостей .
У транспортних задачах під постачальниками і споживачами розуміються різні промислові і сільськогосподарські підприємства, заводи, фабрики, склади, магазини і т.д. Однорідними вважаються вантажі, які можуть бути перевезені одним видом транспорту. Під вартістю перевезень розуміються тарифи, відстані, час, витрата палива і т.п.
2. Математична модель транспортної задачі.
Змінними (невідомими) транспортної задачі є i=1,2,,…,m, j=1,2,…,n – об'єми перевезень від кожного i-го постачальника кожному j-му споживачу. Ці змінні можна записати у вигляді матриці перевезень
.
Оскільки вираз визначає витрати на перевезення вантажу від i-го постачальника j-му споживачу, то сумарні витрати на перевезення всіх вантажів рівні . По умові задачі вимагається забезпечити мінімум сумарних витрат. Отже, цільова функція має вигляд .
Система обмежень задачі складається з двох груп рівнянь. Перша група з m рівнянь описує той факт, що запаси всіх m постачальників вивозяться повністю:
, i=1,2,…,m.
Друга група з n рівнянь виражає вимогу повністю задовольнити запити всіх n споживачів:
, j=1, 2, …, n.
Враховуючи умову позитивності об'ємів перевезень, математичну модель задачі можна записати так:
, (1)
, i=1,2,…,m, (2)
, j=1, 2, …, n, (3)
, i=1,2,,…,m, j=1,2,…,n (4)
У розглянутій моделі транспортної задачі передбачається, що сумарні запаси постачальників рівні сумарним запитам споживачів, тобто .
Така задача називається задачею з правильним балансом, а її модель – закритою. Якщо ж ця рівність не виконується, то задача називається задачею з неправильним балансом, а її модель – відкритою.
Математичне формулювання транспортної задачі таке: знайти змінні задачі , i=1,2,,…,m, j=1,2,…,n, задовольняючі системі обмежень (2), (3), умовам позитивності (4) і забезпечуючи мінімум цільової функції (1).
3. Методи побудови початкового опорного рішення.
Метод північно-західного кута.
Існує ряд методів побудови початкового опорного рішення, найпростішим з яких є метод північно-західного кута. У даному методі запаси чергового постачальника використовуються для забезпечення запитів чергових споживачів до тих пір, поки не будуть вичерпані повністю, після чого використовуються запаси наступного по номеру постачальника.
Заповнення таблиці транспортної задачі починається з лівого верхнього кута і складається з ряду однотипних кроків. На кожному кроці, виходячи із запасів чергового постачальника і запитів чергового споживача, заповнюється тільки одна клітка і відповідно виключається з розгляду один постачальник або споживач. Здійснюється це таким чином:
Нульові перевезення прийнято заносити в таблицю тільки тоді, коли вони потрапляють в клітинку (i,j), що підлягає заповненню. Якщо в чергову клітинку таблиці (i,j) вимагається поставити перевезення, а i-й постачальник або j-й споживач має нульові запаси або запити, то в клітинку ставиться перевезення, рівне нулю (базисний нуль), і після цього, як завжди, виключається з розгляду відповідний постачальник або споживач. Таким чином, в таблицю заносять тільки базисні нулі, решта клітинок з нульовими перевезеннями залишається порожніми.
Щоб уникнути помилок після побудови початкового опорного рішення необхідно перевірити, що число зайнятих клітинок рівне m+n-1 і вектори-умови, відповідні цим клітинкам, лінійно незалежні.
Теорема 4. Рішення транспортної задачі, побудоване методом північно-західного кута, є опорним.
Доказ. Число зайнятих опорним рішенням клітинок таблиці повинне бути рівне N=m+n-1. на кожному кроці побудови рішення по методу північно-західного кута заповнюється одна клітинка і виключається з розгляду один рядок (постачальник) або один стовпець (споживач) таблиці задачі. Через m+n-2 кроку в таблиці буде зайнято m+n-2 клітинки. В той же час залишаться невикресленими один рядок і один стовпець, при цьому незайнята клітинка одна. При заповненні цієї останньої клітинки число зайнятих клітинок складе m+n-2+1=m+n-1.
Перевіримо, що вектори, відповідні зайнятим опорним рішенням клітинкам, лінійно незалежні. Застосовний метод викреслювання. Всі зайняті клітинки можна викреслити, якщо виконати це у порядку їх заповнення.
Необхідно мати на увазі, що метод північно-західного кута не враховує вартість перевезень, тому опорне рішення, побудоване даним методом, може бути далеко від оптимального.
Метод мінімальної вартості.
Метод мінімальної вартості простий, він дозволяє побудувати опорне рішення, достатньо близьке до оптимального, оскільки використовує матрицю вартостей транспортної задачі С=((), i=1,2,,…,m, j=1,2,…,n. Як і метод північно-західного кута, він складається з ряду однотипних кроків, на кожному з яких заповнюється тільки одна клітка таблиці, відповідна мінімальній вартості min {{}, і виключається з розгляду тільки один рядок (постачальник) або один стовпець (споживач). Чергову клітку, відповідну , заповнюють за тими ж правилами, що і в методі північно-західного кута. Постачальник виключається з розгляду, якщо його запаси використані повністю. Споживач виключається з розгляду, якщо його запити задоволені повністю. На кожному кроці виключається або один постачальник, або один споживач. При цьому якщо постачальник ще не виключений, але його запаси рівні нулю, то на тому кроці, коли від даного постачальника вимагається поставити вантаж, у відповідну клітку таблиці заноситься базисний нуль і лише, потім постачальник виключається з розгляду. Аналогічно із споживачем.
Теорема 5. Рішення транспортної задачі, побудоване методом мінімальної вартості, є опорним.
7. Перехід від одного опорного рішення до іншого.
У транспортній задачі перехід від одного опорного рішення до іншого здійснюється за допомогою циклу. Для деякої вільної клітинки таблиці будується цикл, що містить частину клітинок, зайнятих опорним рішенням. По цьому циклу перерозподіляються об'єми перевезень. Перевезення завантажується у вибрану вільну клітинку і звільняється одна із зайнятих кліток, виходить нове опорне рішення.
Теорема 6. (про існування і єдиність циклу). Якщо таблиця транспортної задачі містить опорне рішення, то для будь-якої вільної клітинки таблиці існує єдиний цикл, що містить цю клітинку і частину клітинок, зайнятих опорним рішенням.
Доказ. Опорне рішення займає N=m+n-1 клітинок таблиці, яким відповідають лінійно незалежні вектори-умови. Якщо ж до зайнятих клітинок приєднати одну вільну, то відповідні їм m+n векторів лінійно залежні, і по тій же теоремі існує цикл, що містить цю клітинку. Припустимо, що таких циклів два (i1,j1), (i1,j2), (i2,j2), …, (ik,j1) і (i1,j1), (i2,j1), …, (i1,ji). Тоді, об'єднавши клітинки обох циклів без вільної клітинки (i1,j1), одержимо послідовність клітинок (i1,j2), …, (ik,j1), (i2,j1), …, (i1,ji), які утворюють цикл. Це суперечить лінійній незалежності векторів-умов, створюючих базис опорного рішення. Отже, такий цикл єдиний.
Зазначений цикл.
Цикл називається зазначеним, якщо його кутові клітинки пронумеровані по порядку і непарним клітинкам приписаний знак «+», а парним – знак «-» (рис 2.) 1 2
+ -
- 5 +
6
+ -
рис 2.
Зрушенням по циклу на величину називається збільшення об'ємів перевезень у всіх непарних клітинках циклу, відмічених знаком «+», на і зменшення об'ємів перевезень у всіх парних клітинках, відмічених знаком «-», на .
Теорема 7. Якщо таблиця транспортної задачі містить опорне рішення, то при зрушенні по будь-якому циклу, що містить одну вільну клітинку, на величину == вийде опорне рішення.
Доказ. У таблиці транспортної задачі, що містить опорне рішення, виберемо вільну клітинку і відзначимо її знаком «+». По теореме6. для цієї клітинки існує єдиний цикл, який містить частину клітинок, зайнятих опорним рішенням. Пронумеруємо клітинки циклу, починаючи з клітинки, відміченої знаком «+». Знайдемо == і здійснимо зрушення по циклу на цю величину.
У кожному рядку і в кожному стовпці таблиці, що входять в цикл, дві і лише дві клітинки, одна з яких відмічена знаком «+», а інша - знаком «-». Тому в одній клітинці об'єм перевезення збільшується на , а в іншій зменшується на , при цьому сума всіх перевезень в рядку (або стовпці) таблиці залишається незмінною. Отже, після зрушення по циклу як і раніше і запаси всіх постачальників вивозяться повністю, і запити всіх споживачів задовольняються повністю. Оскільки зрушення по циклу здійснюється на величину ==, то всі об'єми перевезень будуть ненегативними. Отже, нове рішення є допустимим.
Якщо залишити вільною одну з клітинок з нульовим об'ємом перевезення, відповідних , те число зайнятих клітинок буде рівне N=m+n-1. Оскільки цикл єдиний, те видалення з нього однієї клітинки розриває його. Цикл із зайнятих клітинок, що залишилися, утворити не можна, відповідні вектори-умови лінійно незалежні, а рішення є опорним.
8. Розподільний метод.
Один з найпростіших методів рішення транспортної задачі – розподільний метод.
Хай для транспортної задачі знайдене початкове опорне рішення і обчислене значення цільової функції на цьому рішенні Z((). По теоремі 6 для кожної вільної клітинки таблиці задачі можна побудувати єдиний цикл, який містить цю клітинку і частину клітинок, зайнятих опорним рішенням. Зазначивши цей цикл і здійснивши зрушення (перерозподіл вантажу) по циклу на величину ==, можна одержати нове опорне рішення Х2.
Визначимо, як зміниться цільова функція при переході до нового опорного рішення. При зрушенні на одиницю вантажу по циклу, відповідному клітинці (l, до), приріст цільової функції рівно різниці двох сум: ==, де - сума вартостей перевезень одиниць вантажу в непарних клітинках циклу, відмічених знаком «+», - сума вартостей перевезень одиниць вантажу в парних клітинках циклу, відмічених знаком «-».
У клітинках, відмічених знаком «+», величини вантажу додаються, що приводить до збільшення значення цільової функції Z((), а в клітинках, відмічених знаком «-», величини вантажу зменшуються, що приводить до зменшення значення цільової функції.
Якщо різниця сум для вільної клітинки (l, до) менше нуля, тобто <0, той перерозподіл величини по відповідному циклу приведе до зменшення значення Z(() на величину , тобто опорне рішення можна поліпшити. Якщо ж величини , звані оцінками, для всіх вільних кліток таблиці транспортної задачі ненегативні, те значення цільової функції не можна зменшити і опорне рішення оптимальне. Отже, ознакою оптимальності розподільного методу є умова =0. (11)
Для вирішення транспортної задачі розподільним методом необхідно знайти початкове опорне рішення. Потім для чергової опорної клітинки (l, до) побудувати цикл і обчислити оцінку . Якщо оцінка ненегативна, перехід до наступної вільної клітинки. Якщо ж оцінка негативна, слід здійснити зрушення по циклу на величину ==. В результаті вийде нове опорне рішення.
Для кожного нового опорного вирішення обчислення оцінок починається з першої вільної клітинки таблиці. Очевидність вільних клітинок, що перевіряються, доцільно встановлювати у порядку зростання вартості перевезень , оскільки розв'язується задача на знаходження мінімуму.
9. Метод потенціалів.
Широко поширеним методом рішення транспортних задач є метод потенціалів. Цей метод дозволяє спростити найбільш трудомістку частину обчислень – знаходження оцінок вільних клітинок.
Теорема 8. (ознака оптимальності опорного рішення). Якщо допустиме рішення Х=((), i=1,2,,…,m, j=1,2,…,n транспортної задачі є оптимальним, то існує потенціали (числа) постачальників , i=1,2,,…,m і споживачів , j=1,2,…,n, задовольняючі наступним умовам:
++== при >0, (12)
++ при =0. (13)
Доказ. Використовуємо другу теорему подвійності. Запишемо математичну модель транспортної задачі
,
, i=1,2,,…,m,
, j=1,2,…,n,
0, i=1,2,,…,m, j=1,2,…,n.
складемо математичну модель подвійної задачі. Позначимо через , i=1,2,,…,m змінні (оцінки), відповідні першим m рівнянням системи обмежень, і через , j=1,2,…,n змінні, відповідні останнім n рівнянням. Записуємо
F(U, V)==, ++, i=1,2,,…,m, j=1,2,…,n.
Кожне обмеження подвійної задачі містить тільки дві змінні, оскільки вектор-умова системи обмежень початкової задачі має тільки дві відмінні від нуля (рівні одиниці) координати ,i-ю і (m+j) -у. Умов позитивності подвійна задача не має, оскільки всі обмеження в початковій задачі – рівність. По другій теоремі подвійності, якщо при підстановці в систему обмежень подвійної задачі деяке обмеження виконується як строга нерівність ++<<, то відповідна координата оптимального рішення початкової задачі рівна нулю, тобто =0. Якщо ж оптимальним рішенням обмеження задовольняється як рівність ++==, то відповідна координата оптимального рішення відмінна від нуля, тобто >0.
Група рівності (12) ++== при >0 використовується як система рівнянь для знаходження потенціалів. Неважко бачити, що ця система могла мати дещо інший вигляд, наприклад --++== або --==, якщо перед тим, як записати подвійну задачу, всі рівняння однієї з груп рівнянь початкової задачі помножити на (-1).
Дана система рівнянь має m+n невідомих , i=1,2,,…,m і , j=1,2,…,n. Число рівнянь системи, як і число відмінних від нуля координат невиродженого опорного рішення, рівне m+n-1. оскільки число невідомих системи на одиницю більше числа рівнянь, то одній з них можна задати значення довільно, а інші знайти з системи.
Група нерівностей (13) ++ при =0 використовується для перевірки оптимальності опорного рішення. Ці нерівності зручно записати у вигляді ==++-- при =0. (14)
Числа називаються оцінками вільних кліток таблиці або векторів-умов транспортної задачі, що не входять в базис опорного рішення. В цьому випадку ознаку оптимальності можна сформулювати так само, як в симплексному методі (для задачі на мінімум): опорне рішення є оптимальним, якщо для всіх векторів-умов (клітинок таблиці) оцінки непозитивні.
Оцінки для вільних клітинок транспортної таблиці використовуються для поліпшення опорного рішення. З цією метою знаходять клітинку (до, l) таблиці, відповідну max{{}==. Якщо 0, те рішення оптимальне. Якщо ж >0, то для відповідної клітинки (до, l) будують цикл і покращують рішення, перерозподіляючи вантаж == по цьому циклу.
Приклад
Знайти оптимальний розв’язок транспортної задачі:
А = ( 100; 200; 10; 50 )
B = ( 150; 50; 120; 40 )
3 1 2 8
7 6 5 4
C = 4 3 4 7
6 7 6 6
Рішення:
ai = 360 ; bi = 360
ai = bi = 360 - задача закритого типу. Побудуємо опорний план методом мінімальної вартості :
V1 V2 V3 V4
|
Ai Bi |
100 |
200 |
10 |
50 |
|
150 U1 |
3 |
1 150 |
2 |
8 |
|
50 U2 |
7 |
6 |
5 |
4 50 |
|
120 U3 |
4 60 |
3 50 |
4 10 |
7 |
|
40 U4 |
6 40 |
7 |
6 |
6 0 |
Заповнення клітинок повинно бути m + n – 1
Z1 = 150 1 + 50 4 + 60 4 + 50 3 + 10 4 + 40 6 = 1020
Перевіримо план на oптимальність розподільним методом:
C11 = 3 - 1 + 3 – 4 = 1
C12 = 2 – 4 + 3 – 1 = 0
C13 = 8 – 6 + 6 – 4 + 3 – 1 = 6
C21 = 7 – 4 + 6 – 6 = 3
C22 = 6 – 4 + 6 – 6 + 4 – 3 = 3
C23 = 5 – 4 + 6 – 6 + 4 – 4 = 1
C42 = 7 – 3 + 4 – 6 = 2
C43 = 6 – 4 + 4 – 6 = 0
Так як всі Cij 0, то план оптимальний.
Перевіримо план на оптимальність методом потенціалів:
u1 + v2 = 1 u1 = 0 v1 = 1
u2 + v4 = 4 u2 = 3 v2 = 1
u3 + v1 = 4 u3 = 3 v3 = 1
u3 + v2 = 3 u4 = 5 v4 = 1
u3 + v3 = 4
u4 + v1 = 6
u4 + v4 = 6
d11 = 3 – ( 0 + 1 ) = 2 d23 = 5 – ( 3 + 1 ) = 1
d13 = 2 – ( 0 + 1 ) = 1 d34 = 7 – ( 3 + 1 ) = 3
d14 = 8 – ( 0 + 1 ) = 7 d42 = 7 – ( 5 + 1 ) = 1
d21 = 7 – ( 3 + 1 ) = 3 d43 = 6 – ( 5 + 1 ) = 0
d22 = 6 – ( 3 + 1 ) = 2
Так як всі d ij 0, то план оптимальний Z opt = 1020
Завдання для самостійного виконання
Задача 1.
Деяке об’єднання складається з двох підприємств, які виготовляють столи та трьох меблевих магазинів. Виробництво столів першим підприємством описане в задачі 1., друге постачає столів у кількості 100 одиниць. Вартості перевезення одиниці продукції від підприємства до магазинів наведено в ум. од.:
|
Підприємства-виробники |
Магазини |
||
|
1 |
2 |
3 |
|
|
1 |
23 |
19 |
22 |
|
2 |
20 |
13 |
17 |
Перший магазин реалізовує 10 одиниць продукції, другий – 25 і третій – 200. Знайти оптимальний план перевезень продукції, що дає можливість мінімізувати сумарну вартість перевезень. Врахувати умову, що з першого підприємства вся продукція має бути вивезена повністю.
Задачі
За наведеними в таблиці витратами на перевезення вантажу від пунктів постачання А1, А2, А3 до пунктів споживання В1, В2, В3, В4, а також обсягами запасів продукції в пунктах постачання та її попиту в пунктах споживання знайти оптимальний план транспортної задачі.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
5 3 1 |
4 2 6 |
3 5 3 |
4 5 1 |
160 140 60 |
|
Попит |
90 |
80 |
50 |
80 |
1.
2.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
4 7 13 |
3 11 9 |
5 6 10 |
10 8 12 |
110 100 190 |
|
Попит |
100 |
120 |
110 |
80 |
3.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
4 6 3 |
2 3 2 |
3 5 6 |
1 6 3 |
80 140 70 |
|
Попит |
80 |
50 |
50 |
70 |
4.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
2 3 4 |
3 2 3 |
2 5 2 |
4 1 1 |
130 140 130 |
|
Попит |
120 |
130 |
100 |
120 |
5.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
6 5 3 |
7 1 2 |
3 4 6 |
2 3 2 |
180 90 170 |
|
Попит |
60 |
80 |
100 |
160 |
6.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
8 4 3 |
1 6 5 |
9 2 8 |
7 12 9 |
110 190 90 |
|
Попит |
80 |
90 |
170 |
80 |
7.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
9 6 8 |
7 2 10 |
5 4 12 |
3 6 1 |
175 125 140 |
|
Попит |
180 |
110 |
60 |
40 |
8.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
5 7 2 |
7 2 3 |
4 3 6 |
2 1 8 |
200 175 225 |
|
Попит |
100 |
130 |
80 |
190 |
9.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
5 4 8 |
4 6 2 |
4 3 5 |
2 7 9 |
260 180 200 |
|
Попит |
180 |
160 |
210 |
180 |
10.
|
Пункт постачання |
Витрати на перевезення одиниці вантажу до пункту споживання |
Обсяг запасів продукції |
|||
|
В1 |
В2 |
В3 |
В4 |
||
|
А1 А2 А3 |
3 5 2 |
3 3 1 |
2 1 4 |
4 2 2 |
180 60 80 |
|
Попит |
120 |
40 |
50 |
80 |
Варіант 01 Варіант 03
А = ( 50, 40, 10, 100) А = ( 100, 180, 120, 130)
В = (120, 10, 40, 30) В = (200, 110, 130, 140)
3 1 2 8 1 2 6 7
С = 7 6 5 4 С= 6 7 1 2
4 3 4 7 3 4 5 1
6 7 6 6 1 4 2 1
Варіант 02 Варіант 04
А = ( 10, 100, 80, 70) А = ( 120, 80, 90, 10)
В = (40, 60, 50, 200) В = (20, 40, 180, 50)
1 5 4 3 1 5 6 7
С = 6 7 2 1 С= 4 3 2 1
5 4 5 5 1 1 1 1
2 3 1 7 2 1 4 6
Варіант 05 Варіант 09
А = ( 120, 80, 120, 200) А = ( 100, 20, 80, 10)
В = (200, 100, 150, 50) В = (90, 50, 40, 70)
1 4 3 2 4 3 2 1
С = 5 6 7 1 С= 5 6 7 8
9 1 1 10 3 5 2 7
2 3 5 8 5 1 4 2
Варіант 06 Варіант 10
А = ( 50, 40, 90) А = ( 100, 80, 30, 70)
В = ( 30, 70, 80) В = (90, 50, 40, 70)
1 5 4 1 4 3 2
С = 2 6 7 С= 5 6 7 8
2 1 1 9 8 6 5
5 5 5 4
Варіант 07 Варіант 11
А = ( 100, 200, 300, 150) А = (60, 40, 80, 50)
В = (120, 80, 400, 100) В = (70, 30, 60, 70)
1 2 3 7 1 2 4 6
С = 2 5 6 2 С= 4 3 2 1
8 7 1 1 2 3 3 2
1 1 5 4 6 2 2 3
Варіант 08 Варіант 12
А = ( 100, 50, 50, 200) А = (20, 10, 40, 50)
В = (80, 30, 20, 170) В = (30, 15, 25, 40)
5 6 7 8 1 2 4 6
С = 4 5 3 2 С= 5 4 3 1
1 1 1 1 2 1 1 2
6 7 6 5 1 2 5 3
Варіант 13 Варіант 17
А = (100, 200, 10, 50) А = ( 40, 20, 50, 10)
В = (150, 50, 120, 40) В = (3, 17, 35, 45)
3 1 2 8 1 3 4 3
С = 7 6 5 4 С= 2 5 4 2
4 3 4 7 6 1 1 1
6 7 6 6 1 2 3 4
Варіант 14 Варіант 18
А = (40, 80, 50, 50) А = ( 70, 60, 80)
В = (100, 95, 45, 35) В = (70, 40, 80, 30)
1 5 4 3 3 2 3 1
С = 2 6 7 8 С= 4 5 4 2
7 8 4 2 8 4 5 8
1 1 1 1
Варіант 15 Варіант 19
А = ( 10, 210, 10, 80) А = (30, 40, 10, 20)
В = (120, 80, 90, 50) В = (40, 30, 150, 10)
3 1 2 8 1 2 3 4
С = 7 6 5 4 С= 5 3 1 6
4 3 4 7 7 4 2 5
6 7 6 6 6 3 8 1
Варіант 16 Варіант 20
А = ( 60, 40, 30, 50) А = ( 100, 180, 120, 130)
В = (70, 30, 40, 50) В = (200, 110, 130, 140)
3 4 2 1 1 2 6 7
С = 5 2 3 4 С= 6 7 1 2
1 8 7 2 3 4 5 1
2 3 6 5 1 4 2 1
Питання для самоконтролю
Класичне формулювання транспортної задачі.
Сформулюйте транспортну задачу за критеріями:
Найменшої вартості перевезень
Найменшого терміну перевезень
За яких умов транспортна задача називається збалансованою?
За яких умов транспортна задача називається незбалансованою?
Як незбалансовану транспортну задачу привести до збалансованої?
Що таке опорний план перевезення? Методи його обчислення?
Скільки компонент повинно бути в опорному плані?
За яких умов транспортна задача називається виродженною?
Що таке цикл у розподільчій матриці ТЗ?
Метод потенціалів розв’язання транспортної задачі?
Розподільний метод розв’язання ТЗ?
За яких умов наявний план перевезення буде оптимальним?
При аналізі табличних даних в Excel можна для заданого значення результату і певних умов (обмежень) визначити величини впливових змінних. Це здійснюється за допомогою програми пошуку рішень.
Вирішення оптимізацій них задач
За допомогою настройки Поиск решения потрібно визначити структуру посівів озимої пшениці, проса і гречки, щоб прибуток від реалізації продукції був максимальним при таких умовах:
загальна площа посіву не перевищує –1000га;
запаси мінеральних добрив – 1200 ц.д.р.;
трудові ресурси 70000 люд.-год.;
площа гречки не більше 200 га.
Нормативи затрат праці, добрив і розмір прибутку в розрахунку на 1га. Посівів
наведені в таблиці. 6.1
Табл. 6.1
|
Показники |
Одиниця виміру |
Припадає на 1 га посівів |
||
|
Витрати праці |
Люд.- год |
70 |
60 |
56 |
|
Витрати добрив |
ц |
1,6 |
1,5 |
1,0 |
|
Прибуток |
Ум. Од |
161 |
75 |
275 |
Для рішення задачі слід скласти її математичну модель:
Знайти МАХ цільової функції:
С=161х+75х+275х, де змінні х,х, х, - площі посівів кожної культури.
При таких обмеженнях:
х+х+х1000 – сума площ не перевищує загальної площі;
70х+60х+56х70000
1,6х+1,5х+х1200
х200
Пошук рішення здійснюється у такій послідовності дій:
розташувати вихідні данні так, як показано на таблиці рис 6.1;
Рис. 6.1. Вихідні дані
установити курсор у чарунку Е6;
використовуючи майстра функцій, обчислити функцію СУММПРОЗИВ,
де у поле Массив 1 вивести діапазон чарунок В5:D5 і натиснути клавішу [f4]
щоб зробити цю адресу абсолютною, у поле Массив 2 – відповідно B6:D6 і натиснути кнопку ОК (згідно обмеженню першому);
продублювати цю формулу у чарунку Е6:Е10 (згідно обмеження цільової функції) (рис. 6.2)
Рис. 6.2. Розрахунки
установити курсор у чарунку Е10 – цільова функція;
вибрати команду Сервис – Поиск решения;
у вікні Поиск решения заповнити так поля, як указано (обмеження додавати за допомогою кнопки Добавить (рис.6. 3) )
Рис. 6.3. Додавання обмежень
натиснути кнопку Параметры і встановити параметри, як вказано на рис 6.4, і натиснути кнопку ОК;
Рис. 6.4. Встановлення пареметрів
у вікні Поиск решения натиснути кнопку Выполнить;
якщо результати вас задовольняють, у вікні Результаты поиска решения (рис. 6.5) вибрати перемикач Сохранить найденое решение і натиснути кнопку ОК.
Рис. 6.5. Результати пошуку рішення
На рис. 6.5 бачимо результати розв’язання задачі. Площа озимої пшениці – 625 га,
Гречки – 200 га, прибуток – 155625 грн, використано всі ресурси по добривах, але залишилися недовикористаними площа та трудові ресурси.
Тема 7. Розв’язання транспортної задачі
Відомо обсяги поставок і потреба споживачів (таб. 7.1). Задано тарифи на перевезення 1т. Вантажу від кожного постачальника кожному споживачу (таб. 7.2).
Необхідно визначити напрямок та обсяги вантажоперевезень з мінімальними витратами на перевезення. При цьому всі вантажі повинні бути вивезені, а потреби задоволені. Перевезення вантажу повинно здійснюватися тільки від постачальника до споживача.
Вхідні данні
Таб. 7.1. Постачальники Вантаж Таб. 7.2. Споживачі вантаж
|
1 2 3 4 |
1900 2050 1800 1950 |
|
7700 |
|
|
1 2 3 4 5 6 |
1320 1250 1230 1200 1340 1360 |
|
7700 |
Тарифи на перевезення, грн./т
|
Постачальники |
Споживачі |
|||||
|
1 |
2 |
3 |
4 |
5 |
6 |
|
|
1 |
7 |
6 |
8 |
10 |
5 |
6 |
|
2 |
8 |
6 |
9 |
7 |
8 |
5 |
|
3 |
6 |
10 |
5 |
8 |
8 |
7 |
|
4 |
10 |
9 |
7 |
8 |
8 |
8 |
Розташувати ці данні як показано на рис 7.1
рис 7.1. розташування вхідних даних для розв’язання задачі
Для розв’язання цієї задачі необхідно:
Тест 1 Яка необхідна умова розв’язання економічної задачі симплексним методом:
а). Вільні члени від’єднані;
б). Вільні члени додані;
в). В нерівностях повинен бути тільки знак ≤;
г). В нерівностях можуть бути різні знаки.
Тест 2. Як заповняється Z рядок, якщо задача на мах:
а). Коефіцієнти беремо з цільової функції;
б). Коефіцієнти беремо з цільової функції з оберненим знаком;
в). Коефіцієнти беремо з нерівностей.
г). Інші варіанти.
Тест 3. Як заповнюється Z рядок, якщо задача на min:
а). Коефіцієнти беремо з цільової функції з оберненим знаком;
б). Коефіцієнти беремо з цільової функції:
в). Коефіцієнти беремо з нерівностей;
г). Інші варіанти.
Тест 4. Як визначається вирішальний стовпчик, якщо задача на мах:
а). По Z рядку найбільше додатне число;
б). По Z рядку найбільше від’ємне число по модулю;
в). По більших членах найбільше додатне число;
г). По більших членах найбільше від’ємне число по модулю.
Тест 5. Як визначається вирішальний стовпчик, якщо задача на min:
а). По Z рядку найбільше від’ємне число по модулю;
б). По Z рядку найбільше додатне число;
в). По вільних членах найбільше від’ємне число по модулю;
г). По вільних членах найбільше додатне число.
Тест 6.Як визначається симплексне відношення:
а). Коефіцієнти цільової функції ділимо на елементи вирішального стовпчика;
б). Вільні члени ділимо на елементи вирішального стовпчика;
в). Інші варіанти.
Тест 7. Коли план буде оптимальним, якщо задача на мах:
а). в Z ряду всі елементи від’ємні;
б). В Z ряду всі елементи додатні;
в). В Z ряду всі елементи від’ємні або нульові;
г). В Z ряду всі елементи додатні або нульові.
Тест 8. Коли план буде оптимальним, якщо задача на min:
а). В Z ряду всі елементи від’ємні ;
б). В Z ряду всі елементи додатні;
в). В Z ряду всі елементи додатні або нульові;
г). В Z ряду всі елементи від’ємні або нульові.
Тест 9. Яка умова розв’язання задачі М методом:
а). вільні члени від’ємні;
б). вільні члени додатні;
в). в нерівностях повинен бути тільки знак ≤;
г). В нерівностях можуть бути різні знаки.
Тест 10. Як заповнюється Z рядок, якщо задача на min:
а). Коефіцієнти беремо з цільової функції;
б). Коефіцієнти беремо з цільової функції з оберненим знаком;
в). Коефіцієнти беремо з нерівностей;
г). Інші варіанти.
Тест 11. Як визначається вирішальний стовпчик, якщо задача на мах:
а). По Z рядку найбільше додатне число;
б). По Z рядку найбільше від’ємне число по модулю;
в). По L рядку найбільше додатне число;
г). По L рядку найбільше від’ємне число по модулю.
Тест 12. Як визначається вирішальний стовпчик, якщо задача на min:
а). По Z рядку найбільше від’ємне число по модулю;
б). По Z рядку найбільше додатне числи;
в). По L рядку найбільше додатне число;
г). По L рядку найбільше від’ємне число по модулю.
Тест 13. Коли план буде оптимальним, якщо задача на min:
а). По Z рядку всі елементи нульові або від’ємні;
б). По Z рядку всі елементи додатні або нульові;
в). По L рядку всі елементи від’ємні;
г). По L рядку всі елементи додатні.
Тест 14. Коли план буде оптимальним, якщо задача на max:
а). По Z рядку всі елементи додатні або нульові;
б). По Z рядку всі елементи від’ємні або нульові;
в). По L рядку всі елементи від’ємні;
г). По L рядку всі елементи додатні.
Тест 15. Якщо одна з пари двоїстих задач сформульована на мах цільової функції, то друга:
а). На min;
б). На max;
в). Інші варіанти.
Тест 16. Коефіцієнти цільової функції однієї із задач є:
а). Вільними членами системи обмежень другої задачі;
б). Коефіцієнтами системи обмежень;
в). Обмеженими коефіцієнтами системи обмежень
Тест 17. Що таке М у задачах лінійного програмування.
а) дуже маленьке число;
б) помилка при обчисленнях;
в) дуже велике число;
г) грошова оцінка.
Тест 18. Що таке коефіцієнти структурних зрушень?
а) Коефіцієнти в стовпцях змінних першої симплексної таблиці
б) Коефіцієнти Z-рядка першої симплексної таблиці;
в) Коефіцієнти Z-рядка останньої симплексної таблиці
г) Коефіцієнти в стовпцях змінних останньої симплексної таблиці;
д) Коефіцієнти в рядках змінних останньої симплексної таблиці;
Тест 19. Змінювати оптимальний план можна в таких напрямках:
Тест 20. Введення додаткових умов в оптимальний план можливе в таких випадках:
Тест 21. Що таке альтернативні розв’язки?
Тест 22. Матриці, складені з коефіцієнтів обмежень вихідної і двоїстої задач, є:
Тест 23. Чим відрізняються симетричні і несиметричні спряжені задачі?
Тест 24. Який запис має канонічна форма задачі лінійного програмування?
Тест 25. Критерій оптимальності опорного плану?
|
[1] Мета і програма викладання дисципліни [2] Форма і критерії оцінки [2.1] Тема 1. Графічний метод розв'язання задач лінійного програмування [2.2] Тема 2. Симплексний метод розв'язку задачі лінійного програмування. [2.3] Тема 3. М-метод (метод великих штрафів) [2.4] Тема 4. Двоїста задача лінійного програмування [2.5] Тема 5. Транспортна задача лінійного програмування, її структура та методи розв'язку [2.6] Тема 6. Пошук рішення [3] ТЕСТИ
[4] [5] ВИКОРИСТАНА ЛІТЕРАТУРА |
Математичне програмування
Робочий зошит. Модуль 1.
Склали: О.С. Бондар – к.е.н.
М.І. Трофимчук – к.е.н.
А.Ф Неборака - - асистент
О.Ю Углова - - асистент
С.І. Романенко - - асистент
О.В. Савчук - - асистент
О.В. Лісовий - - асистент
О.Б. Яломистий - - асистент
В.І. Кармазін - асистент
Редактор
Комп’ютерна верстка
Здано до склад. Підп. До друку Формат Ум. друк. арк. Тираж Зам. ціна 09117 Біла Церква, Соборна пл.,8; тел. 3-11-01