Курсовая работа: Розв’язання задач лінійного програмування
A 2 m
...
A n m
Процес переходу від попередньої таблиці до наступної взагалі спрощується: достатньо дописати номер рядка та стовпчика провідного елемента до всіх мінорів таблиці, що стоять у чисельниках, крім елементів того ж рядка, та до всіх мінорів знаменників (в початковій таблиці знаменник рівний одиниці).
Але слід звернути увагу на такий випадок: якщо провідний елемент опинився у тому ж рядку, що і раніше введений елемент, то “більш застарілий” слід викинути з мінору, а новий загальним чином дописати в кінець списку рядків та стовпчиків мінору відповідно. Звідси випливає, що рядки в мінорі не можуть повторюватись, тобто їх не може бути більше, ніж рівнянь обмежень, і мінори не будуть нескінченно розростатись. Але може зустрітися випадок, коли в списку стовпців, з яких складається мінор, зустрінуться однакові стовпці, тобто мінор рівний нулю. Це якраз відповідає нульовим елементам таблиці на відповідному кроці і вписується в загальне правило.
За допомогою даного методу можна набагато точніше обчислювати розв’язки задач лінійного програмування без накопичування похибки (при використанні комп’ютера), яка виникає при діленні. Цього можна досягти, якщо зберігати чисельники окремо, а знаменники взагалі завжди однакові.
3 Розробка моделі розв’язку задачі
За умовою задачі необхідно знайти оптимальний варіант розподілу бюджету на різний вид реклами, завдяки якому він в результаті дав би найбільшій прибуток фірмі.
Для розрахунку здачі введемо деякі позначення:
- витрати бюджету фірми на телерекламу;
- витрати на рекламу по радіо;
- витрати на рекламу у газетах.
В результаті потрібно отримати прибуток, тому цільова функція буде максимізуватися. Завдяки досвіду минулих років, відомо, який прибуток буде отриманий фірмою, при витраті одного долара на різні види реклами, тому можна записати цільову функцію, вона матиме наступний вигляд:
(3.1)
За умовою задачі витрати не повинні перевищувати 10000, тому можемо записати перше обмеження:
(3.2)
Витрати на теле- та радіорекламу не повинна перевищувати шістдесят відсотків бюджетних коштів, тому можна записати друге обмеження:
(3.3)
За умовою витрати на газетну рекламу не повинні перевищувати більш як удвічі витрати на радіо рекламу:
(3.4)
Обов’язково потрібно врахувати наступні нерівності, адже вони суттєво вплинуть на розв’язок задачі:
(3.5)
Оскільки дана задача буде розв'язуватись симплекс методом, приведемо модель до вигляду, який буде зручним для використання симплекс методу. Всі вище записані обмеження об’єднаємо до системи і отримаємо:
(3.6)
Для того, щоб розв’язати задачу симплекс-методом необхідно систему обмежень, яка містить нерівності, перетворити до системи рівнянь. Для цього введемо додаткові змінні 
. При використанні симплекс методу, цільова функція повинна мінімізуватися, для цього помножимо її на -1 та додамо додаткові змінні з відповідними коефіцієнтами. Тоді функція мети перетвориться до наступного вигляду:
(3.7)