О.Б. Яломистий - - асистент

МАТЕМАТИЧНЕ

ПРОГРАМУВАННЯ

(Модуль 1)

Робочий зошит для вивчення дисципліни студентами економічного факультету за модульно-рейтинговою системою навчення

Біла Церква

УДК 681.3.06Затверджено

методичною комісією економічного факультету

(Протокол № 4 від 22.12.2005 р.)

Укладачі: О.С. Бондар – к.е.н., М.І. Трофимчук – к.е.н., А.Ф Чеборака, О.Ю Углова, С.І. Романенко, О.В. Савчук, О.В. Лісовий, О.Б. Яломистий, В.І. Кармазін - асистенти

Анотація

Математичне програмування: Робочий зошит для вивчення дисципліни студентами економічного факультету за модульно-рейтинговою системою навчання. Модуль 1/

, О.С. Бондар, М.І. Трофимчук – к.е.н., А.Ф Чеборака, О.Ю Углова. – Біла Церква, 2006. – 44

Рецензент канд. екон. наук А.А. Ільєнко

© БДАУ, 2006

Мета і програма викладання дисципліни

Предметом вивчення курсу "Математичне програмування" є способи математичної формалізації економічних систем і методи знаходження оптимальних планів їх діяльності. Мета курсу - дати студентам математичну підготовку, яка дозволяє будувати математичні моделі і обирати оптимальні рішення для організації управління економічними процесами.

При вивченні математичного програмування передбачається модульно-рейтингова оцінка знань студентів за 100 бальною шкалою, в основі якої лежить структурно-модульна схема. Набрана студентом кількість балів є відповідним еквівалентом для одержання підсумкової оцінки з навчального предмета:

№ п/п	Назва теми	Кількість годин
Лекції	Лаб.-практичні
І.	Модуль 1. Задачі дослідження операцій та їх класифікація. Геометрична інтерпритація загальної задачі лінійного програмування. Симплексний метод розв'язування задач лінійного програмування. Симплексний метод з штучним базисом (М - метод.) Теорія двоїстості в лінійному програмуванні.

Тема 2. Задачі дослідження операцій та їх класифікація. Місце математичного програмування в розв’язуванні задач дослідження операцій. Основна задача ЛП. Загальні відомості про лінійне програмування. Загальна задача лінійного програмування. Основна задача лінійного програмування. Основні поняття. Економічна постановка задачі лінійного програмування. Математичне формулювання задачі лінійного програмування..

	Тема 3. Геометрична інтерпритація загальної задачі лінійного програмування. ОЗЛП. Поняття симплекса. Графічний спосіб розв'язування ОЗЛП з двома змінними. Особливості розв'язування задач лінійного програмування з великою кількістю змінних Визначення області допустимих розв'язків Побудова вектора-нормалі і визначення оптимального розв’язку у області допустимих розв’язків Економічна інтерпретація геометричного розв’язку задачі лінійного програмування
	Тема 4. Симплексний метод розв'язування задач лінійного програмування. Ідея методу, область визначення. Алгоритм простого (прямого) симплекс -методу. Побудова опорного (базисного) розв'язку задачі. Ознаки оптимальності опорних планів Ознаки необмеженості цільових функцій в допустимій області Ознаки наявності нескінченної множини оптимальних планів Ознаки оптимальності розв'язку. Вироджені плани задачі лінійного програмування та проблеми зациклення Алгоритм симплексного методу розв’язання не вироджених задач лінійного програмування Особливі випадки застосування симплекс-метода. Методика інтерпретації симплекс - таблиць. Аналіз моделі на стійкість.

	Тема 5. Симплексний метод з штучним базисом (М - метод.) Метод з штучним базисом. Ідея методу, область визначення. Алгоритм М - методу (методу великих штрафів). Ознаки оптимальності розвитку ОЗЛП М -методом. Практичне застосування.

Тема 6. Теорія двоїстості в лінійному програмуванні. Постановка прямої та двоїстої задач лінійного програмування. Правила побудови математичних моделей прямої та двоїстої (симетричної) задач лінійного програмування. Симетричні та несиметричні двоїсті задачі. Теореми двоїстості та їх економічний зміст. Інтерпретація двоїстих оцінок в ЗЛП. Постоптимальний аналіз лінійних моделей.

