Приклад. На цих складах маємо продукцію а1, а2, а3

Нехай маємо 4 склади А1, А2, А3, А4.

На цих складах маємо продукцію а1, а2, а3. Маємо 3 споживача В1, В2, В3 яким відповідно треба завезти продукцію у кількості в1, в2, в3.

Якщо на цих складах була б кількість продукції, для задоволення запитів, то виконалася б рівняння:

Але частіше всього нерівність:

Позначимо через Cij кошт перевезення одиниці вантажу з одного пункта у інший.

Обмеження та цільова функція виглядають так:

х – кількість вантажу, яке перевозиться з кожного складу, кожному споживачів;

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

Для цього уявимо х =0. Залишившуся систему можна вирішити звичайними методами. Набір використаних для рішення m змінних зветься базисом. Інші n-m змінні звуться незалежними. У кожній реальній системі може існувати декілька базисів, кожний зі своїм набором базисних та незалежних змінних. Якщо серед базисних рішень будуть такі які надають від’ємні значення змінним, то вони є неприпустимими і виключаються. Серед припустимих базисних рішень шукаються такі, які мінімізують (максимізують) лінійну цільову функцію. Ці рішення і є оптимальними.

4.4. Опис методики рішення транспортної задачи

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

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

У таблиці 4.1. та 4.2. наведені умови задачи та питомі (на один товарний вагон) витрати на перегін.

У таблиці 4.1. вказано, що в пунктах S1, S2, S3, маємо залишки порожніх товарних вагонів у кількостях 9, 4 та 8 вагонів, відповідно, у пунктах D1, D2, D3, D4, D5 не вистачає, відповідно, 3, 5, 4, 6 та 3 вагонів. (для спрощення уявимо, що задача збалансована, тобто сумарна кількість надлишкових вагонів дорівнюється сумарній кількості невистаючих вагонів).

У таблиці 4.2. наведени питомі витрати Cij на перегін одного порожнього вагона з пункту відправлення у пункт призначення J (i-строка, j-стовпець).

Таблиця 4.1 – Умови задачи

Пункти призначення	D1	D2	D3	D4	D5	Над-лишок
Пункти відправлення
S1	X11	X12	X13	X14	X15
S2	X21	X22	X23	X24	X25
S3	X31	X31	X33	X34	X35
Потреба

Таким чином, треба визначити такі значення Xij (i=1, 2, 3; j=1, 2, 3, 4, 5) таблиці 4.1., щоб задовольнити наданим обмеженням та мінімізувати сумарні витрати.

Таблиця 4.2 – Питомі витрати

Пункти призначення	D1	D2	D3	D4	D5
Пункти відправлення
S1	С11 -10	С12 -20	С13 -5	С14 -9	С15 -10
S2	С21 -2	С22 -10	С23 -8	С24 -30	С25 -6
S3	С31 -1	С31 -20	С33 -7	С34 -10	С35 -4

4.5. Методичні вказівки до виконання лабораторної роботи

4.5.1. Для виконання пп. 4.2.2, 4.2.3. необхідно ознайомитися із конспектом лекцій, вивчити методи лінійного програмування.

4.5.2. Для виконання пп. 4.2.3., 4.2.4. необхідно отримати у викладача вихідні дані.

4.5.3. Отримати результати рішення на конкретних даних, отримати роздрук вихідних даних.

4.6. Зміст звіту

4.6.1. Мета роботи.

4.6.2. Опис метода рішення транспортної задачи.

4.6.3. Блок – схема алгоритму.

4.6.4. Текст програми.

Контрольні питання

1 Сформулювати мету задачи лінійного програмування.

2 Методи рішення задач лінійного програмування на прикладі транспортної задачі.

3 Поняття цільової функції.

4 Принцип визначення обмежень у задачи лінійного програмування.

5 Поняття базисного рішення.

Література

Список основної літератури

Вершин О.Е. “Компьютер для менеджера”. –М.: Высшая школа, 1990.

Солонин И.С. “Математическая статистика в технологии машиностроения”. –М.: Машиностроение, 1972.

Перегудов Ф.И. “Введение в системный анализ”. – М.: Высшая школа, 1989.

Неймин Я.Г. “Модели в науке и технике”. –Л.: Наука, 1984.

Химмемблау Д.М. “Анализ процессов статистическими методами”. –Л.: Наука, 1989.

Черчмен У., Акоф Р. “Введение в исследование операций”. –М.: Наука, 1968.

Список додаткової літератури

Вальд А. “Последовательный анализ”. –М.: Физматгиз, 1960. –328с.

Бокс Дж., Дженкинс Г. “Анализ временных рядов. Прогноз и управление”. –М.: Мир – 406с.

Буслнеко Н.П. “Математическое моделирование производственных процессов”. –М.: Наука, 1969.

Сытник В.Ф., Караголова Е.А. “Математические модели в планировании и управлении предприятиями”. –К.: Высшая школа, Главное издательство, 1986. – 214с.