Модифицированный симплекс-метод с мультипликативным представлением матриц

Примечание	Язык написания: Borland C++ 3.1
	Загрузить архив:
	Файл: simplex.zip (269kb [zip], Скачиваний: 172) скачать

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по “Системному анализу”

Тема: “Решение задач линейного программирования большой размерности”

Выполнил студент гр. Э-282:

     Богдановский А. А.

Проверил преподаватель:

Тихненко Е. В.

________________________

Дата:

“___” __________ 1996 г.

СОДЕРЖАНИЕ

TOC o "1-3" f                                                                                   GOTOBUTTON _Toc347013713PAGEREF _Toc347013713 3

2. Конкретизация задачи                                                                                           GOTOBUTTON _Toc347013714PAGEREF _Toc347013714 3

3. Математическая модель симплекс-метода с мультипликативным представлением обратной матрицы                                                              GOTOBUTTON _Toc347013715PAGEREF _Toc347013715 3

3.1. Модифицированный симплекс-метод                                                                                                              GOTOBUTTON _Toc347013716PAGEREF _Toc347013716 4

3.2. Мультипликативная форма обратной матрицы                                                                                          GOTOBUTTON _Toc347013717PAGEREF _Toc347013717 5

3.3. Преимущества метода                                                                                                                                             GOTOBUTTON _Toc347013718PAGEREF _Toc347013718 8

4. Алгоритм метода, реализованного в программе                                GOTOBUTTON _Toc347013719PAGEREF _Toc347013719 9

5. Текст программы SASIMPL                                                                                  GOTOBUTTON _Toc347013720PAGEREF _Toc347013720 11

6. Интерфейс пользователя                                                                                 GOTOBUTTON _Toc347013721PAGEREF _Toc347013721 11

6.1. Работа с программой                                                                                                                                             GOTOBUTTON _Toc347013722PAGEREF _Toc347013722 12

6.2. Формат файлов, содержащих постановку задач линейного программирования                         GOTOBUTTON _Toc347013723PAGEREF _Toc347013723 13

7. Результаты работы программы                                                                   GOTOBUTTON _Toc347013724PAGEREF _Toc347013724 14

СПИСОК ЛИТЕРАТУРЫ                                                                                                    GOTOBUTTON _Toc347013725PAGEREF _Toc347013725 17

Приложение I. Текст программы SASIMPL                                                     GOTOBUTTON _Toc347013726PAGEREF _Toc347013726 18

[А. А.1]В соответствии с общей постановкой задачи, возможностями студента, доступной литературой и другими факторами, студентом была конкретизирована и сформулирована следующая задача:

· “модифицированный симплекс-метод с мультипликативным представлением обратной матрицы”;

·

·

·

[А. А.2]Решаемая задача линейного программирования представлена в канонической форме и имеет следующий вид:

min F = cx, при Ax = b, x ³ 0 ,

где      c          -           вектор коэффициентов целевой функции (c₁,c₂,...,c_n);

A         -           матрица ограничений размера m´n ранга m, может быть представлена также как вектора [P₁, P₂, ..., P_n];

b          -           m-вектор правой части ограничений (b₁,b₂,...,b_m).         

Таким образом, поставленная задача имеет n - переменных и m - ограничений.

До рассмотрения мультипликативной формы кратко опишем этапы модифицированного симплекс-метода с хранением обратной матрицы в явной форме.

[А. А.3]Интерфейс пользователя

Программа SASIMPL имеет примитивный пользовательский интерфейс, который позволяет загружать данные о задачах из внешних файлов, решать их и просматривать результаты. Кроме того, программа предоставляет скромную справочную систему для удобства работы.

[А. А.1] Тихненко считает, что обращение к себе как к  третьему лицу - плохой тон...

[А. А.2] Оказывается каноническая форма постановки линейной задачи не обуславливает наличие начального опорного плана (единичного базиса) - это в принципе самая главная ошибка курсовика (то есть у меня требовалась постановка задачи не только в каноническом виде, но и чтобы присутствовал единичный базис...)

[А. А.3] Тихненко не понравилось в интерфейсе слишком!! много разных цветов (я это тоже осознал - цветов в программе, как на попугае...). Еще, естественно, не понравилось то, что задаваь задачу надо вне программы и то, что надо вручную делать единичный базис...