Форма і критерії оцінки

Форма контролю	К-ть заходів	Оцінка	Сума балів
max	min	max	min
Модуль 1
1. Семінари
2. Реферати
3. Контрольна робота
4. Виступ
Всього:

МОДУЛЬ 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. Графічний метод розв'язання задач лінійного програмування

Графічний метод застосовують, як правило, для розв'язання задач лінійного програмування з двома змінними. Він спирається на геометричну інтерпретацію загальної задачі лінійного програмування та властивості її розв'язку:

1) оптимальний розв'язок, якщо він існує, лежить на границі області припустимих розв'язків;

2) щоб знайти оптимальний розв'язок, необхідно рухатись від однієї точки до іншої у напрямі зменшення (мінімуму), та зростання (максимуму) функції мети.

Задача лінійного програмування має такий вигляд:

,

,

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

,

Тоді схему алгоритму графічного методу послідовно можна подати таким чином:

1) побудувати область припустимих розв'язків R, виходячи з обмежень задачі;

2) побудувати вектори нормалі і функції Z;

3) зміщувати пряму паралельно самій собі у напрямі вектора (в іншому напрямі, якщо шукаємо мінімум Z) доти, поки вона не буде проходити через крайню точку області R, найбільш віддалену (найменш віддалену – у випадку ) від початку координат.

При цьому можуть бути три випадки:

a) вектор-функція Z та одна із сторін області припустимих розв'язків R паралельні; в цьому випадку цільова функція досягає оптимального значення в будь-якій точці цієї сторони, тобто існує нескінченна множина оптимальних розв'язків задачі;

б) вектор-функція Z та область R мають одну крайню точку, координати якої визначають єдиний оптимальний розв'язок;

в) у напрямі вектора область припустимих розв'язків не обмежена; в цьому випадку задача не має розв'язку;

4. Обчислення координат крайньої точки та значення цільової функції.

Практичні завдання

Задача №1

Компанія виробляє продукцію двох видів А і В. Обидві потребують роботи

двох цехів: збирального і оздоблювального. Відомості про виробництво:

Цех	Продукція	Разом необхідно робочих годин
А	В
Збиральний
Оздоблювальний
Валовий прибуток на одиницю

Компанія зацікавлена в найбільшій прибутковості цих комбінацій продукції. Знайти скільки треба виробляти продукції А і В, щоб валовий прибуток був максимальний. (кількість робочих годин збільшується на номер варіанту).

Задача № 2

Для виробництва товарів А і В підприємство використовує два види сировини І і ІІ. Витрати сировини на виробництво товарів наведені в таблиці.

Сировина	Витрати сировини на виробництво товару
А	В
І		а
ІІ	b

Кількість на складі кожного виду сировини: І – a ( b+1) одиниць; ІІ – b (a+1) одиниць. При реалізації одиниця товару А приносить прибуток b+2 грн., одиниця товару В – а грн.. Спланувати виробництво таким чином, щоб сумарний прибуток був максимально можливим. ( a =№ варіанту + 3, b = № варіанту + 7 )

Задача № 3

Знайти графічним методом мінімум і максимум лінійної функції

F(x₁,x₂)=a x₁ + b x₂

в області, що визначена системою обмежень

x1 + a x2 < a + ab,

b x1 + x2< b + ab

x1 ³0 ; x2 ³ 0. ( a =№ варіанту + 7 , b = =№ варіанту + 9 )

Задачі для самостійного розв’язання

Задачі

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

			max Z = 8x1+6x2 3x1+5x2£11 4x1+x2£8 x1³0 , x2³0		max Z = 3x1+4x2 3x1+2x2£8 x1+4x2£10 x1³0 , x2³0

Питання для самоконтролю

1. Як ви розумієте поняття „математична модель” та її визначення?

2. Особливості розбулови математичних моделей в теорії дослідження операцій.

3. Як ви розумієте термін „параметри управління”?

4. Принципова різниця між детермінованими та стохастичними математичними моделями.

