Решение задачи линейного программирования симплекс-методом

Лабораторная работа № 2.

Решение задачи линейного программирования симплекс-методом

Цель: Изучение прямой и двойственной задачи линейного программирования

Основные понятия оптимизации

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

Нахождение оптимального решения всегда предполагает наличие следующих составляющих:

1. Параметры, характеризующие исследуемый объект, которые в процессе решения задачи остаются неизменными: производительность станков, количество раскраиваемых деталей и т.д. Обозначим их А=(а1, а2,…,аn).
2. Параметры, которыми можно варьировать, добиваясь оптимального решения: ассортимент изготавливаемых изделий, координаты размещения деталей на раскраиваемом листе и т.д. Обозначим их Х=(х1, х2,…,хk).
3. Параметры, определяющие ограничения, которым должны удовлетворять варьируемые параметры: максимальный фонд рабочего времени станка, размер раскраиваемого листа и т.д. Обозначим их В=(b1, b2,…,bm).
4. Функция, которая связывает между собой известные и неизвестные параметры. Обозначим ее через W(A,X). Эта функция, с помощью которой можно сравнивать между собой получаемые варианты решения задачи. Она называется целевой функцией (или критерием качества).

Формально задачу оптимизации можно записать следующим образом:

[pic 1]

В тех случаях, когда целевая функция и система ограничений описываются линейными соотношениями, задача оптимизации называется задачей линейного программирования.

Процесс решения задачи линейного программирования обычно состоит из следующих этапов:

1. формализация постановки задачи, т.е. представление ее в виде схемы, таблицы, графиков и т.п.;
2. построение целевой функции, в качестве которой может выступать, например, максимальная прибыль или объем продукции, минимальные затраты и т.п.;
3. составление системы ограничений, которым должны удовлетворять искомые величины;
4. решение задачи.

Постановка задачи

Мебельная фирма производит тумбочки под телевизоры и компьютерные столы. Для изготовления одной тумбочки требуется 18 м2 материалов, а для одного стола – 30 м2. Фирма имеет возможность приобретать еженедельно не более 1800 м2 материалов. Время изготовления всех деталей тумбочки на станках составляет 2 часа, а стола –3 часа. Станки на предприятии могут работать не более 210 часов. Клиенты фирмы готовы покупать любое количество тумбочек по цене 2 у.е. за штуку, а столов – по 4 у.е., но не более 40 штук в неделю. Сколько тумбочек и столов следует выпускать фирме в неделю, чтобы получить максимальную прибыль.

Задачи линейного программирования (ЗЛП) можно решать двумя методами: графическим и симплексным.

1. Решение ЗЛП  графическим методом

1. Выполните формализацию постановки задачи, представив исходные данные в виде таблицы. Введите обозначения: х1 – количество тумбочек, которые следует выпускать за наделю; х2 – количество столов.

[pic 2]

1. Составьте целевую функцию. Поскольку х1 – количество тумбочек, которые следует выпускать за наделю, а цена одной тумбочки – 2 у.е., то общая прибыль от реализации тумбочек составит 2х1 у.е. Для столов соответственно – 4х2. Таким образом, общая прибыль составит 2х1 + 4 х2. Ее необходимо максимизировать. Таким образом, целевая функция будет иметь вид:

F(x1,x2) = 2х1 + 4 х2. → мах

1. Составьте систему ограничений:

[pic 3]

Первое ограничение учитывает возможности предприятия по приобретению материалов; второе – возможности имеющегося оборудования; третье – возможности сбыта продукции.

Добавьте условие неотрицательности искомых параметров

[pic 4]

и получите постановку ЗЛП:

[pic 5]

1. Определите область допустимых решений. Для этого необходимо построить три прямые, соответствующие неравенствам ограничений:

[pic 6]

Построение прямых проведите с использованием мастера диаграмм. Прямая линия определяется по двум точкам, поэтому вычислим пары точек для каждой прямой. Координату х1 задайте произвольно, а координату х2 – вычислите по соответствующей формуле.