МІНІСТЕРСТВО ОСВІТИ І НАУКИ РЕСПУБЛІКИ КАЗАХСТАН
КАЗАХСЬКИЙ ДЕРЖАВНИЙ ЖІНОЧИЙ ПЕДАГОГІЧНИЙ ІНСТИТУТ
КАФЕДРА ІНФОРМАТИКИ
Дипломна робота
ПО ТЕМІ:
В« Рішення транспортної задачі лінійного програмування в середовищі MS Excel В»
Виконала: студентка 4курса,
протокол № о/о, р/о, спец. В«ІнформатикаВ»
Оспанова А.А.
Науковий керівник:
к.т.н., доцент старший викладач
Г.І. Салгараева Мусіраліев Ж.А.
Алмати 2008
ЗМІСТ
ВСТУП
Глава I Задачі лінійного програмування
1.1 Загальна характеристика задачі лінійного програмування
1.2 Математична постановка задачі лінійного програмування
Глава II Основні методи рішення транспортної задачі лінійного програмування
2.1 Математична постановка транспортної задачі
2.2 Рішення транспортної задачі за допомогою програми Ms Excel
2.3 Рекомендації за рішенням задач оптимізації за допомогою надбудови В«Пошук рішенняВ»
Глава III Двоїста задача лінійного програмування
3.1 Математичне формулювання двоїстої задачі лінійного програмування
3.2 Математична постановка двоїстої задачі про фарби
3.3 Рішення двоїстої задачі про фарби за допомогою програми Ms Excel
Висновок
Література
Введення
Транспортна задача.
У деякому географічному регіоні є фіксоване число пунктів виробництва і зберігання деякого однорідного продукту та кінцеве число пунктів споживання цього продукту. В якості продукту може виступати, наприклад, нафта, вугілля, пісок, цемент, т.д. Для кожного з пунктів виробництва і зберігання відомий обсяг виробництва продукту або його запасу. Для кожного пункту споживання задана потреба в продукті у цьому пункті споживання.
Потрібно визначити оптимальний план перевезень продукту, так щоб потреби у всіх пунктах споживання були задоволені, а сумарні витрати на транспортування всієї продукції були мінімальними.
Рисунок1. Ілюстрація транспортної задачі для двох пунктів виробництва і трьох пунктів споживання
Очевидно, оціночної функцією в даній задачі є сумарні витрати на транспортування всієї продукції, а обмеженнями служать обсяги виробництва і потреби в продукті в кожному пункті споживання.
Дана задача також є однією з класичних завдань лінійного програмування, методи її вирішення ми будемо розглядати далі. В бізнес додатках ця задача відома як задача про переміщення товарів зі складів на торгові точки або задача про планування ланцюжків постачань. У разі штучного товару, наприклад, телевізори, комп'ютери, пилососи, автомобілі тощо, відповідна транспортна задача відноситься до класу задач цілочисельного програмування.
Транспортна завдання: Зменшення витрат на перевезення.
У цій роботі ми розглянемо рішення класичної транспортної завдання Excel 7.0 дозволяє знаходити оптимальне рішення, зберігаючи задані обмеження.
Транспортна задача є класичною завданням дослідження операцій. Безліч задач розподілу ресурсів зводяться саме до цієї задачі.
1. Математична постановка транспортної завдання.
Загальна постановка транспортної задачі полягає у визначенні оптимального плану перевезень деякого однорідного вантажу з т пунктів відправлення А1, А2, ..., Ат в п пунктів призначення В1, В2, .., Вп. При цьому в якості критерію оптимальності зазвичай береться або мінімальна вартість перевезень всього вантажу. Позначимо через сij тарифи перевезення одиниці вантажу з i-го пункту відправлення в j-й пункт призначення, через ai-запаси вантажу в j-му пункті відправлення, через bj-потреби у вантажі в j-му пункті призначення, а через xij-кількість одиниць вантажу, перевезеного з i-го пункту відправлення в j-й пункт призначення. Тоді математична постановка задачі полягає у визначенні мінімального значення функції:
, [1]
при умовах:
[2]
[3]
[4]
Оскільки переменниеудовлетворяют системам рівнянь (2) і (3) і умові неотрицательности (4), то забезпечується доставка необхідної кількості вантажу до кожного з пунктів призначення (умова (2)), вивезення наявного вантажу з усіх пунктів відправлення (умова (3)), а також виключаються зворотні перевезення (умова (4)).
Визначення 1. Усяке невід'ємне рішення системи лінійних рівнянь (2) і (3), яке визначається матрицею Х = () (i = 1, ... m; j = 1, ... n), називається планом транспортної завдання.
Определеніе2. План = () (i = 1, ... m; j = 1, ... n), при якому функція (1) приймає своє мінімальне значення, називається оптимальним планом транспортної задачі.
Зазвичай вихідні дані транспортної задачі записують у вигляді (див. таблицю 1.)
Очевидно, загальне наявність вантажу у постачальників одно:
,
а загальна потреба у вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, тобто
одиниць.
Якщо загальна потреба у вантажі в пунктах призначення дорівнює запасу вантажу в пунктах відправлення, тобто
=, [5]
Те модель такої транспортної задачі називається закритою. Якщо ж зазначена умова не виконується, то модель транспортної задачі називається відкритою.
Таблиця 1
Теорема 1 . Для разрешимости транспортної задачі необхідно і достатньо, щоб запаси вантажу в пунктах відправлення були рівні потребам у вантажі в пунктах призначення, тобто щоб виконувалося рівність (5)
Пункти
відправлення
Пункти призначення
Запаси
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
Потреб
ности
...
...
У разі перевищення запасу над потребою
>,
вводиться фіктивний (n +1)-й пункт призначення з потребою
= -
і відповідні тарифи вважаються рівними нулю: = 0 (i = 1, ... m). Отримана таким чином завдання є транспортною задачею, для якої виконується рівність (5).
Аналогічно, при
<,
вводиться фіктивний (m +1)-й пункт відправлення з запасом вантажу
= -
і тарифи пологаем рівними нулю: = 0 (j = 1, ... m). Цим задача зво...