5. Основні етапи розбудови проекту дослідження операцій.

6. Навести приклади задач лінійного програмування з практичною орієнтацією.

7. Характерні особливості задач лінійного програмування.

8. Форми запису задач лінійного програмування.

9. Відмінності у запису ЗЛП у стандартній та каннонічній формі.

10. Що таке лінія рівня функцій двох змінних?

11. Умови графічного розв’язання ЗЛП.

12. Графічне тлумачення можливих ситуацій у розвязанні ЗЛП.

Тема 2. Симплексний метод розв'язку задачі лінійного програмування.

Ідея методу, область визначення. Алгоритм методу. Побудова опорного плану. Ознаки оптимальності опорного плану. Особливі випадки застосування симплекс-методу. Інтерпретація симплекс-таблиці – аналізу моделі на стійкість.

Тема 3. М-метод (метод великих штрафів)

Ідея методу, область визначення. Алгоритм методу. Ознаки оптимальності. Практичне застосування.

Приклад

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

РЕСУРСИ	ТЕХНОЛОГІЧНІ ЗАСОБИ	ОБСЯГ РЕСУРСІВ
№		Т1	Т2	Т3
1	Робоча сила, людино-год.
	Попит, т
	Електроенергія, квт/год
	Продуктивність технологічних засобів, грн.

Необхідно визначити інтенсивність використання технологічних засобів.

Рішення:

Економіко математична модель задачі матиме такий вигляд:

Цільова функція:

Z = 500 x₁ + 400 x₂ + 300 x₃ ® max,

Обмеження:

(х_j ³ 0 ; j = 1,3 )

Зведемо систему обмежень до канонічного вигляду:

15х₁ + 20х₂ + 100х₃ + х₄ = 1500

х₁ + 2х₂ + 3х₃ + х₅ = 200

10х₁ + 20х₂ + 10х₃ + х₆ = 200

Z = 500х₁ + 400х₂ +300х₃ + 0х₄ + 0х₅ + 0х₆ ® max

Опорний план:

х₄ = 1500

х₅ = 200

х₆ = 200

Z = 0

Ресурси є, але виробництво не ведеться. Тому прибуток дорівнює нулю.

Виходячи з опорною плану побудуємо першу симплексну таблицю:

№	Базисні змінні	Сі	Вільні члкни	Х1	Х2	Х3	Х4	Х5	Х6	Симплексні відношення
	х4		1500							100
	х5
3	х6
	Z			-500	-400	-300

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

№ п/п	Базисні змінні	Сі	Вільні члени	Х1	Х2	Х3	Х4	Х5	Х6
	Х1				1,33	6,67	0,067
	Х5				0,67	-3,67	-0,067
	Х6				6,67	-56,67	-0,67
	Z				266,67	3033,33	33,33

Так як в Z – рядку усі елементи невід’ємні, то в другій таблиці отримано оптимальний розв’язок.

Технологічні засоби Т₂ і Т₃ використовувати недоцільно. Найбільший прибуток 50000 грн. дасть використання 100 одиниць технологічних засобів Т₁

Попит залишиться недовикористаним у кількості 100 т.

Електроенергія залишиться недовикористаною у кількості 1000 квт / год.

Аналіз останньої симплексної таблиці.

Якщо до оптимального п лану ввести одну одиницю технологічного засобу Т₂ , то доцільно зменшити використання технологічного засобу Т₁ на 1,33 одиниці. Попит зменшиться на 0,67 т, а використання електроенергії зменшиться на 6,67 квт / год. Прибуток збільшиться на 266,67 грн.

Якщо до оптимального плану ввести одиницю технологічного засобу Т₃, то доцільно зменшити використання технологічного засобу Т₁ на 6,67 одиниць.

При цьому попит збільшиться на 3,67 т, а використання електроенергії збільшиться на 56,67 квт / год. Прибуток при цьому зросте на 3033,33 грн.

Якщо ресурси робочої сили збільшити на 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 кг споживчої речовини
А	В	С
І
ІІ

Вартість 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. На виробництво двох видів продукції потрібні чотири групи устаткування (див. таблицю). Необхідно організувати випуск продукції так. щоб прибуток від її реалізації був найбільшим.

