Розв’язання задач лінійного програмування (стр. 3 из 5)

В основі симплекс-методу є процес побудови початкової симплекс-таблиці, та перехід від однієї симплекс-таблиці до наступної згідно певних правил. Такі переходи виконуються доти, доки не буде виконано критерій оптимальності або не стане зрозумілим, що розв’язку не існує. Перехід від однієї симплекс-таблиці до наступної здійснюється наступним чином. Згідно певних критеріїв вибирається провідний елемент таблиці (b_k,l), який стоїть на перетині рядка, який виводиться з базису, та стовпчика, який буде введено до базису. Елементи таблиці перераховуються так:

. (2.

)

Очевидним чином дану формулу можна спростити до наступної:

. (2.2)

тобто всі елементи нової таблиці матимуть вигляд a_i,j/ x, де х – провідний елемент попередньої таблиці (зауваження: якщо дроби можна скоротити, то цього НЕ слід робити для правильності подальших міркувань).

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

Таблиця 2.1 – Симплекс-таблиця

¼	¼
¼	a/x	b/x	¼
¼	c/x	d/x	¼
¼	¼

Нехай на другому кроці провідним буде елемент d/x. Тоді елемент a/x перераховується за загальним правилом:

(2.3)

причому легко переконатися, що чисельник (ad-bc)/x буде цілим числом.

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

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

мінор, що складений з елементів перетину рядків

зі стовпцями

початкової таблиці. Сама таблиця матиме вигляд:

Таблиця 2.2 – Симплекс-таблиця

A₁¹	A₂¹	...	A_n¹
A₁²	A₂²	...	A_n²
...	...	...	...
A₁^m	A₂^m	...	A_n^m

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

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

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

3 Розробка моделі розв’язку задачі

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

Для розрахунку здачі введемо деякі позначення:

- витрати бюджету фірми на телерекламу;

- витрати на рекламу по радіо;

- витрати на рекламу у газетах.

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

(3.1)

За умовою задачі витрати не повинні перевищувати 10000, тому можемо записати перше обмеження:

(3.2)

Витрати на теле- та радіорекламу не повинна перевищувати шістдесят відсотків бюджетних коштів, тому можна записати друге обмеження:

(3.3)

За умовою витрати на газетну рекламу не повинні перевищувати більш як удвічі витрати на радіо рекламу:

(3.4)

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

(3.5)

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

(3.6)

Для того, щоб розв’язати задачу симплекс-методом необхідно систему обмежень, яка містить нерівності, перетворити до системи рівнянь. Для цього введемо додаткові змінні

. При використанні симплекс методу, цільова функція повинна мінімізуватися, для цього помножимо її на -1 та додамо додаткові змінні з відповідними коефіцієнтами. Тоді функція мети перетвориться до наступного вигляду:

(3.7)

Розв'язок цієї моделі наведений у розділі тестування даної курсової роботи.

4 Розробка програмного забезпечення

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

4.1 Призначення програми

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

4.2 Вибір середовища програмування

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

Excel — це великий охоронець списків (хоча їх прийнято називати в Excel базами даних) і творець таблиць. Тому Excel як не можна краще підходить для відстежування інформації про товари, що продаються, про обслуговуваних клієнтів, про службовців, яких контролює будь-яка організація і т.д.