ФГТУ СПО Волгоградський технологічний коледж
Спеціальність 230105 «Програмне забезпечення обчислювальної техніки і автоматизованих систем»
Курсова робота
З дисципліни «Математичні методи»
Тема:
Реалізація алгоритму симплекс-методу з довільними вільними членами
Виконав: Левітін С.А.
Студент гр. ВТ - 3-1
Перевірив: Тьоткін А.А.
Волгоград 2011
Зміст
Введення
1. Постановка завдання
2. Математичне забезпечення
. Розробка алгоритму програми
. Приклад роботи програми
Висновок
Список використаної літератури
Введення
Основною метою даного проекту є закріплення теоретичних знань в області вирішення завдань базових лінійного програмування симплекс - методом, що отримав в літературі також назву методу послідовного поліпшення плану та реалізація поставленої задачі на мові програмування С ++.
Симплексний метод вирішення завдань лінійного програмування - обчислювальна процедура, заснована на принципі послідовного поліпшення рішень - переходу від однієї базисної точки до іншої, для якої значення цільової функції більше (ці операції фіксуються в симплексній таблиці). Доведено, що якщо оптимальне рішення існує, то воно обов'язково буде знайдено через кінцеве число кроків (за винятком так званої «виродженої задачі; при якій можливе явище« зациклення », т. Е. Багаторазового повернення до одного й того ж положення).
Даний метод був розроблений американським математиком Джорджем Данцигом (George Dantzig) в 1947 році.
1. Постановка завдання
Необхідно розробити програму, вирішальну базову задачу лінійного програмування симплекс-методом за допомогою симплекс-таблиць. Вільні члени системи обмежень задачі можуть бути довільними.
2. Математичне забезпечення
Прикладом задачі лінійного програмування є цільова функція з певним напрямом екстремуму і система обмежень для цієї цільової функції. Наприклад:
F (X)=3x1 + 5x2 + 4x3= gt; max
, 1x1 + 0,2x2 + 0,4x3 lt;=1100
. 05x1 + 0.02x2 - 0.02x3 lt;=120
x1 + x2 + 2x3 lt;=8000
Необхідно знайти оптимальний план даної задачі за допомогою симплекс-методу з використанням симплекс-таблиці.
3. Розробка алгоритму програми
Перед початком роботи необхідно було зрозуміти сам алгоритм симплекс-методу. Для цього вирішувалося кілька завдань письмово. Після освоєння алгоритму була продумана структор самого проекту. Першим ділом був написаний клас user_data , який приймає дані користувача, тобто Саму задачу, яку необхідно вирішити за допомогою симплекс-методу. Розглянемо вміст заголовного файлу цього класу.
Лістинг 1. user_data.h
# ifndef _USER_DATA_H _
# define _USER_DATA_H _
user_data {: get_data_from_user (); user_data_is_valid ();: * function; * fm; ** system; * sign; num_v; num_l; way;
};
# endif/* _USER_DATA_H_ */
Розглянемо всі захищені змінні-члени даного класу.
int num_v зберігає в собі значення кількості змінних вихідної задачі.
Int num_l зберігає в собі значення кількості обмежень вихідної завдання.
double * function зберігає значення коефіцієнтів цільової функції завдання. Даний член є покажчиком типу double, для якого в подальшому буде виділена пам'ять і виробиться ініціалізація його як одновимірного масиву з розміром num_v .
double * fm зберігає в собі значення вільних членів системи обмежень. Також є покажчиком типу double, який буде инициализирован як одновимірний масив з розміром num_l .
double ** system зберігає в собі значення коефіцієнтів самої системи обмежень. Це член є покажчиком на масив покажчиків,...