Група виробничого устаткування	Необхідна кількість устаткування для випуску одиниці продукції	Кількість устаткування у групі
І	ІІ
А В С Д
Прибуток від реалізації

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

Виріб	Час обробки виробу на верстаті, год
І	ІІ	ІІІ
А В	0,5 0,25	0,4 0,3	0,2 0,4

Час роботи верстатів І, ІІ і ІІІ - відповідно до 40, 36 і 36 год на тиждень. Прибуток від реалізації одного виробу А і В – відповідно 5 і 3 грн. Визначити тижневі норми виробництва виробів А і В, при яких прибуток буде максимальний.

8. Для виробництва двох видів продукції використовують токарне, фрезерне та шліфувальне устаткування. Норми витрат часу на обробку одного виробу продукції та фонд робочого часу для кожного типу устаткування наведено в таблиці.

Тип виробничого устаткування	Витрати часу на обробку одного виробу продукції, год	Фонд робочого часу устаткування, год
Фрезерне Токарне Шліфувальне
Прибуток від реалізації одиниці продукції, грн

Визначити план випуску продукції, що забезпечить найбільший прибуток.

Задачі для самостійного розв’язання

9. На меблевій фабриці зі стандартних листів фанери необхідно вирізати заготовки трьох видів у кількості відповідно 24, 31 і 18 шт. Кожний лист фанери можна розрізати для заготовки двома способами. Кількість отриманих заготовок при кожному способі розрізування, а також залишки фанери після розрізування наведено у таблиці.

Вид заготовки	Кількість заготовок при розрізування за способом, шт
першим	другим
I ІІ ІІІ
Залишки фанери, см2

Визначити, яку кількість фанери і яким способом потрібно розрізати, щоб отримати бажану кількість заготовок з найменшими залишками.

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

Вид корму	Кількість одиниць кормів для щоденного споживання	Загальна кількість корму
І ІІ ІІІ
Прибуток від реалізації однієї шкури, у.о.

Визначити, скільки лисиць і нутрій треба вирощувати, щоб прибуток від реалізації хутра був найбільшим.

Задача 11.

Підприємство виготовляє письмові столи типів А, В, і С. Для одного столу типу А необхідно 2 м2 деревини, для столу типу В – 3 м2, а для столу типу С – 5 м2. Підприємство може отримати до 400 м2 деревини за тиждень. Для виготовлення одного столу типу А потрібно 12 хвилин роботи обладнання, для моделі типу В – 30 хв. Та для моделі типу С – 40 хв. Обладнання може використовуватися 3000 хв. На тиждень. Оцінено, що за тиждень може бути реалізовано до 550 столів.

Відомо, що прибуток від реалізації одного письмового столу типу А становить 30 дол., типу В – 40 дол., та типу С – 60 дол. Визначити, скільки столів кожного типу необхідно виготовляти за тиждень.

Необхідно:

1. Записати математичні моделі прямої та двоїстої задач.

2. Знайти оптимальні плани прямої та двоїстої задач.

3. Виконати аналіз оптимальних планів прямої та двоїстої задач:

3.1. Визначити оптимальні обсяги виробництва продукції.

3.2. Визначити ресурси, що використовуються не повністю та вказати кількість лишків відповідних ресурсів.

3.3. Визначити ресурси, збільшення загального запасу яких забезпечить зростання прибутку.

3.4. Вказати види продукції, виготовлення яких за оптимальним планом не передбачається і визначити величину перевищення витрат на виготовлення одиниці продукції над її вартістю.

3.5. Вказати межі можливих змін загального запасу ресурсів, за яких структура оптимального плану не зміниться.

3.6. Вказати межі можливих змін вартостей кожного виду продукції, за яких структура оптимального плану продукції не змінюється.

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

Питання для самоконтролю

1. Як розуміти поняття базису в n-мірному векторному просторі?

2. За яких умов система лінійних алгебраічних рівнянь буде сумісною? За яких умов СЛАР буде мати єдиний розв’язок?

3. Що таке базисні та вільні змінні у СЛАР?

4. Який запис має канонічна форма задачі лінійного програмування?

5. Що таке опорний план ЗЛП?

6. За якими формулами виконуються перерахунки коефіцієнтів системлінійних лінійних алгебраічних рівнянь при заміні базису?

7. За яких умов доцільно змінювати досягнутий опорний план? Критерій оптимальності опорного плану?

8. Як і з якою метою будується фіктивний базис симплексного методу розв’язання ЗЛП?

Тема 4. Двоїста задача лінійного програмування

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

Кожній задачі лінійного програмування можна поставити у відповідність іншу, пов’язану певним чином з початковою задачею. Такі задачі називають двоїстими, або спряженими. Спільний розгляд двоїстих пар задач дуже важливий в економічному аналізі оптимального плану. Відповідність між вихідною та двоїстою задачами полягає в побудові на основі першої задачі двоїстої до неї /як вихідна може розглядатися будь-яка зі спряженої пари задач/. Двоїсті задачі бувають симетричні і несиметричні.

Симетричні задачі

Початкова задача Двоїста задача

/1.10/ /1.10а/

/1.11/ /1.11а/

/1.12/ /1.12а/

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

Розглянемо правила побудови двоїстої задачі.

1. Кожному і - му обмеженню вихідної задачі відповідає змінна двоїстої задачі; і навпаки, кожному j - му обмеженню двоїстої задачі відповідає змінна вихідної задачі.

2. Якщо одна з пари двоїстих задач сформульована на максимум цільової функції, то друга - на мінімум і навпаки.

3. Обмеження-нерівності слід записувати зі знаком « » - при мінімізації цільової функції.

4. Коефіцієнти цільової функції однієї із задач є вільними членами системи обмежень другої задачі.

5. Матриці, складені з коефіцієнтів обмежень вихідної і двоїстої задач, є взаємно транспонованими.

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

Теорема 1.1. /Перша теорема двоїстості/. Якщо одна зі спряжених задач має оптимальний план, то його має й друга задача, причому значення цільових функцій збігаються, тобто .

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

Оптимальний розв’язок двоїстої задачі знаходять за даними останьої симплексної таблиці вихідної задачі за формулою

, де - матриця-рядок двоїстих змінних ;

- матриця-рядок, складена з коефіцієнтів цільової функції для базисних змінних останньої симплексної таблиці вихідної задачі;

- матриця обернена до матриці В, складеної з компонентів базисних векторів останньої симплексної таблиці вихідної задачі.

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

Зауважимо, що визначається додаванням до відповідної оцінки коефіцієнтів . Вважаємо, що одинична матриця в початковій задачі утворена векторами .

Теорема 1.2. /Друга теорема двоїстості/. Якщо при підстановці компонентів оптимального плану в і - те або j - те обмеження вихідної /двоїстої/ задачі це обмеження виконується як рівняння, то відповідна змінна спряженої задачі буде строго більша від нуля, а коли воно виконується як строга нерівність, то відповідна змінна спряженої задачі дорівнює нулю.

Наведемо формальний запис цієї теореми для задач /1.10/ - /1.12/ і /1.10а/ - /1.12а/.

Нехай дано оптимальний план вихідної задачі у вигляді .

Тоді маємо:

якщо , то ;

якщо , то .

У разі, коли дано оптимальний план двоїстої задачі дістаємо:

якщо , то ;

якщо , то .

Теорема 1.3. /Третя теорема двоїстості./ Двоїсті оцінки показують приріст цільової функції, який зумовлюється малою зміною вільного члена відповідного обмеження:

або .

Приклад 1.1. Розв’язати двоїсту задачу, використовуючи розв’язок вихідної

Записуємо двоїсту задачу

Здобута пара задач несиметрична, оскільки обмеження вихідної задачі записані в канонічній формі. Отже, двоїсті змінні У - довільні /можуть бути як додатними, так і від’ємними або такими, що дорівнюють нулю/.

Задачі для самостійного розв’язання

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

Питання для самоконтролю

Економічний сенс задачі, спряженої до задачі планування обсягів виробництва.

За яких умов спряжені задачі називаються симетричними?

Якими правилами необхідно користуватися, формулюючи спряжену симетричну задачу?

Як пов’язані оптимальні розв’язки спряжених задач?

Як пов’язані змінні вихідної та спряженої задач?

Як побудувати оптимальний план спряженої задачі за наявності такого плану вихідної задачі?

Що стверджують основні теореми спряженості?

Тема 5. Транспортна задача лінійного програмування, її структура та методи розв'язку

Однорідний вантаж зосереджений у 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. Методи побудови початкового опорного рішення.

Метод північно-західного кута.

Існує ряд методів побудови початкового опорного рішення, найпростішим з яких є метод північно-західного кута. У даному методі запаси чергового постачальника використовуються для забезпечення запитів чергових споживачів до тих пір, поки не будуть вичерпані повністю, після чого використовуються запаси наступного по номеру постачальника.

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

1. якщо , то і виключається постачальник з номером i, , k=1, 2, …, n, доk j, ;

2. якщо , то і виключається споживач з номером j, , k=1, 2, …, m, доk i, ;

3. якщо , то і виключається або i-й постачальник, , k=1, 2, …, n, доk j, , або j-й споживач, , k=1, 2, …, m, доk i, .

Нульові перевезення прийнято заносити в таблицю тільки тоді, коли вони потрапляють в клітинку (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 +

+ -

3 4

рис 2.

Зрушенням по циклуна величину називається збільшення об'ємів перевезень у всіх непарних клітинках циклу, відмічених знаком «+», на і зменшення об'ємів перевезень у всіх парних клітинках, відмічених знаком «-», на .

Теорема 7. Якщо таблиця транспортної задачі містить опорне рішення, то при зрушенні по будь-якому циклу, що містить одну вільну клітинку, на величину == вийде опорне рішення.

Доказ. У таблиці транспортної задачі, що містить опорне рішення, виберемо вільну клітинку і відзначимо її знаком «+». По теореме6. для цієї клітинки існує єдиний цикл, який містить частину клітинок, зайнятих опорним рішенням. Пронумеруємо клітинки циклу, починаючи з клітинки, відміченої знаком «+». Знайдемо == і здійснимо зрушення по циклу на цю величину.

У кожному рядку і в кожному стовпці таблиці, що входять в цикл, дві і лише дві клітинки, одна з яких відмічена знаком «+», а інша - знаком «-». Тому в одній клітинці об'єм перевезення збільшується на , а в іншій зменшується на , при цьому сума всіх перевезень в рядку (або стовпці) таблиці залишається незмінною. Отже, після зрушення по циклу як і раніше і запаси всіх постачальників вивозяться повністю, і запити всіх споживачів задовольняються повністю. Оскільки зрушення по циклу здійснюється на величину == , то всі об'єми перевезень будуть ненегативними. Отже, нове рішення є допустимим.

Якщо залишити вільною одну з клітинок з нульовим об'ємом перевезення, відповідних , те число зайнятих клітинок буде рівне N=m+n-1. Оскільки цикл єдиний, те видалення з нього однієї клітинки розриває його. Цикл із зайнятих клітинок, що залишилися, утворити не можна, відповідні вектори-умови лінійно незалежні, а рішення є опорним.

8. Розподільний метод.

Один з найпростіших методів рішення транспортної задачі – розподільний метод.

Хай для транспортної задачі знайдене початкове опорне рішення і обчислене значення цільової функції на цьому рішенні Z(( ). По теоремі 6 для кожної вільної клітинки таблиці задачі можна побудувати єдиний цикл, який містить цю клітинку і частину клітинок, зайнятих опорним рішенням. Зазначивши цей цикл і здійснивши зрушення (перерозподіл вантажу) по циклу на величину == , можна одержати нове опорне рішення Х2.

Визначимо, як зміниться цільова функція при переході до нового опорного рішення. При зрушенні на одиницю вантажу по циклу, відповідному клітинці (l, до), приріст цільової функції рівно різниці двох сум: == , де - сума вартостей перевезень одиниць вантажу в непарних клітинках циклу, відмічених знаком «+», - сума вартостей перевезень одиниць вантажу в парних клітинках циклу, відмічених знаком «-».